明天程序设计需要打印的 代码总结

1.快慢指针

经典题目--

T1-删除排序数组中的重复项: 

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

代码如下：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int fast=1;int slow=1;for(fast=1;fast<=nums.size()-1;fast++){if(nums[fast]!=nums[fast-1])//由于是升序排列 所以数组 重复元素是在一起的{nums[slow++]=nums[fast];}}return slow;}
};

2.对撞指针:

T1-两数之和 II - 输入有序数组

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

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

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

代码如下：

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {//和 上机课的 那个 平方之和的 数 --思路完全一样，都是采用对撞指针vector<int> answer;int front=0;//理解有误--其实 他说的 是 返回的 时候 返回从1开始的 下标int back=numbers.size()-1;int sum=0;while(front!=back){sum=numbers[front]+numbers[back];//1.if(sum==target){return {front+1,back+1};}//2.elsesum>target?back--:front++;}return {};}
};

3.滑动窗口:

T1-长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

代码如下：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {//滑动窗口的思想--左右边界值--定一动一int left=0,right=-1;int min_len=nums.size()+1;int sum=0;while(left<nums.size())//左边界不出界{//1.如果sum小于target且right+1未出界--把right+1位置的值加上if(sum<target&&right+1<nums.size()){sum+=nums[++right];}else{//(1)若right出界那么利用if可以让后续left也出界//(2)如果时sum大于等于target，那么一致减小到最小sum-=nums[left++];}//更新min_len的值if(sum>=target){min_len=min(right-left+1,min_len);}}if(min_len==nums.size()+1)return 0;else return min_len;}
};

4.归并排序:

T1：利用 “归并排序” 对 1个单向链表 进行 排序:

<1> -----关键：

（1）merge_sort函数 : 递归 函数--出口，直到只有1个 或者 0个 元素为止，直接返回这个节点，作用就是 链表 分成 2半， 

(2)merge_sort函数中：因为是链表，所以需要 利用 fast ，slow快慢指针 找到中间位置，然后分别找到 left链表 和 right链表的 头节点（注意把 left链表的 尾节点 设置为 NULL）

(3)merge函数：不需要用递归 实现 ，直接用while循环即可， 直到其中有一个指针为NULL，最后接上剩下的 那个链表（等价于上课 讲到的 2个有序 链表的 合并）

<2>--------代码如下:

/* Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
//其中 一些 注释 用于之前的 调试，因为 函数体里面的 临时指针很容易被 销毁掉
class Solution {
public://利用 归并排序加以实现:ListNode* sortList(ListNode* head) {head=merge_sort(head);return head;}ListNode* merge_sort(ListNode* head){//出口 ，head长度为1 或 0 直接返回if(head == nullptr || head->next==nullptr){return head;}//(1)利用 快慢指针 找到中间位置ListNode* fast=new ListNode(0);ListNode* slow=new ListNode(0);fast=head->next; //这种链表没有头节点，每个节点都有valslow=head;//fast 每次移动2格 ， slow移动一格while(fast!= NULL && fast->next!=NULL){fast=fast->next->next;slow=slow->next;}//(2)此时slow指向的位置就是向下取整的中间位置//递归，直到1个元素 或0 个元素ListNode* right=new ListNode(0);ListNode* left=new ListNode(0);right=merge_sort(slow->next); //右边链表的起点slow->next=NULL; //左边链表的尾部 置NULLleft=merge_sort(head);head=merge(left,right);//尝试 添加一个新的 堆区空间ListNode* ans=new ListNode(0);ans=head;//show(ans);return ans; //head这个指针式传递进来的，可以返回，不是临时变量}//输出 函数void show(ListNode* node){while(node!=NULL){cout<<node->val<<endl;node=node->next;}}ListNode* merge(ListNode* left,ListNode* right){//cout<<"left:"<<left->val<<"right:"<<right->val<<"merge一下"<<endl;//既然传递进来的 left 和 right都是 有序的 ，相当于 上课讲的链表merge合并ListNode* root_ =new ListNode(0);//堆区，防止销毁临时变量ListNode* root=new ListNode(0);root=root_;root->next=NULL;while(left!=NULL && right!=NULL){if(left->val < right->val){//left先进root->next= left;root=root->next;left=left->next;}else{//right进root->next=right;root=root->next;right=right->next;}}//(2)处理 剩余的 节点if(left!=NULL){//左边非空root->next=left;}else if(right != NULL){root->next= right;}return root_->next;}
};

T2:对2个有序的数组进行归并:

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

代码如下：

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {//利用尾插法--从最后的位置开始 交替防止--不会产生遮掩问题int p1=m-1;int p2=n-1;int cur=m+n-1;while(p1>=0&&p2>=0){if(nums1[p1]>=nums2[p2]){nums1[cur--]=nums1[p1--];}else{nums1[cur--]=nums2[p2--];}}while(p1>=0){nums1[cur--]=nums1[p1--];}while(p2>=0){nums1[cur--]=nums2[p2--];}}
};

5.数组中的第k个最大的元素--小根堆

T1-数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

代码如下：

法一：直接sort，然后取出倒数第k个元素即可

法二：改进 大根堆排序

class Solution {
public:
//1.小的大根堆 的 构建函数void max_heapify(vector<int> &arr,int start,int end){//(1)先 初始化 dad节点的 下标，和 son节点的 下标int dad=start;int son=dad*2+1;//(2 然后利用循环进行 小的堆的构建while(son<=end){//判断：找出 两个子节点中大的哪一个if(son+1<=end&&arr[son]<arr[son+1]){son++;}//判断：dad节点的元素是否已经 比 两个子节点 元素大--直接returnif(arr[dad]>=arr[son]){return ;}else{//说明需要进行交换--同时，还要考虑是否--影响 已经构架好的 对结构swap(arr[dad],arr[son]);dad=son;son=dad*2+1;}}}//2.改进的 堆排序函数--算了，直接放到里面int findKthLargest(vector<int>& nums, int k) {//思路：（1）先构建一个大根堆//(2)在进行堆排序的 过程中，只需要选出 第k大的 就可以了，改进了//(1)int len=nums.size();for(int i=len/2-1;i>=0;i--){max_heapify(nums,i,len-1);}//(2)for(int i=len-1;i>=len-k;i--){swap(nums[0],nums[i]);max_heapify(nums,0,i-1);}//nice真不错--漂亮return nums[len-k];}
};

6.二分查找:

T1－猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

代码如下：

/ * Forward declaration of guess API.* @param  num   your guess* @return 	     -1 if num is higher than the picked number*			      1 if num is lower than the picked number*               otherwise return 0* int guess(int num);*/class Solution {
public:int guessNumber(int n) {//利用二分搜索，每次返回中间的数值mid，然后依次二分数值区间long long left = 1;long long right =n;long long mid = (right + left)/2;while(right>=left){mid = (right + left)/2;if(guess(mid) == 0){return mid;}else if(guess(mid) == -1){//right 有边界变为 mid-1right = mid-1;}else{left = mid+1;}}return mid;}
};

7.bfs--广搜:

T1-打开旋转锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

代码如下：

class Solution {
public://一下借鉴他人的答案：--双向 BFS方法//1.初始设置:string s,t;unordered_set<string> st;//作为deadends的禁忌表//2.主函数--调用一次bfs函数int openLock(vector<string>& deadends, string target) {s="0000";t=target;if(s==t) return 0;for(const auto& d: deadends)st.insert(d);                      //设置好禁忌表if(st.count(s)) return -1;int ans=bfs();return ans;                       //关键在于调用bfs}//3.bfs函数int bfs(){//(1)初始化两个队列，用于存放上一次加入队列的 状态queue<string> d1,d2;   //d1从s出发，d2从target出发//(2)利用哈希表记录已经搜索过的点----避免无限循环！！！--妙unordered_map<string,int> m1,m2;    //示例："{"1000",1}代表1000这个状态最先由1次变换得到"//(3)d1，从s开始，d2从target开始--双向bfsd1.push(s);m1[s]=0;d2.push(t);m2[t]=0;//(4)只要两个队列都不为空，就继续搜索，直到所有的状态都已经被搜索一遍while(d1.size()&&d2.size()){int time=-1;//作为 转换的次数if(d1.size()<=d2.size()){//从较小的队列开始搜索--节约时间time=update(d1,m1,m2);}else time=update(d2,m2,m1);//前一个是己方遍历过的哈希表， 后一个是 对方遍历过的哈希表if(time!=-1) return time;//只要第一次找到直接返回}return -1;//只要一方空了，说明没有可能了}//4.定义update函数 --用于向不同方向更新int update(queue<string>& q,unordered_map<string,int>& cur,unordered_map<string,int>& other){//(1)取出队列中的第一个元素，并且从队列中删除string t=q.front();q.pop(); //局部变量--遮盖全局变量int step=cur[t];//保留这个元素 经过多少次转换得到//(2)8种处理for(int i=0;i<4;i++){for(int j=-1;j<=1;j++){//跳过0if(j==0) continue;//得到变换结果int origin=t[i]-'0';int next=(origin+j)%10;if(next==-1) next=9;//特殊string copy=t;//保留原本，处理copy副本copy[i]='0'+next;//(3)判断 下一步怎么走if(st.count(copy)||cur.count(copy)) continue; //已经 搜索过， 或者在禁忌表中if(other.count(copy)) return step+1+other[copy];//找到了，返回 汇合步数else{//都不是--入队--最后一个位置q.push(copy);cur[copy]=step+1;}}}//这一轮的8个房间 搜索对象没有找到 返回-1return -1;}
}; //带思考--只要一方空了，就可以 否定其他可能了？？why
//答：（1）这种双向 bfs是为了加快 搜索速度；
//     (2)比如说：d1空了，说明从s出发的所有可能达到的状态都已经进入了m1中，而m1仍然没有和m2产生交集
//     (3)注意：m2中可是包好target的啊！！！所以从s出发永远达不到target

8.dfs-递归深度优先搜索

T1-通过添加+ 、- 运算符得到target目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

代码如下:

class Solution {
public://定义dfsint t=0,size=0;int cnt=0;void dfs(int sum,vector<int>& nums,int level){//(1)层数 +1level++;//(2)level<=size可以继续递归if(level<=size){dfs(sum+nums[level-1],nums,level); //加法 深入一层dfs(sum-nums[level-1],nums,level); //减法 深入一层}//(3)出口else{if(sum==t){cnt++;}return;}}int findTargetSumWays(vector<int>& nums, int target) {//利用 dfs递归思想--遍历每一种情况//1.先设置好 重要的 全局参数t=target;size=nums.size();//2.调用dfsdfs(0,nums,0);//3.返回结果return cnt;}
};

9.unorder_map哈希表的 常用场景:

T1-两数之和:

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

代码如下：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//unordered_map---yyds太妙了！思路：先把nums中的元素 以及对应的下标存进map中，然后遍历查找://1.存储:int size=nums.size();unordered_map<int,int> map1;for(int i=0;i<=size-1;i++){map1[nums[i]]=i;}//2.遍历查找:for(int i=0;i<=size-1;i++){if(map1.count(target-nums[i])&&i!=map1[target-nums[i]])return {i,map1[target-nums[i]]};}return {-1,-1};}
};

10.旋转二维矩阵：（一个线性代数的问题:转置 + reverse）

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

代码如下：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {//线性代数：有这一道题--先转置，然后行reverseint size=matrix.size();//1.转置for(int i=0;i<=size-1;i++){for(int j=i+1;j<=size-1;j++){swap(matrix[i][j],matrix[j][i]);}}//2.行reversefor(auto &it: matrix){reverse(it.begin(),it.end());}}
};

-3.三次周赛 和 1次双周赛 题目总结:（单独打印......）

-2.包括字符串匹配KMP算法，凸包等 数据结构课程上的 算法题目 - 总结（单独打印......）

-1.动态规划部分的题目--（单独打印......）