LeetCode Sum of Square Numbers Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a² + b² = c. Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

---

给定一个非负整数c，问是否存在两个整数a和b，使得a² + b² = c。 简单题，首尾指针法，首尾指针分别指向[0,c]，根据a² + b² 和 c的大小，首指针++或者尾指针–。 但是这样性能太差，过不了大数据，其实尾指针只需要到sqrt(c)即可，因为如果b大于sqrt(c)的话，a² + b² 肯定大于 c的。所以新的首尾指针范围就是[0,sqrt(c)]，性能大幅提升。 代码如下： [cpp] class Solution { public: bool judgeSquareSum(int c) { long long i = 0, j = sqrt(c) + 1; while (i <= j) { long long cur = i*i + j*j; if (cur == c)return true; else if (cur < c)++i; else –j; } return false; } }; [/cpp] 本代码提交AC，用时3MS。]]>

151. Reverse Words in a String

Given an input string, reverse the string word by word.

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

---

对一个字符串，以单词为单位进行逆序。注意字符串中可能会有多个连续的空格，还可能在首尾有空格。 如果允许使用额外的空间，那就好办，先把字符串分词，然后逆序拼接。代码如下：

class Solution {
public:
    void reverseWords(string& s)
    {
        string ans = "";
        int start = 0, end = 0, n = s.size();
        while (true) {
            while (start < n && s[start] == ‘ ‘)
                ++start;
            if (start >= n)
                break;
            end = start + 1;
            while (end < n && s[end] != ‘ ‘)
                ++end;
            if (end >= n)
                break;
            ans = s.substr(start, end – start) + " " + ans;
            start = end + 1;
        }
        if (end > start)
            ans = s.substr(start, end – start) + " " + ans;
        s = ans.substr(0, ans.size() – 1);
    }
};

本代码提交AC，用时9MS。

如果不借助额外空间，则只能在原字符串上进行逆序了，有意思。我们可以进行两次翻转，第一次对整个字符串翻转，然后遍历新字符串，对每个单词进行翻转。比如原字符串是”the sky is blue”，第一次翻转之后就是”eulb si yks eht”，再依次对每个单词翻转，就变成了”blue is sky the”。
我们知道对一个字符串进行翻转可以使用首尾指针的方法in-place实现，代码中为了可读性，直接调用了STL的reverse函数。

class Solution {
public:
    void reverseWords(string& s)
    {
        reverse(s.begin(), s.end()); 
        //i,j为新字符串每个单词的首尾位置，u,v为旧字符串每个单词的首尾位置
        int i = 0, j = 0, u = 0, v = 0, n = s.size();
        while (true) {
            while (u < n && s[u] == ‘ ‘)
                ++u;
            if (u >= n)
                break;
            v = u;
            while (v < n && s[v] != ‘ ‘)
                s[j++] = s[v++];
            reverse(s.begin() + i, s.begin() + j);
            if (v >= n)
                break;
            s[j++] = ‘ ‘;
            i = j;
            u = v;
        }
        if (j == 0)
            s = "";
        else if (s[j – 1] == ‘ ‘)
            s.resize(j – 1);
        else
            s.resize(j);
    }
};

本代码提交AC，用时6MS。虽然第二种方法更快，也更省空间，但是有很多边界条件很容易出错，我还是觉得第一种方法安全。
参考：http://www.cnblogs.com/grandyang/p/4606676.html

LeetCode 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”. Note: The vowels does not include the letter “y”.

---

把字符串中的所有元音字母逆序。简单题，使用首尾两个指针i,j，找到元音后交换，直到i>j。 完整代码如下： [cpp] class Solution { public: string reverseVowels(string s) { unordered_set<char> vowels = { ‘a’,’e’,’i’,’o’,’u’,’A’,’E’,’I’,’O’,’U’ }; int i = 0, j = s.size() – 1; while (i < j) { while (i < j&&vowels.find(s[i]) == vowels.end())++i; if (i >= j)break; while (i < j&&vowels.find(s[j]) == vowels.end())–j; if (i >= j)break; swap(s[i++], s[j–]); } return s; } }; [/cpp] 本代码提交AC，用时52MS。]]>

167. Two Sum II – Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

---

