当前位置：首页 > news >正文

CodeTop 复习

news 2025/8/15 15:58:24

CodeTop 复习

1.递归篇
- 1.[合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/)
- 2.[汉诺塔问题](https://leetcode.cn/problems/hanota-lcci/)
2.动态规划
- 1.[使用最小花费爬楼梯](https://leetcode.cn/problems/min-cost-climbing-stairs/description/)
- 2.[第N个斐波那契数](https://leetcode.cn/problems/n-th-tribonacci-number/description/)
- 3.[三步问题](https://leetcode.cn/problems/three-steps-problem-lcci/)
3.贪心
- 1.[柠檬水找零](https://leetcode.cn/problems/lemonade-change/)
- 2.[将数组和减半的最少操作次数](https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/)

1.递归篇

1.合并两个有序链表

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//递归if(list1==nullptr) return list2;if(list2==nullptr) return list1;if(list1->val<=list2->val){//返回l1list1->next=mergeTwoLists(list1->next,list2);return list1;}else{list2->next=mergeTwoLists(list1,list2->next);return list2;}  }
};

2.汉诺塔问题

第一次把a上的移到b上,c是空的,所以把b当成原来的c:->dfs(a,c,b);
第二次把b上的移到c上,a是空的,所以:->dfs(b,a,c);

class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {dfs(A,B,C,A.size());        }void dfs(vector<int>& a, vector<int>& b, vector<int>& c,int n){if(1==n){c.push_back(a.back());a.pop_back();return;}dfs(a,c,b,n-1);c.push_back(a.back());a.pop_back();dfs(b,a,c,n-1);}
};

2.动态规划

1.使用最小花费爬楼梯

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//动态规划//最后楼顶的位置是size处//dp里是到达i位置时的最低花费vector<int> dp(cost.size()+1,0);dp[0]=0,dp[1]=0;for(int i=2;i<dp.size();i++)dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);return dp[dp.size()-1];}
};

2.第N个斐波那契数

class Solution {
public:int tribonacci(int n) {//用递归,轮转数组,可以节省空间//dp[i]里表示第i个Tnint dp[4]={0};dp[0]=0,dp[1]=1,dp[2]=1;if(n<3) return dp[n];for(int i=3;i<=n;i++){dp[3]=dp[1]+dp[2]+dp[0];dp[0]=dp[1];dp[1]=dp[2];dp[2]=dp[3];}return dp[3];       }
};