LeetCode OJ – 第38页

LeetCode 125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.length() == 0)
            return true;
        int i = 0, j = s.length() - 1;
        while(i < j) {
            while(i < j && !isalnum(s[i])) {
                i++;
            }
            while(i < j && !isalnum(s[j])) {
                j--;
            }
            if(i < j && tolower(s[i]) != tolower(s[j])) {
                return false;
            } else {
                i++;
                j--;
            }
        }
        return true;
    }
};

class Solution {

public:

bool isPalindrome(string s) {

if(s.length() == 0)

return true;

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

while(i < j) {

while(i < j && !isalnum(s[i])) {

i++;

}

while(i < j && !isalnum(s[j])) {

j--;

}

if(i < j && tolower(s[i]) != tolower(s[j])) {

return false;

} else {

i++;

j--;

}

return true;

}

};

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;

}

};