一、 前言

LeetCode 高频题目 Hot100习题笔记(一)
hot前10看上一篇文章喔，本篇论文主要刷的是Top 10-20的题目

LeetCode Hot100 习题，在官网上看热度需要会员，推荐codetop网站，是微软的一位大佬设计的网站，按照大厂习题热度排了序。

加油呀，每天整理算法的学习资料~~~ 冲冲冲

二、习题

141 环形链表

/ * 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) { unordered_set<ListNode*> uset; while(head){     if(uset.count(head)) return true;     uset.insert(head);     head = head->next; } return false;    }};

102 二叉树的层次遍历

class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if(root == nullptr) return result; queue<TreeNode*> q; q.push(root); while(!q.empty()){     int size = q.size();     vector<int> temp;     while(size--){  TreeNode* node = q.front();  q.pop();  temp.push_back(node->val);  if(node->left) q.push(node->left);  if(node->right) q.push(node->right);     }     result.push_back(temp); } return result;    }};

121 买卖股票的最佳时机

动态规划题目
dp[i][0]表示第i天不持有股票的最大值
dp[i][1]表示第i天持有股票的最大值
也就是说在第I天下有两种状态
今天持有股票：
1、昨天的股票今天没卖
2、昨天没买股票，今天买了
今天不持有股票：
1、昨天不持有股票
2、昨天有股票，今天卖了
因此：
初始化状态:
dp[0][0]表示第一天没有买卖股票，利润0
dp[0][1] 表示第一天买了股票，利润-price[0];
实现代码

class Solution {public:    int maxProfit(vector<int>& prices) { int  len = prices.size(); if(len == 0) return 0; vector<vector<int>> dp(len, vector<int>(2)); dp[0][1] -= prices[0]; dp[0][0] = 0; for(int i = 1; i < len; i++){     // 今天持有股票     dp[i][1] = max(dp[i-1][1], -prices[i]);     // 今天不持有股票的最大值     dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]); } return dp[len - 1][0];    }};

160 相交链表

class Solution {public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {std::set<ListNode*> node_set;//将链表A的地址存在集合中while (headA){node_set.insert(headA);headA=headA->next;}//在集合中查找链表B的地址while (headB){//如果找到了headBif (node_set.find(headB) != node_set.end()) {return headB;}headB = headB->next;}return NULL;}};

103 二叉树的锯齿形层序遍历

推荐一个非常棒的算法学习网站，代码随想录
https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

/ * 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>> zigzagLevelOrder(TreeNode* root) { // 其实就是层次遍历加翻转 vector<vector<int>> res; if(root == nullptr) return res; queue<TreeNode*> que; que.push(root); int count = 1; while(!que.empty()){     int size = que.size();// 取每一层元素个数     vector<int> temp  = {};// 临时存放每一层的元素     for(int i = 0; i < size; ++i){  TreeNode* node = que.front();  que.pop();  temp.push_back(node->val);  if(node->left) que.push(node->left);  if(node->right) que.push(node->right);     }     if(count %2 == 0)  reverse(temp.begin(), temp.end());     count++;     res.push_back(temp); } return res;    }};

88.合并两个有序数组

class Solution {public:    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int m1=m-1; int n1=n-1; int len=m+n-1; while(m1>=0&&n1>=0){     nums1[len--]=nums1[m1]>nums2[n1]?nums1[m1--]:nums2[n1--]; } while(n1>=0){     nums1[len--] = nums2[n1--]; }    }};

20 有效地括号

class Solution {public:    bool isValid(string s) { stack<char> st; for(int i =0; i < s.length(); ++i){     char one = s[i];     if(!st.empty()){  char temp = st.top();  if(temp == '(' && one == ')' ||     temp == '[' && one == ']' ||     temp == '{' && one == '}'){      st.pop();      continue;     }     }     st.push(one); } if(st.empty()) return true; else return false;    }};

236 二叉树的最近公共祖先

class Solution {public:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 如果找到p/q 或者root = nullptr则返回 if(root == p || root == q || root == nullptr ) return root; // 后序遍历模拟回溯 TreeNode* left = lowestCommonAncestor(root->left,p,q); TreeNode* right = lowestCommonAncestor(root->right,p,q); // 左右不为空 说明找到了 // 左为空 右边不空空则说明 祖先一定在右边 if(left !=nullptr && right != nullptr) return root; else if(left!=nullptr && right == nullptr) return left; else return right;    }};

5 最长回文子串

class Solution {public:    string longestPalindrome(string s) { // dp[i][j] 表示区间[i,j]的子串是否为回文子串 vector<vector<int>> dp(s.size(),vector<int>(s.size(),0)); /*情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串 情况二：下标i 与 j相差为1，例如aa，也是文子串 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。 */  int maxLen = 0; int left = 0; int right = 0; for(int i = s.size() - 1; i>=0; i--){     // 从下到上，防止dp[i+1][j-1]没计算的     for(int j = i; j <s.size(); j++){  if(s[i] == s[j]){      if( j  - i <=1){   // 情况一和情况二   dp[i][j] = true;      }else if(dp[i+1][j-1]){   // 情况三   dp[i][j] = true;      }  }  if(dp[i][j] && j -i + 1 >maxLen){      maxLen = j - i + 1;      left = i;      right = j;  }     } } return s.substr(left, right - left + 1);    }};

33 搜索旋转排序数组

class Solution {public:    int search(vector<int>& nums, int target) { int n = (int)nums.size(); if (!n) {     return -1; } if (n == 1) {     return nums[0] == target ? 0 : -1; } int l = 0, r = n - 1; while (l <= r) {     int mid = (l + r) / 2;     if (nums[mid] == target) return mid;     if (nums[0] <= nums[mid]) {  if (nums[0] <= target && target < nums[mid]) {      r = mid - 1;  } else {      l = mid + 1;  }     } else {  if (nums[mid] < target && target <= nums[n - 1]) {      l = mid + 1;  } else {      r = mid - 1;  }     } } return -1;    }};

三、参考资料

• CodeTop100
• LeetCode