leetcode 热题100题

538. 把二叉搜索树转换为累加树

leetcode-100题 - 图1
代码思路：反序中序遍历的方法

BST的中序遍历就是从小到大,那么反过来就是从大到小,然后累加就好了.

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11.     int num=0;
  12. public:
  13.     TreeNode* convertBST(TreeNode* root) {
  14.         if(root!=NULL){
  15.             //遍历右子树
  16.             convertBST(root->right);
  17.             //遍历节点
  18.             root->val=root->val+num;
  19.             num=root->val;
  20.             //遍历左子树
  21.             convertBST(root->left);
  22.             return root;
  23.         }
  24.         return NULL;
  25.     }
  26. };

时间复杂度：O(n)
空间复杂度：O(n)

  • 是否独立解答
  • 是否理解程序代码

448. 找到所有数组中消失的数字

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

我的代码：

先排序，然后判断相邻两位的差值是否大于1，大于1则证明中间缺少数字，数组首尾是否为1和n单独判断

  1. class Solution {
  2. public:
  3.     vector<int> findDisappearedNumbers(vector<int>& nums) {
  4.         if(nums.size()<1) return nums;
  5.         sort(nums.begin(),nums.end());
  6.         int len=nums.size();
  7.         vector<int> n;
  9.         if(nums[0]!=1){
  10.             int j=nums[0]-1;
  11.             for(int k=1;k<=j;k++){
  12.                     n.push_back(k);
  13.                 }
  14.         }
  16.         for(int i=0;i<len-1;i++){
  17.             if(nums[i+1]-nums[i]>1){
  18.                 int j=nums[i+1]-nums[i];
  19.                 for(int k=1;k<j;k++){
  20.                     n.push_back(nums[i]+k);
  21.                 }
  22.             }
  23.         }
  24.         if(nums[len-1]!=len){
  25.             int j=len-nums[len-1];
  26.             for(int k=1;k<=j;k++){
  27.                     n.push_back(nums[len-1]+k);
  28.                 }
  29.         }
  30.         return n;
  31.     }
  32. };

执行用时 :228 ms, 在所有 C++ 提交中击败了6.32%的用户

内存消耗 :32.4 MB, 在所有 C++ 提交中击败了5.56%的用户

时间复杂度：O(n^2)
空间复杂度：O(n)

  • 是否独立完成
  • 是否理解代码

优秀解答：

将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。

image-20200412170955971

  1. class Solution {
  2. public:
  3.     vector<int> findDisappearedNumbers(vector<int>& nums) {
  4.         for (int i = 0; i < nums.size(); ++i)
  5.         nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);
  6.         vector<int> res;
  7.         for (int i = 0; i < nums.size(); ++i){
  8.             if (nums[i] > 0)
  9.                 res.push_back(i+1);
  10.         }
  11.         return res;
  12.         }
  13. };

执行用时 :112 ms, 在所有 C++ 提交中击败了37.58%的用户

内存消耗 :32.2 MB, 在所有 C++ 提交中击败了5.56%的用户

  • 代码是否理解

时间复杂度：O(n)
空间复杂度：O(n)

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
img
在节点 c1 开始相交。
我的代码：

首先计算出两链表的长度差 len，让长链表指针先走 len，然后两链表指针一起走，当两链表指针指到同一位置时，即找到相交点。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  * };
  7.  */
  8. class Solution {
  9.     int a=0,b=0;
  10. public:
  11.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  12.         ListNode* pA=headA;
  13.         ListNode* pB=headB;
  14.         while(pA!=NULL){
  15.             a++;
  16.             pA=pA->next;
  17.         }
  18.         while(pB!=NULL){
  19.             b++;
  20.             pB=pB->next;
  21.         }
  22.         pA=headA;
  23.         pB=headB;
  24.         if(a>=b){
  25.             int len=a-b;
  26.             while(len--){
  27.                 pA=pA->next;
  28.             }
  29.             while(b--){
  30.                 if(pB==pA){
  31.                     return pA;
  32.                 }
  33.                 pA=pA->next;
  34.                 pB=pB->next;
  35.             }
  36.             return NULL;
  37.         }
  38.         if(a<b){
  39.             int len=b-a;
  40.             while(len--){
  41.                 pB=pB->next;
  42.             }
  43.             while(a--){
  44.                 if(pB==pA){
  45.                     return pA;
  46.                 }
  47.                 pA=pA->next;
  48.                 pB=pB->next;
  49.             }
  50.             return NULL;
  51.         }
  52.      return NULL;
  53.     }
  54. };

