算法

二分查找

cpp复制

1bool isgreed(int num, int target) {2 return num> target;3}4int binaryserach(vector<int>&num, int r,int target) {5 int i =-1,mid;6 while (r - i > 1) {7 mid = i + (r -i) / 2;//相当于(1+r)/2,防止数据溢出8 if (isgreed(num[mid], target))9 r= mid;10 else i = mid;11 1213 }14 if(r==num.size())15 cout<<"未找到，返回数组长度"<<endl;16 return r;1718}

收起

找大于x的第一个数，return val>x;

找大于等于x的第一个数，return val>=x;

找小于x的第一个数（相当于找大于等于x-1的第一个数），return val>=x return r-1;

找小于等于x的第一个数（相当于找大于x-1的第一个数），return val>x return r-1;

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

思路：

两个数组是有序，那么合成后的数组的前一半是由两个数组各自前一半的部分组成

如果分别把两个数组分为两半，各自找出左右两边的最小值和最大值，就可算出 分别用两个变量去记录两个数组各自的分成两部分后的最大和最小值

把两个数组切成左右两部分，让左边所有数都小于等于右边所有数。

cpp复制

1from typing import List23class Solution:4 def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:5 # 保证 nums1 是较短的数组6 if len(nums1) > len(nums2):7 nums1, nums2 = nums2, nums189 m = len(nums1)10 n = len(nums2)1112 left = 013 right = m1415 while left <= right:16 i = (left + right) // 217 j = (m + n + 1) // 2 - i #总长度为奇数时左边最大值为中位数1819 nums1_left = float("-inf") if i == 0 else nums1[i - 1]20 nums1_right = float("inf") if i == m else nums1[i]2122 nums2_left = float("-inf") if j == 0 else nums2[j - 1]23 nums2_right = float("inf") if j == n else nums2[j]2425 if nums1_left <= nums2_right and nums2_left <= nums1_right:26 if (m + n) % 2 == 1:27 return max(nums1_left, nums2_left)28 else:29 return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 23031 elif nums1_left > nums2_right:32 right = i - 133 else:34 left = i + 1

收起

双向指针

接雨水

python复制

1def maxrain(arr):2 left = 03 right = len(arr) - 145 left_max = 06 right_max = 07 water = 089 while left < right:10 if arr[left] < arr[right]:11 if arr[left] >= left_max:12 left_max = arr[left]13 else:14 water += left_max - arr[left]1516 left += 11718 else:19 if arr[right] >= right_max:20 right_max = arr[right]21 else:22 water += right_max - arr[right]2324 right -= 12526 return water272829arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]30print(maxrain(arr))

收起

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j 、 i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

三数之和

cpp复制

1 vector<vector<int>> threeSum(vector<int>& nums) {2 sort(nums.begin(), nums.end());3 vector<vector<int>> v;45 for (int i = 0; i < nums.size() - 2; ++i) {6 if (nums[i] > 0) break;7 if (i > 0 && nums[i] == nums[i - 1]) continue;89 int left = i + 1, right = nums.size() - 1;1011 while (left < right) {12 int sum = nums[i] + nums[left] + nums[right];1314 if (sum == 0) {15 v.push_back({nums[i], nums[left], nums[right]});16 while (left < right && nums[left] == nums[left + 1]) left++;17 while (left < right && nums[right] == nums[right - 1]) right--;18 left++;19 right--;20 } else if (sum > 0) {21 right--;22 } else {23 left++;24 }25 }26 }2728 return v;29}

收起

1.相当于要求i<j<k;

2.要去重

3.定一个元素后，本质是用双向指针求两数之和，所以要先排序

python复制

1def threeSum(arr):2 arr.sort()3 res = []45 for i in range(len(arr) - 2):6 # 如果固定的数已经大于 0，后面更大，不可能和为 07 if arr[i] > 0:8 break910 # 去重：跳过重复的固定数11 if i > 0 and arr[i] == arr[i - 1]:12 continue1314 left = i + 115 right = len(arr) - 11617 while left < right:18 total = arr[i] + arr[left] + arr[right]1920 if total == 0:21 res.append([arr[i], arr[left], arr[right]])2223 # 去重 left24 while left < right and arr[left] == arr[left + 1]:25 left += 12627 # 去重 right28 while left < right and arr[right] == arr[right - 1]:29 right -= 13031 # 找到一组后，两边都要移动32 left += 133 right -= 13435 elif total > 0:36 right -= 137 else:38 left += 13940 return res

收起

盛最多水的容器

给你一个长度为 n 的整数数组 height 。 有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

要不要我把这题标准双指针代码（最精简、不出错版）直接给你？11. 盛最多水的容器

给你一个长度为 n 的整数数组 height 。 有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

i

cpp复制

1nt areasum(vector<int>&arr) {2 if (arr.size() < 2)return 0;3 int left = 0, right = arr.size()-1;4 int length = min(arr[left],arr[right]);5 int area = length * (right - left);6 while (left < right) {7 if (arr[left] > arr[right])8 right--;9 else left++;10 length= min(arr[left], arr[right]);11 area = max(area, length * (right - left));12 }13 return area;14}

收起

谁的高度低就移动谁的指针

用哈希表求两数之和

1.求两数之和

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

1.先存后查

问题：会出现自匹配，因为原来数组和哈希表中元素相同，元素重复，要加判断

cpp复制

1auto it=mp.find(need);23it->second!=i

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int,int>mp;

for(int i=0;i<nums.size();i++)

mp[nums[i]]=i;

for(int i=0;i<nums.size();i++){

​ int need=target-nums[i];

​ auto it=mp.find(need);

​ if(it!=mp.end()&&it->second!=i)

​ return {it->second,i};

}

return {};

}

