Code – 第242页

LeetCode 6. ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

class Solution {
public:
    string convert(string s, int numRows) {
        string t[numRows];
        string ans;
        int i = 0;
        while(i < s.length()) {
            for(int j = 0; j < numRows && i < s.length(); j++)
                t[j] += s[i++];
            for(int k = numRows - 2; k > 0 && i < s.length(); k--)
                t[k] += s[i++];
        }
        for(int j = 0; j < numRows; j++) {
            ans += t[j];
        }
        return ans;
    }
};

class Solution {

public:

string convert(string s, int numRows) {

string t[numRows];

string ans;

int i = 0;

while(i < s.length()) {

for(int j = 0; j < numRows && i < s.length(); j++)

t[j] += s[i++];

for(int k = numRows - 2; k > 0 && i < s.length(); k--)

t[k] += s[i++];

}

for(int j = 0; j < numRows; j++) {

ans += t[j];

}

return ans;

}

};

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