程序员进阶之算法练习（八十四）
题目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;