算法通过值去找键，所以数据的值要放在哈希表中的first,键在second；

即通过a去找b，a在first,b在second；

边存边查

不会出现自匹配问题

疑问：该算法是先查后存，如果查的时候需要的need还没有存进来怎么办

答：两数之和一前一后，例如求7=2+5，开始时2错过了但存进了哈希表，num[i]=5是自然找到了2

cpp复制

1vector<int> twoSum(vector<int>& nums, int target) {23 unordered_map<int,int>mp;45 for(int i=0;i<nums.size();i++){67​ int need=target-nums[i];89​ if(mp.find(need)!=mp.end())1011​ return {mp[need],i};1213​ mp[nums[i]]=i;1415 }1617 return {};1819 }

收起

关于map容器：

find（）：找到元素后，指针指向对应位置的键值；否则指向mp.end()

count（）：找到返回1；否为0

两数相加

cpp复制

1lsit * addtwosum(list *l1,list* l2){2 list *h=new list(0);3 h->next=nullptr;4 int carry=0;5 while(l1 || l2 ||carry!=0){6 int val1 = l1 ? l1->val : 0;7 int val2 = l2 ? l2->val : 0;8 //如果 l1 这个指针不为空（还有节点），就取它的值；如果 l1 为空（遍历完了），就当它的值是 09 int sum=l1->val1+l2->val2+carry;10 int cur=sum%10;11 carry=sum/10;12 list *p=new list(cur);13 p->next=h->next;14 h->next=p;15 if(l1)l1=l1->next;16 if(l2)l2=l2->next;17 }18return h->next;192021

收起

滑动窗口

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

text复制

1class Solution {23public:45 int lengthOfLongestSubstring(string s) {67​ int left=0;89​ int right=0;1011​ int length=0;1213​ unordered_map<char,int> m;1415​ for(right=0;right<s.size();right++){1617​ char c=s[right];1819​ auto it=m.find(c);2021​ if(it!=m.end()&&m[c]>=left){22//m[c]>=left判断该重复字符串是否出现在滑动窗口内，即判断历史重复2324​ left=m[c]+1;25 // 更新（或插入）字符 c 的最新位置26​ m[c]=right;2728​ length=max(length,right-left+1);2930​ }3132​ return length;3334 }3536};

收起

排序

选择排序 (Selection Sort)

算法思想：

• 第1轮：在 [0~n-1] 中找最小元素，与 arr[0] 交换

• 第2轮：在 [1~n-1] 中找最小元素，与 arr[1] 交换

• 以此类推...

• 每次内层循环找到最小值的下标

• 如果最小值不在正确位置则交换

cpp复制

1void selectionSort(std::vector<int> &arr){2 int n=arr.size();3 for(int i=0;i<n-1;i++){4 int minIndex=i;5 for(int j=i+1;j<n;j++){6 if(arr[j]<arr[minIndex])7 minIndex=j;8 }9 if(minIndex!=i)10 std::swap(arr[i],arr[minIndex]);11 }12}

双向选择排序

cpp复制

12//双向选择排序3void selectSorrt(vector<int> &arr){4 int left=0;5 int n=arr.size();6 int right=n-1;7 8 while(left<right){9 int minInx=left;10 int maxInx=right;11 for(int i=left;i<=right;++i){12 if(arr[i]<arr[minInx])13 minInx=i;14 if(arr[i]>arr[maxInx])15 maxInx=i;16 swap(arr[left],arr[minInx]);17 if(maxInx==left)18 maxInx=minInx;19 swap(arr[right],arr[maxInx]);20 }21 ++left;22 --right;23 }24}

收起

堆排序

cpp复制

1//调整大根堆2void MaxHeapify(vector<int> &arr,int n,int i){3 int largest=i;4 int left=2*i+1;5 int right=2*i+2;6 if(left<n&&arr[left]>arr[largest])7 largest=left;8 if(right<n&&arr[right]>arr[largest])9 largest=right;10 if(largest!=i){11 swap(arr[i], arr[largest]);12 MaxHeapify(arr,n,largest);13 }14}1516//循环写法17void MaxHeapify(vector<int> &arr,int n,int i){18 while(true){19 int largest=i;20 int left=2*i+1;21 int right=2*i+2;22 if(left<n&&arr[left]>arr[largest])23 largest=left;24 if(right<n&&arr[right]>arr[largest])25 largest=right;26 if(largest==i)break;27 swap(arr[i], arr[largest]);28 i=largest;29 }30}31//堆排序32void heapSort(vector<int>& arr){33 int n=arr.size();34 //从最后一个非叶节点开始建堆35 for(int i=n/2-1;i>=0;i--){36 MaxHeapify(arr,n,i);37 }38 for(int i=n-1;i>0;i--){39 swap(arr[i],arr[0]);//依次把最大值放到末尾40 MaxHeapify(arr,i,0);//重新调整堆41 }42}

收起

插入排序 (Insertion Sort)

算法思想：

• 第1个元素天然有序
• 从第2个元素开始，把每个元素插入到前面已排序序列的合适位置
• 插入时从后往前比较，大于 temp 的元素依次后移

cpp复制

1void insertionSort(std::vector<int> &arr){2 int n=arr.size();3 for(int i=1;i<n;i++){4 int temp=arr[i];5 int j=i-1;6 while(j>=0&&arr[j]>temp){7 arr[j+1]=arr[j];8 j--;9 }10 arr[j+1]=temp;11 }12}

希尔排序

1. 分组 把数组按一定间隔分成多个子数组。比如 gap=5，就把第1个、第6个、第11个...分成一组。

2. 对每个子数组插入排序 每组内部排好序，此时数组局部变得有序。

3. 缩小步长 gap 变小（变成3），重新分组，再插入排序。

4. 重复 直到 gap=1，变成普通的插入排序，但此时数组已经基本有序，交换次数很少。

cpp复制

1void shellSort(std::vector<int> &arr){2 int n=arr.size();3 for(int gap=n/2;gap>0;gap/=2){4 for(int i=gap;i<n;i++){5 int temp=arr[i];6 int j=i;7 while(j>=gap&&arr[j-gap]>temp){8 arr[j]=arr[j-gap];9 j-=gap;10 }11 arr[j]=temp;12 }13 }14}

收起

快速排序

思路：

选一个基准值，把数组分为两边

左边的值比基准小，右边的值比基准大，然后递归左边和右边

时间复杂度：

text复制

1平均：O(n log n)O(n log n)2最坏：O(n²)

cpp复制

1#include<iostream>2#include<vector>3using namespace std;4int partition(vector<int> &arr,int low,int high){5 int povit=arr[high];//定基准，把数组分为大于基准和小于基准6 int i=low-1;//小于基准的最后下标7 //如果当前元素比基准小，就把它放到左边区域。8 for(int j=low;j<high;j++){9 if(arr[j]<povit){10 ++i;11 swap(arr[i],arr[j]);12 }13 }14 swap(arr[high],arr[i+1]);15 return i+1;16/*17 int povit=arr[low];18 int j=high+1;19 for(int i=high;i>low;--i){20 if(arr[i]<povit){21 j--；22 swap(arr[i],arr[j]);23 }24 swap(arr[low],arr[j-1]);25 return j-1;26 }27*/28}29void QuickSort(vector<int> &arr,int low,int high){30 if(low<high){31 int pi=partition(arr,low,high);32 QuickSort(arr,low,pi-1);33 QuickSort(arr,pi+1,high);34 }35}36

收起

python复制

1def quick_sort(arr):2 # 递归终止条件：数组长度为 0 或 1，天然有序3 if len(arr) <= 1:4 return arr56 # 选择第一个元素作为基准值7 pivot = arr[0]89 # 比 pivot 小的元素10 left = []1112 # 比 pivot 大或等于 pivot 的元素13 right = [] 1415 # 从第二个元素开始遍历16 for x in arr[1:]:17 if x < pivot:18 left.append(x)19 else:20 right.append(x)2122 # 递归排序左边和右边23 return quick_sort(left) + [pivot] + quick_sort(right)242526nums = [5, 2, 7, 1, 9, 3]27result = quick_sort(nums)2829print(result)

收起

树

层序遍历

cpp复制

1#include<iostream>2#include<vector>3#include<queue>4using namespace std;5typedef struct TreeNode6{7 TreeNode *left;8 TreeNode *right;9 int val;10 TreeNode():left(nullptr),right(nullptr),val(0){}11}*list;1213vector<int> cenOrder(list root){14 vector<int> v;15 queue<list> q;16 q.emplace(root);17 while(!q.empty()){18 list cur=q.front();19 q.pop();20 v.emplace_back(cur->val);21 if(cur->left)q.emplace(cur->left);22 if(cur->right)q.emplace(cur->right);23 }24 return v;25}2627vector<vector<int>> cenOrders(list root){28 vector<vector<int>> res;29 queue<list> q;30 q.emplace(root);31 while(!q.empty()){32 int n=q.size();33 vector<int> v;34 for(int i=0;i<n;i++){35 list cur=q.front();36 q.pop();37 v.emplace_back(cur->val);38 if(cur->left) q.push(cur->left);39 if(cur->right) q.push(cur->right);40 }41 res.emplace_back(v);42 }43 return res;44}

收起

前序和中序的迭代写法

cpp复制

12typedef struct TreeNode3{4 TreeNode *left;5 TreeNode *right;6 int val;7 TreeNode():left(nullptr),right(nullptr),val(0){}8}*list;9void PrevOreder(list root){10 list cur=root;11 stack<list> stc;12 while(!cur ||!stc.empty()){13 while(cur){14 cout<<cur->val<<endl;15 stc.emplace(cur);16 cur=cur->left;17 }18 cur=stc.top();19 stc.pop();20 cur=cur->right;21 }22}23void inOrder(list root){24 list cur=root;25 stack<list> stc;26 while(!cur ||!stc.empty()){27 while(cur){28 stc.emplace(cur);29 cur=cur->left;30 }31 cur=stc.top();32 stc.pop();33 cout<<cur->val<<endl;34 cur=cur->right;35 }36}

收起

两个鸡蛋 / 两个易碎小球测楼层问题

有一栋楼 n 层，有两个一模一样的小球。 从某一层往下扔，如果碎了，说明这一层太高；如果没碎，说明这一层及以下都安全。 要找出“小球不碎的最高楼层”。

思路：

假设我们希望最坏最多测试 x 次。

第一次从第 x 层扔。

如果第一次就碎了：

text复制

1第一个球：测第 x 层，碎了2第二个球：从 1 层测到 x - 1 层

最多次数是：

text复制

11 + (x - 1) = x

所以第一次最多可以跳 x 层。

---

如果第一次没碎，就已经用掉了 1 次。

剩余次数只剩：

text复制

1x - 1 次

所以第二次不能再跳 x 层，只能跳 x - 1 层。

第二次楼层就是：

text复制

1x + (x - 1)

如果第二次碎了，答案在：

text复制

1x + 1 到 x + (x - 1) - 1

中间最多有 x - 2 层要用第二个球测。

总次数：

text复制

1第一次没碎：1 次2第二次碎：1 次3第二个球线性测：x - 2 次45总共 = 1 + 1 + (x - 2) = x

所以第二次跳 x - 1 层刚刚好。

---

2. 第三次为什么跳 x - 2？

如果前两次都没碎，说明已经用了 2 次。

剩余次数：

text复制

1x - 2 次

所以第三次最多只能跳 x - 2 层。

第三次楼层是：

text复制

1x + (x - 1) + (x - 2)

如果第三次碎了，第二个球还要在线性区间里测，最多测 x - 3 次。

总次数：

text复制

1前两次没碎：2 次2第三次碎：1 次3第二个球线性测：x - 3 次45总共 = 2 + 1 + (x - 3) = x

---

3. 所以每次跳的层数就是

text复制

1x, x - 1, x - 2, x - 3, ..., 1

这是一个等差数列。

第一个球测试的楼层是这些跳跃距离的累加：

text复制

1第1次：x2第2次：x + (x - 1)3第3次：x + (x - 1) + (x - 2)4第4次：x + (x - 1) + (x - 2) + (x - 3)5...

要覆盖 n 层楼，就要求：

text复制

1x + (x - 1) + (x - 2) + ... + 1 >= n

这就是等差数列求和：

text复制

1x * (x + 1) / 2 >= n

程序思路：

先找出最小实验的次数

第一个球：

一个变量记录上一次测试的楼层，一个变量记录当前记录的楼层，一个变量记录步长

如果球在当前层碎了，就开始第二个球

如果没用碎了，步长减一，继续循环

第二个球：

遍历上一次和第一个球碎了之间的楼层

python复制

1def find_max_safe_floor(n, safe_floor):2 def broken(floor):3 return floor > safe_floor45 # 找到最小的 x，使得 x + (x-1) + ... + 1 >= n6 x = 17 while x * (x + 1) // 2 < n:8 x += 1910 prev = 011 cur = 012 step = x1314 # 第一个球：按 x, x-1, x-2 ... 的间隔往上测15 while cur < n:16 prev = cur17 cur += step1819 if cur > n:20 cur = n2122 print(f"第一个球测试第 {cur} 层")2324 if broken(cur):25 print(f"第一个球在第 {cur} 层碎了")26 break27 else:28 print(f"第一个球在第 {cur} 层没碎")2930 step -= 13132 # 如果最高层都没碎33 if cur == n and not broken(cur):34 return n3536 # 第二个球：从上一次没碎的下一层开始逐层测37 for floor in range(prev + 1, cur):38 print(f"第二个球测试第 {floor} 层")3940 if broken(floor):41 print(f"第二个球在第 {floor} 层碎了")42 return floor - 143 else:44 print(f"第二个球在第 {floor} 层没碎")4546 return cur - 1474849print("最大不碎楼层是：", find_max_safe_floor(100, 20))

收起