【leetcode刷题之路】初级算法——链表+树+排序和搜索+动态规划

news/2024/11/23 2:16:32/

文章目录

    • 3 链表
      • 3.1 【链表】删除链表中的节点
      • 3.2 【双指针】删除链表的倒数第 N 个结点
      • 3.3 【链表】反转链表
      • 3.4 【链表】合并两个有序链表
      • 3.5 【链表】回文链表
      • 3.6 【双指针】环形链表
    • 4 树
      • 4.1 【递归】二叉树的最大深度
      • 4.2 【递归】验证二叉搜索树
      • 4.3 【递归】对称二叉树
      • 4.4 【BFS】二叉树的层序遍历
      • 4.5 【分治】将有序数组转换为二叉搜索树
    • 5 排序和搜索
      • 5.1 【排序】合并两个有序数组
      • 5.2 【二分】第一个错误的版本
    • 6 动态规划
      • 6.1 【动态规划】爬楼梯
      • 6.2 【动态规划】买卖股票的最佳时机
      • 6.3 【动态规划】最大子数组和
      • 6.4 【动态规划】打家劫舍

3 链表

3.1 【链表】删除链表中的节点

https://leetcode.cn/problems/delete-node-in-a-linked-list/

给出的就是要删除的那个节点，直接前后移动就行了。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:void deleteNode(ListNode* node) {node->val = node->next->val;node->next = node->next->next;}
};

3.2 【双指针】删除链表的倒数第 N 个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

利用双指针left和right，首先让right遍历n个节点，再让两个指针同时遍历，当right遍历到链表结尾时，left所指的就是倒数第n个节点，正常删除即可。

/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* left = head;ListNode* right = head;for(int i=0;i<n;i++){right = right->next;}if(right == nullptr) return head->next;while(right->next!=nullptr){left = left->next;right = right->next;}left->next = left->next->next;return head;}
};

3.3 【链表】反转链表

https://leetcode.cn/problems/reverse-linked-list/

使用头插法解决，后续考虑一下递归和栈。

