柳婼の blog – 第245页 – 我不管，反正我最萌～

LeetCode 303. Range Sum Query – Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.

class NumArray {
private:
    vector<int> v;
public:
    NumArray(vector<int> &nums) {
        if(nums.size() == 0)
            return ;
        v.push_back(nums[0]);
        for(int i = 1; i < nums.size(); i++) {
            v.push_back(v[i - 1] + nums[i]);
        }
    }

    int sumRange(int i, int j) {
        if(i == 0)
            return v[j];
        return v[j] - v[i - 1];
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

class NumArray {

private:

vector<int> v;

public:

NumArray(vector<int> &nums) {

if(nums.size() == 0)

return ;

v.push_back(nums[0]);

for(int i = 1; i < nums.size(); i++) {

v.push_back(v[i - 1] + nums[i]);

}

int sumRange(int i, int j) {

if(i == 0)

return v[j];

return v[j] - v[i - 1];

}

};

// Your NumArray object will be instantiated and called as such:

// NumArray numArray(nums);

// numArray.sumRange(0, 1);

// numArray.sumRange(1, 2);

LeetCode343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

Hint:

There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

我们知道…某数的n次方结果总是比乘法大…
如果可以拆成3…那就不要选择2…包括4(是2的平方)
如果可以拆成5…依旧小于3×2=6
如果可以拆成6…依旧小于3×3=9
如果可以拆成7…依旧小于3x2x2=9
如果可以拆成8…依旧小于3x3x2=18
如果可以拆成9…依旧小于3*3*3=27
所以说拆成大数还不如变成3的次方形式。。
4 = 2 + 2
5 = 2 + 3
6 = 3 + 3
7 = 3 + 3 + 1 = 3 + 4
8 = 3 + 3 + 2
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1 = 3 + 3 + 4
11 = 3 + 3 + 3 + 2
12 = 3 + 3 + 3 + 3
我的意思是…
如果有3 + 1 出现，那它是小于2的2次方的…
所以如果余数是1，就把3×1改成x4…

如果有3 + 2出现，那就没法拆成次方形式…
所以如果余数是2，依然是3×2…

如果有3 + 3出现，那一定大于 2的3次方…
所以如果余数是0，那就是3×3…

就是说…
尽可能拆成3的n次方形式…如果余数是1那就把3*1变成2*2…
找到规律后，代码就很简单，如下：

class Solution {
public:
    int integerBreak(int n) {
        if(n <= 3)
            return n - 1;
        int cnt = 1;
        while(n > 2) {
            cnt = cnt * 3;
            n = n - 3;
        }
        if(n == 0) 
            return cnt;
        else if(n == 1)
            return cnt / 3 * 4;
        else 
            return cnt * 2;
    }
};

class Solution {

public:

int integerBreak(int n) {

if(n <= 3)

return n - 1;

int cnt = 1;

while(n > 2) {

cnt = cnt * 3;

n = n - 3;

}

if(n == 0)

return cnt;

else if(n == 1)

return cnt / 3 * 4;

else

return cnt * 2;

}

};

LeetCode345. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

class Solution {
public:
    string reverseVowels(string s) {
        int i = 0, j = s.length() - 1;
        while(i < j) {
            while(i < j && s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u'
                        && s[i] != 'A' && s[i] != 'E' && s[i] != 'I' && s[i] != 'O' && s[i] != 'U') {
                i++;
            }
            while(i < j && s[j] != 'a' && s[j] != 'e' && s[j] != 'i' && s[j] != 'o' && s[j] != 'u'
                        && s[j] != 'A' && s[j] != 'E' && s[j] != 'I' && s[j] != 'O' && s[j] != 'U') {
                j--;
            }
            if(i < j) {
                swap(s[i], s[j]);
            }
            i++;
            j--;
        }
        return s;
    }
};

class Solution {

public:

string reverseVowels(string s) {

int i = 0, j = s.length() - 1;

while(i < j) {

while(i < j && s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u'

&& s[i] != 'A' && s[i] != 'E' && s[i] != 'I' && s[i] != 'O' && s[i] != 'U') {

i++;

}

while(i < j && s[j] != 'a' && s[j] != 'e' && s[j] != 'i' && s[j] != 'o' && s[j] != 'u'

&& s[j] != 'A' && s[j] != 'E' && s[j] != 'I' && s[j] != 'O' && s[j] != 'U') {

j--;

}

if(i < j) {

swap(s[i], s[j]);

}

i++;

j--;

}

return s;

}

};

LeetCode344. Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.

//方法一：最简单的办法，直接调用 reverse 函数。。
class Solution {
public:
    string reverseString(string s) {
        reverse(s.begin(), s.end());
        return s;
    }
};

//方法二：比较常规的做法，左右两边第一个和倒数第一个调换，第二个和倒数第二个调换...
class Solution {
public:
    string reverseString(string s) {
        for(int i = 0; i < s.length() / 2; i++) {
            swap(s[i], s[s.length() - i - 1]);
        }
        return s;
    }
};

//方法一：最简单的办法，直接调用 reverse 函数。。

class Solution {

public:

string reverseString(string s) {

reverse(s.begin(), s.end());

return s;

}

};

//方法二：比较常规的做法，左右两边第一个和倒数第一个调换，第二个和倒数第二个调换...

class Solution {

public:

string reverseString(string s) {

for(int i = 0; i < s.length() / 2; i++) {

swap(s[i], s[s.length() - i - 1]);

}

return s;

}

};

在 mac 系统下播放.csf 视频的方法

经过几个小时的折腾，试了十几种播放器，各种百度 google 必应。。先上结论：

无法直接播放。。只能在虚拟机中 windows 系统下安装 ScenicEidtor 软件格式转码成 wmv 或者 flv 解决。。

Moviest打开文件的选项里面.csf 文件是灰色的无法打开

VLC同上；

MPlayerX 显示“不支持的格式文件”

暴风影音也打不开

唯一能打开这格式的 wondershare Player 打开来后声音不清晰+没有画面出现

……

后来百度了一下 CSF 格式：

csf它可以把ppt和教师讲课的视频完美结合，很多大学和大型企业使用这套软件进行教学录像和远程教育，简称科建流媒体格式，有的人甚至称其为“大学课程专用格式”。

开发：江苏科建教育软件有限责任公司

所属：流媒体格式

国内自产的一种格式。。怪不得试了很多种外国的播放器都无法打开。。

最后知乎搜索了一下，也表示 mac 上面是无法实现直接打开的//所以放弃尝试吧。。

此处：各种求开发出 mac 可以直接播放.csf格式视频的播放器。。付费也可以。。

只能尝试用虚拟机里开windows，然后格式转换了。。

试了格式工厂，无法打开这个格式的文件。。

然后百度到只能用ScenicEditor转换。

转换成wmv格式转换的文件更小，flv格式效果更佳。

附上那软件的使用方法：http://jingyan.baidu.com/article/d2b1d1026ac8d45c7e37d492.html

一脸懵比：length() 以及 size_t

刚刚刷 leetcode 的时候又发生了一件灵异事件：

Snip20160420_20

//题目很简单：

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

但是报错了：

Snip20160420_21

奇怪点不在这，在于如果我把两个.length()替换成 int 型的len1和 len2，就 Accepted了。。

就是写成这样就对了：

Snip20160420_22

啊，为什么。。。为什么。。什么都没干啊只是等价替换了啊。。

a82aa4a836975b078e8d_size71_w440_h774

后来机智的我想起，原来在 IDE 里面编程的时候，每次用 .length()会有警告提醒：

Snip20160420_26

size_type。。。

Snip20160420_29

所以说在 unsigned 情况下，如果两个 length()相减，得到的是一个好大好大的值，因为unsingned和unsigned相减得到unsigned的数，也就是如果是负数的话得到的是int的最大值那样的数，但是在转为 int 型之后就会允许相减得到负数，是这样的么。。。验证一下：

Snip20160420_32

啊，我怎么可以这么机智~~(｀･ω･´)

746-160311154339 ~~~~~~~~~~~~