执行用时 :60 ms, 在所有 C++ 提交中击败了56.78%的用户

内存消耗 :14.7 MB, 在所有 C++ 提交中击败了100.00%的用户

  • 是否独立完成
  • 是否理解代码

时间复杂度：O(n)
空间复杂度：O(1)

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

暴力模式：

我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int n = (int)prices.size(), ans = 0;
  5.         for (int i = 0; i < n; ++i){
  6.             for (int j = i + 1; j < n; ++j){
  7.                 ans = max(ans, prices[j] - prices[i]);
  8.             }
  9.         }
  10.         return ans;
  11.     }
  12. };

执行超时。

  • 是否独立完成
  • 是否理解代码

时间复杂度：O(n^2)
空间复杂度：O(1)

利用栈:

相关链接

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int ans = 0;
  5.         vector<int> St;
  6.         prices.emplace_back(-1); // 哨兵👨‍✈️,运行到最后一个(哨兵)时，强制当前栈顶出栈并计算利润(与栈底元素差值)
  7.         for (int i = 0; i < prices.size(); ++ i){
  8.             while (!St.empty() && St.back() > prices[i]){ // 当栈不为空时或栈顶元素大于即将要入栈元素时，计算栈顶与栈底元素差
  9.                 ans = std::max(ans, St.back() - St.front()); // 计算栈顶与栈底元素差,并维护最大值
  10.                 St.pop_back();//栈顶元素出栈
  11.             }
  12.             St.emplace_back(prices[i]);//否则将要入栈的元素入栈
  13.         }
  15.         return ans;
  16.     }
  17. };

执行用时 :16 ms, 在所有 C++ 提交中击败了32.69%的用户

