题目1

题目链接
题目大意：
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 1e9
-109 <= target <= 1e9

题目解析：
两数之和、三数之和的类似问题，题目要求是要找到所有解。
由于题目对数组元素顺序没有要求，可以先对数组排序，得到从小到大的数组nums；
枚举两个元素a和b，作为四元组的两个元素；剩下两个元素在区间[a, b]中选择。
问题变成了，在区间找到两个数字c和d，并且c+d=target-a-b。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        map<vector<int>, int> h;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 3; j < n; ++j) {
                int m = target - nums[i] - nums[j];
                int left = i + 1, right = j - 1;
                while (left < right) {
                    if (nums[left] + nums[right] == m) {
                        vector<int> tmp = {nums[i], nums[j], nums[left], nums[right]};
                        sort(tmp.begin(), tmp.end());
                        if (!h[tmp]) {
                            ret.push_back(tmp);
                            h[tmp] = 1;
                        }
                        ++left;
                    }
                    else if (nums[left] + nums[right] > m) {
                        --right;
                    }
                    else {
                        ++left;
                    }
                }
            }
        }
        
        return ret;
    }
}ac;

题目2

题目链接
题目大意：
给出一个整数数组nums，数组里每个数字各不相同；
数组原来是以递增的顺序排列如[0,1,2,4,5,6,7]，经过变换后，从某个位置开始的元素挪到了数组后半部分，如[4,5,6,7,0,1,2]；
现在给出变换后的数组nums和某个数字target，问target在数组中的索引，如果不存在则输出-1；
要求时间复杂度在O(logN)的级别；

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

题目解析：
在一个有序的数组，查找某个数字的索引，可以通过二分法的方式快速定位；
题目的难点在于数组经过变换后，失去了完整的有序信息；
如果把变换后的数组，用二维坐标系的方式表达，会是是如下的结果：

在两段线段内部，可以使用二分查找。
这里可以用增量查询的方式来定位分段的位置，比如说当前的位置是index；
如果nums[index]<nums[index+1]，我们可以认为[index, index+1]是在同一段；
并且如果1满足，则尝试index+1+2，再尝试index+1+2+4，直到不满足之前的条件，则怎么跨段了，此时降级从index+1开始计算；

对于某一段[index, index+k]，我们通过上诉的方法判断得到是同一段，接下来在这一段里面查找target；
如果target<num[index] 或者 target > num[index+k]，则肯定不在这一段，可以跳过；
如果是其他条件，则同样降级到index+1；

通过这个方法，可以快速定位到target，并且速度非常快！

target < nums[index] 是很重要的剪枝，否则当target在数组中不存在时，很容易降级为O(N)的算法。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return look(nums, target, 0, 1);
    }
    
    int look(vector<int>& nums, int target, int index, int gap) {
        if (index >= nums.size()) {
            return -1;
        }
        if (nums[index] == target) {
            return index;
        }
        if (index + gap < nums.size() && nums[index + gap] > nums[index] && (nums[index + gap] < target || target < nums[index])) {
            return look(nums, target, index + gap, gap * 2);
        }
        else {
            return look(nums, target, index + 1, 1);
        }
    }
    
}leetcode;

题目3

题目链接
题目大意：
给出一个递增的整数数组nums，求某个整数target在数组的区域，如下：

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

题目解析：
二分法，给出整数target，可以比较快速找出分别找出左边界，同理找到右边界即可。
时间复杂度：O（ log N）

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ret;
        
        int left = 0, right = (int)nums.size() - 1;
        int index = -1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                index = mid;
                right = mid - 1;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        ret.push_back(index);
        
        if (index == -1) {
            ret.push_back(-1);
            return ret;
        }
        
        
        left = 0, right = (int)nums.size() - 1;
        index = -1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                index = mid;
                left = mid + 1;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        
        ret.push_back(index);
        
        return ret;
    }
}leetcode;

题目4

题目链接
题目大意：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

题目解析：
经典二分查找，如果数组中有可以直接查找出来。
附加要求，如果数组不存在返回将被插入的位置，这个刚好就是二分的left的位置。

意外发现某个题解
和自己代码一模一样，标点符合和命名都完全一样。

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

题目5

题目链接
题目大意：
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

示例 1:

输入: 1
输出: "1"
解释：这是一个基本样例。
示例 2:

输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。

题目解析：
按照题目的要求，统计连续的数字数量，然后用sprintf转成字符串，再记录下来。

class Solution {
    vector<string> ans;
public:
    string countAndSay(int n) {
        if (!ans.size()) {
            string s = "1";
            ans.push_back(s);
            for (int i = 1; i < 30; ++i) {
                int cnt = 1;
                string strNew;
                for (int j = 1; j < s.length(); ++j) {
                    if (s[j] == s[j - 1]) {
                        ++cnt;
                    }
                    else {
                        char tmp[11];
                        sprintf(tmp, "%d%c", cnt, s[j - 1]);
                        cnt = 1;
                        strNew.append(tmp, strlen(tmp));
                    }
                }
                char tmp[11];
                sprintf(tmp, "%d%c", cnt, s.back());
                strNew.append(tmp, strlen(tmp));
                s = strNew;
                ans.push_back(s);
            }
        }
        return ans[n-1];
    }
}lt;