两数之和
解题思路：哈希表
使用哈希表解题,判断hash表中是否有对应数字
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mymap;
for(int i = 0; i < nums.size(); i++){
if(mymap.count(target-nums[i]) > 0){
return {mymap[target-nums[i]], i};
}else{
mymap.insert(pair<int, int>(nums[i], i));
}
}
return {};
}小结: 熟悉unordered_map常用用法，使用count判断键有无，使用insert插入键值对，使用[键]访问值。
寻找两个正序数组的中位数
解题思路：二分法
寻找中位数可以归纳为寻找第k小的数。每次可以排除k/2位数。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}盛最多水的容器
解题思路:双指针
在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为
此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由两个指针指向的数字中较小值 * 指针之间的距离决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size() - 1;
int maxArea = 0;
int area;
while(i < j){
area = min(height[i], height[j]) * (j - i);
maxArea = max(area, maxArea);
if(height[i] > height[j]){
j--;
}else{
i++;
}
}
return maxArea;
}
};小结: 双指针法，遍历所有可能是最大值得选项，找出最大值。
三数之和
解题思路: 排序 + 双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size() < 3){
return result;
}
sort(nums.begin(), nums.end());
int third;
int target;
for(int first = 0; first < nums.size() - 2; first++){
if(first != 0 && nums[first] == nums[first-1]){
continue;
}
third = nums.size() - 1;
for(int second = first + 1; second < nums.size() - 1; second++){
if(second != first + 1 && nums[second] == nums[second - 1]){
continue;
}
target = 0 - nums[first] - nums[second];
while(third > second && nums[third] > target){
third--;
}
if(third != second && nums[third] == target){
vector<int> tmp = {nums[first], nums[second], nums[third]};
result.push_back(tmp);
}
}
}
return result;
}
};删除排序数组中的重复项
解题：快慢指针
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
int i = 0;
for(int j = 1; j < nums.size(); j++){
if(nums[i] != nums[j]){
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
};下一个排列
算法推导
如何得到这样的排列顺序？这是本文的重点。我们可以这样来分析：
我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
在尽可能靠右的低位进行交换，需要从后向前查找
将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列
以上就是求“下一个排列”的分析过程。
算法过程
标准的“下一个排列”算法可以描述为：
从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
将 A[i] 与 A[k] 交换
可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
该方法支持数据重复，且在 C++ STL 中被采用。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(nums.size() <= 1){
return;
}
int i =nums.size() - 2, j = nums.size() - 1, k = nums.size() - 1;
while(i >= 0 && nums[i] >= nums[j]){
i--;
j--;
}
int tmp;
if(i >= 0){
while(nums[k] <= nums[i]){
k--;
}
tmp = nums[k];
nums[k] = nums[i];
nums[i] = tmp;
}
int end = nums.size() - 1;
for(; j < end; j++, end--){
tmp = nums[j];
nums[j] = nums[end];
nums[end] = tmp;
}
return;
}
};搜索旋转排序数组
和一般二分法不同，通常二分法是nums[mid]和target比较,此题使用nums[low]与target比较。
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size() == 0) return -1;
int low = 0, high = nums.size() - 1;
int mid;
while(low <= high){
mid = (low + high) / 2;
if(nums[mid] == target){
return mid;
}
if(nums[mid] >= nums[low]){
if(target >= nums[low] && target < nums[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}else{
if (nums[mid] < target && target <= nums[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}
};合并区间
排序+双指针
class Solution {
public:
static bool comp(vector<int> First, vector<int> Second){
return First[0] < Second[0];
}
//把<改为 <=后无法通过
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if(intervals.empty()){
return result;
}
sort(intervals.begin(), intervals.end(), comp);
int low = intervals[0][0], high = intervals[0][1];
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] <= high){
high = max(high, intervals[i][1]);
}else{
result.push_back(vector<int>{low, high});
low = intervals[i][0];
high = intervals[i][1];
}
}
result.push_back(vector<int>{low, high});
return result;
}
};
京公网安备 11010502036488号