本题要在一个已排序数组中找两个数，使得这两个数的和等于一个目标target。这应该是LeetCode Two Sum的简化版吧，因为之前那个题有一种解法就是先对数组排序，然后首尾指针夹逼，现在这个题都排好序了，那还有什么好说的呢，直接借用之前的方法。 完整代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target)
    {
        int i = 0, j = numbers.size() – 1;
        while (numbers[i] + numbers[j] != target) {
            if (numbers[i] + numbers[j] > target)
                –j;
            else
                ++i;
        }
        return vector<int>({ i + 1, j + 1 });
    }
};

本代码提交AC，用时9MS。

LeetCode Reverse String Write a function that takes a string as input and returns the string reversed. Example: Given s = “hello”, return “olleh”.

---

本题要把一个字符串逆序一下。最简单的题了，两种方法，一种是直接调用STL的reverse函数；另一种方法是用首尾指针不断swap。 方法1代码如下： [cpp] class Solution { public: string reverseString(string s) { reverse(s.begin(), s.end()); return s; } }; [/cpp] 本代码提交AC，用时9MS。 方法2代码如下： [cpp] class Solution { public: string reverseString(string s) { int i = 0, j = s.size() – 1; while (i < j) { swap(s[i], s[j]); ++i; –j; } return s; } }; [/cpp] 本代码提交AC，用时也是9MS。]]>

125. Valid Palindrome

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

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

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

---

本题要判断一个字符串是否是回文串，回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时，只考虑数字和字母，并且忽略字母的大小写。 思路很简单，两个指针i,j，分别指向字符串的头尾，各自跳过所有非数字和字母的字符，然后把大写字母转换为小写字母，如果出现头尾字符不一样的情况，则不是回文，立即返回false。如果比完整个字符串都相等，则是回文，返回true。 完整代码如下：

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i < s.size() && j >= 0) {
            while (!isAlphaNum(s[i]) && i < s.size())
                i++;
            if (i >= s.size())
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && j >= 0)
                j–;
            if (j < 0)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC，用时12MS。

二刷。其实i,j不用走完全程，只需要走到他们交错之后就可以了，也就是只需要判断整个字符串的前半段和后半段是否逆序相等。
至于代码，其实就是把while循环和if条件判断改一下，如下：

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i <= j) {
            while (!isAlphaNum(s[i]) && i <= j)
                i++;
            if (i > j)
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && i <= j)
                j–;
            if (i > j)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC，用时9MS。

三刷。更简洁的代码：

class Solution {
public:
	bool IsValid(char c) {
		return (c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'z');
	}
	bool isPalindrome(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return true;
		int i = 0, j = n - 1;
		while (i < j) {
			s[i] = tolower(s[i]);
			s[j] = tolower(s[j]);

			if (!IsValid(s[i]))++i;
			else if (!IsValid(s[j]))--j;
			else {
				if (s[i] != s[j])break;
				else {
					++i;
					--j;
				}
			}
		}
		return i >= j;
	}
};

本代码提交AC，用时16MS。

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

---

把两个已排序数组合并成一个有序数组。注意是保存到nums1中。我一开始理解的是在合并过程中不能借助额外空间，所以用两个指针i,j指向两个数组，然后每次从nums2中找第一个小于nums1[i]的数，然后交换nums1[i]和nums2[j]，再调整nums2使有序。如此下去，nums1就是合并有序数组中的较小数组部分。
这个版本的完整代码如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        if (n == 0)
            return;
        int i = 0;
        while (i < m) {
            int j = 0;
            while (nums1[i] <= nums2[j] && i < m)
                i++;
            if (i >= m)
                break;
            swap(nums1[i], nums2[j]);
            while (j < n – 1 && nums2[j] > nums2[j + 1]) {
                swap(nums2[j], nums2[j + 1]);
                j++;
            }
            i++;
        }
        for (int j = 0; j < n; j++) {
            nums1[i++] = nums2[j];
        }
    }
};

本代码提交AC，用时6MS。但是只击败了15%的人，仔细看看算法实现，最坏复杂度是$O(n*m)$，因为如果nums1={6,7,8,9,10}，nums2={1,2,3,4,5}，则nums1[i]每和nums2[0]交换一次，nums2调整时都要交换n-1次，所以最坏复杂度是$O(n*m)$。所以应该还有更好的算法。
看题解，发现我没有很好利用nums1的数组大小至少是n+m这个信息，这说明合并之后的整个数组，最大下标只能是n+m-1，所以我们可以对nums1和nums2从后往前比较，把更大的元素依次在nums1[n+m-1]往前放，这样共3个指针，他们之间不会有overlap。此算法的复杂度只有$O(max(n,m))$。

