1. 31 Next Permutation
   贴一个我不太明白的解法，相关的链接：https://leetcode.com/problems/next-permutation/discuss/13921/1-4-11-lines-C++

void nextPermutation(vector<int>& nums) {
    int i = nums.size() - 1, k = i;
    while (i > 0 && nums[i-1] >= nums[i])
        i--;
    for (int j=i; j<k; j++, k--)
        swap(nums[j], nums[k]);
    if (i > 0) {
        k = i--;
        while (nums[k] <= nums[i])
            k++;
        swap(nums[i], nums[k]);
    }
}

下面是我比较认可的解法：但是细节上还是容易出错，比如<=和>=的地方，i和j的初始化等等

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        // next_permutation(nums.begin(), nums.end());
        int size = nums.size();
        if(size == 0 || size == 1) return;
        for(int i = size - 2, j = size - 1; i >= 0; i--) if(nums[i + 1] > nums[i]){
            while(nums[j] <= nums[i]) j --;
            swap(nums[i], nums[j]);
            reverse(nums.begin() + i + 1, nums.end());
            return;
        }
        reverse(nums.begin(), nums.end());
    }
};

2. 33 Search in Rotated Sorted Array
3. 34 Find First and Last Position of Element in Sorted Array
   记录几个以后可能会经常用到的工具：
   lower_bound：时间复杂度为O(logn)返回第一个target，如果没有就返回第一个比target大的数字，如果所有的数字都比target小，会导致数组越界，使用时需要注意这一点。
   upper_bound：和lower_bound相似
   equal_bound：和上边两个类似。
   使用上边几个STL函数可以有下面两种：

vector<int> searchRange(vector<int>& nums, int target) {
    auto bounds = equal_range(nums.begin(), nums.end(), target);
    if (bounds.first == bounds.second)
        return {-1, -1};
    return {bounds.first - nums.begin(), bounds.second - nums.begin() - 1};
}

vector<int> searchRange(vector<int>& nums, int target) {
    int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    if (lo == nums.size() || nums[lo] != target)
        return {-1, -1};
    int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
    return {lo, hi};
}

但是，题目中的意思明显是要求使用二分法来求解，请慎重使用这些小工具。

4. 35 Search Insert Position
   思路：二分法
   需要注意的地方：end的初始化使用的是size - 1
   不过这个题目可以直接用lower_bound()来解。
   return lower_bound(nums.begin(), nums.end(), target) - nums.begin();

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        int mid;
        while(begin <= end){
            mid = begin + (end - begin) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) end = mid - 1;
            else begin = mid + 1;
        }
        return begin;
    }
};

5. 36 Valid Sudoku
   记录一种牛逼的方法：

public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            char number = board[i][j];
            if (number != '.')
                if (!seen.add(number + " in row " + i) ||
                    !seen.add(number + " in column " + j) ||
                    !seen.add(number + " in block " + i/3 + "-" + j/3))
                    return false;
        }
    }
    return true;
}

6. 38 Count and Say
   思路：注意细节就好
7. 39 Combination Sum
   思路：回溯backtracking
8. 40 Combination Sum II
   思路：回溯backtracking，注意重复的数字