内存消耗 :13.3 MB, 在所有 C++ 提交中击败了5.19%的用户

  • 是否独立完成
  • 是否理解代码

    155. 最小栈

    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    push(x) —— 将元素 x 推入栈中。
    pop() —— 删除栈顶的元素。
    top() —— 获取栈顶元素。
    getMin() —— 检索栈中的最小元素。
    示例: ``` MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); —> 返回 -3. minStack.pop(); minStack.top(); —> 返回 0. minStack.getMin(); —> 返回 -2.
  1. 思路：
  3. > 思路：每次入栈2个元素，一个是入栈的元素本身，一个是当前栈元素的最小值 _ 如：入栈序列为2-3-1，则入栈后栈中元素序列为：2-2-3-2-1-1 _ 用空间代价来换取时间代价

class MinStack { public: /* initialize your data structure here. / MinStack() {

  1. }
  3. void push(int x) {
  4.     if(st.empty()){
  5.         st.push(x);
  6.         st.push(x);
  7.     }else{
  8.         int tmp=st.top();
  9.         st.push(x);
  10.         if(tmp<x){
  11.             st.push(tmp);
  12.         }else{
  13.             st.push(x);
  14.         }
  15.     }
  17. }
  19. void pop() {
  20.     st.pop();
  21.     st.pop();
  22. }
  24. int top() {
  25.     int t=st.top();
  26.     st.pop();
  27.     int top=st.top();
  28.     st.push(t);
  29.     return top;
  30. }
  32. int getMin() {
  33.     return st.top();
  34. }
  35. private:
  36. stack<int> st;

};

/**

  • Your MinStack object will be instantiated and called as such:
  • MinStack* obj = new MinStack();
  • obj->push(x);
  • obj->pop();
  • int param_3 = obj->top();
  • int param_4 = obj->getMin(); */
  2. > 执行用时 :44 ms, 在所有 C++ 提交中击败了43.73%的用户
  4. > 内存消耗 :15 MB, 在所有 C++ 提交中击败了100.00%的用户
  7. - [ ]  是否独立完成
  8. - [ ]  是否理解代码
  10. [官方题解](https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/)：
  12. > 这道题最直接的解法就是我们可以用两个栈，一个栈去保存正常的入栈出栈的值，另一个栈去存最小值，也就是用栈顶保存当前所有元素的最小值。存最小值的栈的具体操作流程如下：
  14. > 将第一个元素入栈。
  16. > 新加入的元素如果大于栈顶元素，那么新加入的元素就不处理。
  18. > 新加入的元素如果小于等于栈顶元素，那么就将新元素入栈。
  20. > 出栈元素不等于栈顶元素，不操作。
  22. > 出栈元素等于栈顶元素，那么就将栈顶元素出栈。

class MinStack { /* initialize your data structure here. / private Stack stack; private Stack minStack;

  1. public MinStack() {
  2.     stack = new Stack<>();
  3.     minStack = new Stack<>();
  4. }
  6. public void push(int x) {
  7.     stack.push(x);
  8.     if (!minStack.isEmpty()) {
  9.         int top = minStack.peek();
  10.         //小于的时候才入栈
  11.         if (x <= top) {
  12.             minStack.push(x);
  13.         }
  14.     }else{
  15.         minStack.push(x);
  16.     }
  17. }
  19. public void pop() {
  20.     int pop = stack.pop();
  22.     int top = minStack.peek();
  23.     //等于的时候再出栈
  24.     if (pop == top) {
  25.         minStack.pop();
  26.     }
  28. }
  30. public int top() {
  31.     return stack.peek();
  32. }
  34. public int getMin() {
  35.     return minStack.peek();
  36. }

}

  2. - [ ]  是否独立完成
  3. - [ ]  是否理解代码
  5. ---
  7. #### [70. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)
  8. 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。<br />每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？<br />注意：给定 n 是一个正整数。<br />示例 1：
  10. > 输入： 2<br />
  11. 输出： 2<br />
  12. 解释： 有两种方法可以爬到楼顶。
  14. > 
  15. > 1. 1 阶 + 1 阶
  16. > 1. 2 阶
  21. 解题思路：使用递归来做，第n阶台阶需要n-1阶台阶+1，或者n-2阶台阶+2.

class Solution { public: int climbStairs(int n) { if(n==1) return 1; if(n==2) return 2; return climbStairs(n-1)+climbStairs(n-2);

  1. }

};

  1. 当n=44时，报超时。**21 / 45** 个通过测试用例。<br />时间复杂度：O(2^n)<br />空间复杂度：O(n)
  3. - [ ]  是否独立完成
  4. - [ ]  是否理解代码
  6. 解题思路：循环方式从1开始，n=(n-1)+(n-2)

class Solution { public: int climbStairs(int n) { if(n==1) return 1; if(n==2) return 2; int sum=0,j=1,k=2; for(int i=3;i<=n;i++){ sum=j+k; j=k; k=sum; } return sum;
} };

  1. 执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户<br />内存消耗 :6 MB, 在所有 C++ 提交中击败了100.00%的用户<br />时间复杂度：O(n)<br />空间复杂度：O(1)
  3. - [ ]  是否独立完成
  4. - [ ]   是否理解代码
  6. ---
  8. #### [198. 打家劫舍](https://leetcode-cn.com/problems/house-robber/)
  9. 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。<br />给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。<br />示例 1:
  11. > 输入: [1,2,3,1]<br />
  12. 输出: 4<br />
  13. 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。<br />
  14. 偷窃到的最高金额 = 1 + 3 = 4 。
  17. 解题思路：动态规划，`dp[i]=max(dp[i-2]+nums[i]，dp[i-1])`

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

  1. }

};

``` 执行用时 :4 ms, 在所有 C++ 提交中击败了58.08%的用户
内存消耗 :7.8 MB, 在所有 C++ 提交中击败了100.00%的用户
时间复杂度：O(n)
空间复杂度：O(n)

  • 是否独立完成
  • 是否理解代码