完整代码如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        if (n == 0)
            return;
        int i = m – 1, j = n – 1, k = m + n – 1;
        while (i >= 0 || j >= 0) {
            int a = i >= 0 ? nums1[i] : INT_MIN;
            int b = j >= 0 ? nums2[j] : INT_MIN;
            if (a > b) {
                nums1[k–] = a;
                i–;
            }
            else {
                nums1[k–] = b;
                j–;
            }
        }
    }
};

本代码提交AC，用时3MS，果然快多了。

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.
  First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
• Could you come up with a one-pass algorithm using only constant space?

---

这道题有意思。实质是要把由0,1,2组成的数组从小到大排序，本来用计数排序，分别统计一下0,1,2这3个数字各有多少个，然后重新构造一个排好序的数组即可，但是Follow up里提到不能使用two-pass算法，并且只能使用常数空间复杂度。 我稍加思考，想到一个可行的算法。因为数组中只有3个数字，那么排好序的数组开头肯定是0（如果有0的话），结尾肯定是2（如果有2的话）。所以我们只需一遍遍历，遇到0则放到开头，遇到2则放到结尾，遇到1的话，就先统计一下1的数目。最后把1重新赋值到所有0的后面，1的个数在前面已经统计过了，所以正好。 完整代码如下：

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int p0 = 0, p2 = nums.size() – 1; // p0和p2分别代表下一个0和2应该填入的位置
        int n1 = 0; // 1的数量
        for (int i = 0; i <= p2; i++) {
            if (nums[i] == 0)
                nums[p0++] = nums[i];
            else if (nums[i] == 1)
                n1++;
            else {
                swap(nums[i], nums[p2]);
                p2–;
                i–;
            }
        }
        for (int i = 0; i < n1; i++)
            nums[p0++] = 1;
    }
};

本代码提交AC，用时3MS。

二刷。看评论区的题解，代码如下，zero和second分别表示可以下一个可以放0或者2的位置。i不断往前扫描，遇到2把它放末尾，遇到0把它放开头，如此不断swap之后，1都被扔到中间了。i最多进行了一次扫描。

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int zero = 0, second = nums.size() - 1;
        int i = 0;
        while (i <= second) {
            while (i < second && nums[i] == 2) {
                swap(nums[i], nums[second--]);
            }
            while (i > zero && nums[i] == 0) {
                swap(nums[i], nums[zero++]);
            }
            ++i;
        }
    }
};

本代码提交AC，用时6MS。

27. Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

---

要求我们把数组中等于某个数的元素全部“移除”，移除并不是真正的移除，可以把它们移到数组的末尾。

我的思路是，i指针从前往后扫，遇到一个等于val的（需要移除的）元素时，j从i+1开始找一个不等于val的，交换i,j指向的元素，i继续前进。
思路还是很简单，结果也正确，但是在计算新数组的长度时需要考虑较多cases，太麻烦，我就直接从末尾再往前找，直到找到一个不等于val的下标位置。ugly代码：

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        if (nums.size() == 0)
            return 0;
        if (nums.size() == 1)
            return (nums[0] != val) ? 1 : 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] != val) {
                        nums[i] = nums[j];
                        nums[j] = val;
                        break;
                    }
                }
            }
        }
        if (nums[0] == val)
            return 0;
        else {
            int i;
            for (i = nums.size() – 1; i >= 0; i–)
                if (nums[i] != val)
                    break;
            return i + 1;
        }
    }
};

本代码提交AC，用时4MS，排名倒数也是在我的预料之中的。看过题解之后，不得不感慨自己还是太笨，过段时间再来刷一遍。

二刷。这题其实很简单，也相当于快慢指针，快指针j一直走，如果nums[j]!=val，则把nums[j]赋值给nums[i]，同时i也往前走；如果nums[j]==val，则i要停下来，相当于i这个位置指示了可以放合法元素的位置。完整代码如下：

class Solution {
public:
	int removeElement(vector<int>& nums, int val) {
		int n = nums.size(), i = -1;
		for (int j = 0; j < n; ++j) {
			if (nums[j] != val)nums[++i] = nums[j];
		}
		return i + 1;
	}
};

本代码很简洁，提交AC，用时4MS。