/*** 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* reverseList(ListNode* head) {ListNode* ans = nullptr;ListNode* x = head;while(x){ListNode* p = x;x = x->next;p->next = ans;ans = p;}return ans;}
};

3.4 【链表】合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/

常规做法，挨个比较大小，后续考虑如何用递归完成。

/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {if(!list1) return list2;if(!list2) return list1;ListNode* ans = new ListNode();ListNode* tmp = ans;while(list1 && list2){if(list1->val <= list2->val){tmp->next = list1;list1 = list1->next;}else{tmp->next = list2;list2 = list2->next;}tmp = tmp->next;}if(!list1) tmp->next = list2;if(!list2) tmp->next = list1;return ans->next;}
};

3.5 【链表】回文链表

https://leetcode.cn/problems/palindrome-linked-list/

首先将链表进行反转，然后按照链表长度的一半逐一进行比较即可，这里要注意赋值的问题，一开始我是想直接把head赋值给一个空链表，后面发现指针这个东西都是指向同一个地址的，所以其中一个的结构变了另一个也会跟着变，后来就改用数组来存head里面原来正序的数字了，后期可以考虑一下如何用双指针（快慢指针）和栈怎么解决。

/*** 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:bool isPalindrome(ListNode* head) {ListNode* res = nullptr;vector<int> num;int length = 0;while(head){num.push_back(head->val);ListNode *temp = head;head = head->next;temp->next = res;res = temp;length++;}int i = 0;while(res && i*2<=length-1){if(num[i] != res->val) return false;res = res->next;i++;}return true;}
};

3.6 【双指针】环形链表

https://leetcode.cn/problems/linked-list-cycle/

定义快慢指针，快指针一次走两步，慢指针一次走一步，如果存在环，则两个指针总会相遇，否则不存在环。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *fast = head;ListNode *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow) return true;}return false;}
};

4 树

4.1 【递归】二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

递归解决，分别遍历左右子树，找出其中的最大值作为树的最大深度。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if(root == NULL) return 0;else{int left_depth = maxDepth(root->left);int right_depth = maxDepth(root->right);return max(left_depth,right_depth)+1;}}
};

4.2 【递归】验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

递归实现，首先要明白二叉搜索树的判定条件，一是左子树<root<右子树，二是下面的左子树的值要比当前结点小，而右子树的值要比当前结点大，也就是不能只在一个小的子树上满足这个条件，往上回溯几代之后这个条件要依然满足才行。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isValidBST(TreeNode* root) {return isValidBST(root , NULL , NULL);}bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {if(root == NULL) return true;else{if(min != NULL && root->val <= min->val) return false;if(max != NULL && root->val >= max->val) return false;}return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);}
};

4.3 【递归】对称二叉树

https://leetcode.cn/problems/symmetric-tree/

以下是递归解法，详见代码，之后需要考虑一下非递归如何实现。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {//如果root为空，则返回trueif(root == NULL) return true;else return isSymmetric(root->left, root->right);}bool isSymmetric(TreeNode* left, TreeNode* right) {//如果左右子树均为空，则返回trueif(left == NULL && right == NULL) return true;//如果只有一个子树为空，或者两个子树均不为空但值不相等，则返回falseelse if(left == NULL || right == NULL || left->val != right->val) return false;//比较左子树的右子树和右子树的左子树是否对称、左子树的左子树和右子树的右子树是否对称else return isSymmetric(left->right, right->left) && isSymmetric(left->left, right->right);}
};

4.4 【BFS】二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

BFS解题，按照树的每一层进行遍历，首先定义队列，如果当前节点不为空，则加入队列，之后分别遍历该节点的左右子树，依次重复上述操作，直到最后队列元素为空。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if(root == NULL) return ans;queue<TreeNode*> tree_node;tree_node.push(root);while(!tree_node.empty()){int n = tree_node.size();vector<int> subtree;for(int i=0;i<n;i++){TreeNode* temp = tree_node.front();tree_node.pop();subtree.push_back(temp->val);if(temp->left != NULL) tree_node.push(temp->left);if(temp->right != NULL) tree_node.push(temp->right);}ans.push_back(subtree);}return ans;}
};

4.5 【分治】将有序数组转换为二叉搜索树

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

分治解题，将构造树的过程分为两部分，首先从数组的中间元素开始，左边的数为左子树，右边的数为右子树，依次往后递推。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {if(nums.size()==0) return NULL;else return sortedArrayToBST(nums, 0, nums.size()-1);}TreeNode* sortedArrayToBST(vector<int>& nums, int start, int end) {if(start > end) return NULL;else{int mid = (start + end) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = sortedArrayToBST(nums, start, mid-1);root->right = sortedArrayToBST(nums, mid+1, end);return root;}}
};

5 排序和搜索

5.1 【排序】合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/

直接把nums2的值赋值到nums1后面，然后对nums1进行排序即可。

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {for(int i=0;i<n;i++){nums1[m+i] = nums2[i];}sort(nums1.begin(),nums1.end());}
};

5.2 【二分】第一个错误的版本

https://leetcode.cn/problems/first-bad-version/

二分法解题，注意遍历大小是从1到n，不要越界了。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int left = 1 , right = n;while(left<right){int mid = left + (right - left) / 2;if(!isBadVersion(mid)) left = mid + 1;else right = mid;}return left;}
};

6 动态规划

6.1 【动态规划】爬楼梯

https://leetcode.cn/problems/climbing-stairs/

爬一楼需要1次，爬二楼需要2次，爬三楼需要3次，这个3次可以看做是从一楼+2或者二楼+1
也就是f（n）=f（n-1）+f（n-2）

class Solution {
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;int ans[n];ans[0] = 1;ans[1] = 2;for(int i=2;i<n;i++){ans[i] = ans[i-1] + ans[i-2];}return ans[n-1];}
};

6.2 【动态规划】买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

动态规划解题，首先定义数组dp[i][2]

  • dp[i][0]：表示第i+1天结束的时候，如果手里没有持有股票，最大的利润是多少
  • dp[i][1]：表示第i+1天结束的时候，如果手里持有股票，最大的利润是多少

在这里我们分别对上述两个进行计算：

  • dp[i][0]
    这个考虑到两种情况，一是第i天没有持有股票，所以与第i天未持有股票的利润一样，二是第i天持有股票，但是决定在第i+1天卖掉，所以利润为第i天持有股票的利润+第i+1天该股票的价格，两个取最大值即可
  • dp[i][1]
    这个也考虑到两种情况，一是第i天持有股票，所以与第i天持有股票的利润一样，二是第i天未持有股票，但是决定在第i天买入，所以利润为负值，两个取最大值即可
//原始代码
class Solution {
public:int maxProfit(vector<int>& prices) {int length = prices.size();if(length==1) return 0;int dp[length][2];dp[0][0] = 0;dp[0][1] = -prices[0];for(int i=1;i<length;i++){dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);dp[i][1] = max(dp[i-1][1],-prices[i]);}return dp[length-1][0];}
};//优化后的代码---用两个变量代替数组
class Solution {
public:int maxProfit(vector<int>& prices) {int length = prices.size();if(length==1) return 0;int stock_unhold = 0;int stock_hold = -prices[0];for(int i=1;i<length;i++){stock_unhold = max(stock_unhold,stock_hold + prices[i]);stock_hold = max(stock_hold,-prices[i]);}return stock_unhold;}
};

6.3 【动态规划】最大子数组和

https://leetcode.cn/problems/maximum-subarray/

利用动态规划，首先定义数组dp[i]，表示终点下标为i的序列的最大子数组和，主要考虑以下两种情况：

  • 如果dp[i-1]大于0，则继续向前增加下标为i的数值，作为dp[i]的子数组和
  • 如果dp[i-1]小于0，则从这里开始停止，重新计算子数组和，赋值为0后再加入下标为i的数值，作为dp[i]的子数组和

最后的结果就是数组中最大的那个值

//原始
class Solution {
public:int maxSubArray(vector<int>& nums) {int length = nums.size();if(length==1) return nums[0];int dp[length];int ans = nums[0];dp[0] = nums[0];for(int i=1;i<length;i++){dp[i] = max(dp[i-1],0) + nums[i];if(dp[i] > ans) ans = dp[i];}return ans;}
};//优化代码---用变量代替数组
class Solution {
public:int maxSubArray(vector<int>& nums) {int length = nums.size();if(length==1) return nums[0];int dps = nums[0];int ans = nums[0];for(int i=1;i<length;i++){dps = max(dps,0) + nums[i];if(dps > ans) ans = dps;}return ans;}
};

6.4 【动态规划】打家劫舍

https://leetcode.cn/problems/house-robber/

利用动态规划，首先定义数组dp[i][2]，状态转移如下所示：

  • dp[i][0]表示第i家不被偷，则前一家可能被偷，也可能没有被偷，取最大值即可；
  • dp[i][1]表示第i家被偷，则前一家一定没有被偷，所以为dp[i-1][0]+nums[i]

最后在第i家的时候取被偷和未被偷之间的最大值即可

class Solution {
public:int rob(vector<int>& nums) {int length = nums.size();if(length==1) return nums[0];int dp[length][2];dp[0][0] = 0;dp[0][1] = nums[0];for(int i=1;i<length;i++){dp[i][0] = max(dp[i-1][0],dp[i-1][1]);dp[i][1] = dp[i-1][0] + nums[i];}if(dp[length-1][0] > dp[length-1][1]) return dp[length-1][0];else return dp[length-1][1];}
};

http://www.ppmy.cn/news/99816.html

相关文章

1170 Safari Park(39行代码+超详细注释)

1170 Safari Park(39行代码+超详细注释)

分数 25 全屏浏览题目 切换布局 作者 陈越 单位 浙江大学 A safari park&#xff08;野生动物园&#xff09;has K species of animals, and is divided into N regions. The managers hope to spread the animals to all the regions, but not the same animals in the t…
阅读更多...
子串--子字符串 0528

子串--子字符串 0528

210102 201012 A1A2…An An…A2A1 如何做&#xff0c; 翻转的是21&#xff0c;因为2>1; 翻转的是210&#xff0c;因为2>0; 翻转的是2101&#xff0c;因为2>1&#xff1b; 翻转的是21010&#xff0c;因为2>0&#xff1b; 翻转的是210102&#xff0c;因为22且1&…
阅读更多...
SpringBoot整合MiniIo

SpringBoot整合MiniIo

什么是MiniIo&#xff1f; MiniIo是一款开源的、轻量级的、分布式的云存储服务。与其他云存储服务相比&#xff0c;MiniIo偏向于“自部署”的架构&#xff0c;也就是说&#xff0c;它更适合部署在自己的服务器上&#xff0c;而不是类似于阿里云、腾讯云等云服务商提供的云存储…
阅读更多...
Python中模块的使用方法4

Python中模块的使用方法4

1 模块、包和库的区别 Python中&#xff0c;模块的英文是“module”&#xff0c;是一个以py为后缀名的文件&#xff1b;包的英文是“package”&#xff0c;是一个包含了多个模块的目录&#xff1b;库的英文是“library”&#xff0c;包含了具有相关功能的包和模块。 2 模块的…
阅读更多...
Flume系列：案例-Flume 聚合拓扑(常见的日志收集结构)

Flume系列：案例-Flume 聚合拓扑(常见的日志收集结构)

目录 Apache Hadoop生态-目录汇总-持续更新 1&#xff1a;案例需求-实现聚合拓扑结构 3&#xff1a;实现步骤&#xff1a; 2.1&#xff1a;实现flume1.conf - sink端口4141 2.2&#xff1a;实现flume2.conf- sink端口4141 2.3&#xff1a;实现flume3.conf - 监听端口4141 …
阅读更多...
ChatGPT生成Excel统计公式

ChatGPT生成Excel统计公式

&#x1f34f;&#x1f350;&#x1f34a;&#x1f351;&#x1f352;&#x1f353;&#x1fad0;&#x1f951;&#x1f34b;&#x1f349; ChatGPT生成Excel统计公式 文章目录 &#x1f350;问题引入&#x1f350;具体操作&#x1f433;结语 &#x1f350;问题引入…
阅读更多...
如何提升解决横向问题的能力

如何提升解决横向问题的能力

横向问题&#xff0c;简单来说就是软件系统内部与业务无关的技术债&#xff0c;比如性能、可扩展性、可用性、可测试性、可维护性和安全合规等问题。这些问题都属于非功能性需求&#xff0c;也就是说&#xff0c;产品经理一般不会把这些问题直接写在需求文档里。 可是日积月累…
阅读更多...
LINUX系统编程

LINUX系统编程

文章目录 linux系统介绍(属于扯闲篇)linux的概况linux的历史起源unixPosix标准和其他标准开源运动linux的诞生 linux使用使用范围linux的登录 linux常用命令linux的shell使用切换用户显示所有用户退出当前用户添加用户 删除用户当前工作目录当前工作目录下的所有文件改变当前工…
阅读更多...
最新文章

Copyright @ 2022~2023