• Leetcode刷题笔记--Hot51-60

    目录

    1--环形链表II（142）

    2--LRU缓存（146）

    3--排序列表（148）

    4--乘积最大子数组（152）

    5--最小栈（155）

    6--相交链表（160）

    7--多数元素（169）

    8--打家劫舍（198）

    9--岛屿数量（200）

    10--反转链表（206）

    1--环形链表II（142）

    主要思路：

            快慢指针，快指针每次走两步，慢指针每次走一步；

            第一次相遇时，假设慢指针共走了 f 步，则快指针走了 2f 步；

            假设起点到环入口结点的长度为 a（不包括入口结点），环的结点数为 b；快指针比慢指针多走的步数肯定全在环中，则有 2f - f = f = nb；则慢指针共走了 nb 步；

            由于慢指针共走了 nb 步，而起点到环入口结点的步数为 a，则实际慢指针在环内走了 nb - a 步；

            此时让慢指针从起点重新出发走 a 步，每次走 1 步；快指针从相遇的地方出发，每次也走 1 步，快慢指针必然在环入口结点相遇；因此快指针相当于也走了 a 步，恰好与 nb - a 步互补，构成完整圈数的 nb 环；

    1. #include 
    2. #include 
    3.  
    4. struct ListNode {
    5.     int val;
    6.     ListNode *next;
    7.     ListNode(int x) : val(x), next(NULL) {}
    8. };
    9.  
    10. class Solution {
    11. public:
    12.     ListNode *detectCycle(ListNode *head) {
    13.         if(head == nullptr) return head;
    14.         ListNode *slow = head;
    15.         ListNode *fast = head;
    16.         while(fast != NULL && fast->next != NULL){
    17.             fast = fast->next->next;
    18.             slow = slow->next;
    19.             if(fast == slow) break; // 第一次相遇
    20.         }
    21.         if(fast == NULL || fast->next == NULL) return NULL; // 没有环
    22.         // 从头开始走
    23.         slow = head;
    24.         while(slow != fast){
    25.             slow = slow->next;
    26.             fast = fast->next;
    27.         }
    28.         // 第二次相遇就是环的入口
    29.         return slow;
    30.     }
    31. };
    32.  
    33. int main(int argc, char *argv[]) {
    34. 	// head = [3, 2, 0, -4], pos = 1
    35. 	ListNode *Node1 = new ListNode(3);
    36. 	ListNode *Node2 = new ListNode(2);
    37. 	ListNode *Node3 = new ListNode(0);
    38. 	ListNode *Node4 = new ListNode(-4);
    39.  
    40. 	Node1->next = Node2;
    41. 	Node2->next = Node3;
    42. 	Node3->next = Node4;
    43. 	Node4->next = Node2;
    44.  
    45. 	Solution S1;
    46. 	ListNode* res = S1.detectCycle(Node1);
    47. 	if(res != nullptr) std::cout << res->val << std::endl;
    48. 	else std::cout << "nullptr" << std::endl;
    49. 	return 0;
    50. }

    2--LRU缓存（146）

    主要思路：

            基于双向链表和哈希表；

            访问元素时，若元素不存在则返回；若元素存在，则将元素记录，并将元素移动到双向链表头部；（确保访问热度最高的元素放在双向链表头部，访问热度最低的元素放在双向链表尾部）；

            插入元素时，若元素不存在：当容量已满时，先移除双向链表尾部的元素，再将新元素插入到双向链表头部；若元素存在，则取出元素并更新元素的值，将更新后的元素插入到双向链表头部；

    1. #include 
    2. #include 
    3.  
    4. class LRUCache {
    5. public:
    6.     struct ListNode{
    7.         ListNode(int key, int val){
    8.             this->key = key;
    9.             this->val = val;
    10.         }
    11.         ListNode* pre = nullptr;
    12.         ListNode* next = nullptr;
    13.         int val = 0;
    14.         int key = 0;
    15.     };
    16.  
    17.     LRUCache(int capacity) {
    18.         this->cap = capacity; // 容量
    19.         head = new ListNode(-1, -1);
    20.         tail = new ListNode(-1, -1);
    21.         head->next = tail;
    22.         tail->pre = head;
    23.     }
    24.     
    25.     int get(int key) {
    26.         if(hash.count(key) == 0) return -1; // 元素不存在
    27.         ListNode* ptr = hash[key]; // 取出元素
    28.         remove(ptr); // 从双向链表中删除元素
    29.         insert(ptr); // 将元素插入到双向链表头部
    30.         return ptr->val; // 返回元素的值
    31.     }
    32.     
    33.     void put(int key, int value) {
    34.         if(hash.count(key) == 0){ // 元素不存在
    35.             if(hash.size() == cap){ // 容量已满
    36.                 ListNode* ptr = tail->pre;
    37.                 remove(ptr); // 去除尾部节点
    38.                 hash.erase(ptr->key);
    39.                 delete(ptr);
    40.             }
    41.             ListNode* new_node = new ListNode(key, value); // 新建节点
    42.             insert(new_node); // 插入新节点到头部
    43.             hash[new_node->key] = new_node;
    44.             return;
    45.         }
    46.         else{ // 元素存在
    47.             ListNode* ptr = hash[key]; // 取出元素
    48.             ptr->val = value; // 更新元素
    49.             remove(ptr); // 先删除元素
    50.             insert(ptr); // 再将元素插入到头部
    51.             return;
    52.         }
    53.     }
    54.  
    55.     void remove(ListNode* ptr){
    56.         // 取出前驱和后驱元素
    57.         ListNode* a = ptr->pre;
    58.         ListNode* b = ptr->next;
    59.         // 更新前驱和后驱元素的指向
    60.         a->next = b;
    61.         b->pre = a;
    62.         ptr->pre = ptr->next = nullptr;
    63.     }
    64.     void insert(ListNode* ptr){
    65.         ListNode* tmp = head->next; // 头指针的下一个元素
    66.         // 将元素插入到双向链表头部
    67.         ptr->pre = head;
    68.         head->next = ptr;
    69.         ptr->next = tmp;
    70.         tmp->pre = ptr;
    71.     }
    72. private:
    73.     int cap = 0; // 容量
    74.     std::unordered_map<int, ListNode*> hash; // 哈希表
    75.     ListNode* head; // 双向链表哨兵头节点
    76.     ListNode* tail; // 双向链表哨兵尾节点
    77. };
    78.  
    79. int main(int argc, char argv[]){
    80.  
    81.     return 0;
    82. }

    3--排序列表（148）

    主要思路：

            基于归并排序，先二分链表，再对链表进行归并排序；

    1. #include 
    2.  
    3. struct ListNode {
    4.     int val;
    5.     ListNode *next;
    6.     ListNode() : val(0), next(nullptr) {}
    7.     ListNode(int x) : val(x), next(nullptr) {}
    8.     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. };
    10.  
    11. class Solution {
    12. public:
    13.     ListNode* sortList(ListNode* head) {
    14.         return SplitList(head);
    15.     }
    16.  
    17.     ListNode* SplitList(ListNode* head){
    18.         if(head == nullptr || head->next == nullptr) return head; // 空或者只有一个结点
    19.  
    20.         ListNode* slow = head, *fast = head, *pre = head;
    21.         while(fast != nullptr){
    22.             pre = slow; // 慢指针的前继指针
    23.             fast = fast->next;
    24.             slow = slow->next;
    25.             if(fast == nullptr) break;
    26.             fast = fast->next;
    27.         }
    28.  
    29.         pre->next = nullptr; // 断开
    30.         return(merge(SplitList(head), SplitList(slow))); // 递归二分至底层，然后归并
    31.     }
    32.  
    33.     ListNode* merge(ListNode* head1, ListNode* head2){
    34.         ListNode* dummyNode = new ListNode(0);
    35.         ListNode *tmp = dummyNode, *tmp1 = head1, *tmp2 = head2;
    36.         while(tmp1 != nullptr && tmp2 != nullptr){
    37.             if(tmp1->val <= tmp2->val){
    38.                 tmp->next = tmp1;
    39.                 tmp1 = tmp1->next; 
    40.             }
    41.             else{
    42.                 tmp->next = tmp2;
    43.                 tmp2 = tmp2->next;
    44.             }
    45.             tmp = tmp->next;
    46.         }
    47.         while(tmp1 != nullptr){
    48.             tmp->next = tmp1;
    49.             tmp1 = tmp1->next;
    50.             tmp = tmp->next;
    51.         }
    52.         while(tmp2 != nullptr){
    53.             tmp->next = tmp2;
    54.             tmp2 = tmp2->next;
    55.             tmp = tmp->next;
    56.         }
    57.         return dummyNode->next;
    58.     }
    59. };
    60.  
    61. int main(int argc, char *argv[]) {
    62.     // head = [4, 2, 1, 3]
    63.     ListNode* Node1 = new ListNode(4);
    64.     ListNode* Node2 = new ListNode(2);
    65.     ListNode* Node3 = new ListNode(1);
    66.     ListNode* Node4 = new ListNode(3);
    67.  
    68.     Node1->next = Node2;
    69.     Node2->next = Node3;
    70.     Node3->next = Node4;
    71.  
    72.     Solution S1;
    73.     ListNode* res = S1.sortList(Node1);
    74.     while(res != nullptr){
    75.         std::cout << res->val << " ";
    76.         res = res->next;
    77.     }
    78. 	return 0;
    79. }

    4--乘积最大子数组（152）

    主要思路：

            基于动态规划，dp_max[i] 和 dp_min[i] 分别表示以坐标 i 结尾的连续子数组和的最大值和最小值；

            状态转移方程：dp_max[i]  = std::max(dp_max[i-1] * nums[i], dp_min[i-1] * nums[i], nums[i])；dp_min[i]  = std::min(dp_max[i-1] * nums[i], dp_min[i-1] * nums[i], nums[i])；

            之所以使用 dp_min[i]，是由于会出现负数的情况，当负负得正时会出现更大的连续和，因此要考虑 dp_min[i]；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProduct(std::vector<int>& nums) {
    7.         std::vector<int> dp_max(nums.size(), 0), dp_min(nums.size(), 0);
    8.         dp_max[0] = dp_min[0] = nums[0];
    9.         int max = dp_max[0];
    10.         for(int i = 1; i < nums.size(); i++){
    11.             dp_max[i] = std::max(std::max(dp_max[i-1] * nums[i], dp_min[i-1] * nums[i]), nums[i]);
    12.             dp_min[i] = std::min(std::min(dp_max[i-1] * nums[i], dp_min[i-1] * nums[i]), nums[i]);
    13.             max = std::max(max, dp_max[i]);
    14.         }
    15.         return max;
    16.     }
    17. };
    18.  
    19. int main(int argc, char argv[]){
    20.     // nums = [2, 3, -2, 4]
    21.     std::vector<int> test = {2, 3, -2, 4};
    22.     Solution S1;
    23.     int res = S1.maxProduct(test);
    24.     std::cout << res << std::endl;
    25.     return 0;
    26. }

    5--最小栈（155）

    主要思路：

            使用一个辅助栈，记录截止到当前元素的最小值。

    1. #include 
    2. #include 
    3.  
    4. class MinStack{
    5. public:
    6.     MinStack(){}
    7.     
    8.     void push(int val){
    9.         stk1.push(val);
    10.         if(stk2.empty() || val <= stk2.top()){
    11.             stk2.push(val);
    12.         }
    13.     }
    14.     
    15.     void pop(){
    16.         int top = stk1.top();
    17.         stk1.pop();
    18.         if(top == stk2.top()) stk2.pop();
    19.     }
    20.     
    21.     int top(){
    22.         return stk1.top();
    23.     }
    24.     
    25.     int getMin() {
    26.         return stk2.top();
    27.     }
    28. private: 
    29.     std::stack<int> stk1, stk2;
    30. };
    31.  
    32. int main(int argc, char argv[]){
    33.  
    34.     return 0;
    35. }

    6--相交链表（160）

    主要思路：

            走过自己的路，再走你走过的路，要么在相交的节点相遇，要么都是 nullptr；

            非常有哲学意义的一道题！！！！！

    1. #include 
    2. #include 
    3.  
    4. struct ListNode{
    5.     int val;
    6.     ListNode *next;
    7.     ListNode(int x) : val(x), next(NULL) {}
    8. };
    9.  
    10. class Solution{
    11. public:
    12.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    13.         if(headA == nullptr || headB == nullptr){
    14.             return nullptr;
    15.         }
    16.  
    17.         ListNode* tmp1 = headA, *tmp2 = headB;
    18.         while(tmp1 != tmp2){
    19.             tmp1 = tmp1->next;
    20.             tmp2 = tmp2->next;
    21.             if(tmp1 == tmp2) break; // 相遇或同时为null
    22.             if(tmp1 == nullptr) tmp1 = headB;
    23.             if(tmp2 == nullptr) tmp2 = headA;
    24.         }        
    25.         if(tmp1 == nullptr) return nullptr;
    26.         return tmp1;
    27.     }
    28. };
    29.  
    30. int main(int argc, char argv[]){
    31.     // intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
    32.     ListNode *Node1 = new ListNode(4);
    33.     ListNode *Node2 = new ListNode(1);
    34.     ListNode *Node3 = new ListNode(8);
    35.     ListNode *Node4 = new ListNode(4);
    36.     ListNode *Node5 = new ListNode(5);
    37.     Node1->next = Node2;
    38.     Node2->next = Node3;
    39.     Node3->next = Node4;
    40.     Node4->next = Node5;
    41.  
    42.     ListNode *Node6 = new ListNode(5);
    43.     ListNode *Node7 = new ListNode(6);
    44.     ListNode *Node8 = new ListNode(1);
    45.     Node6->next = Node7;
    46.     Node7->next = Node8;
    47.     Node8->next = Node3;
    48.  
    49.     Solution S1;
    50.     ListNode* res = S1.getIntersectionNode(Node1, Node6);
    51.     if(res != nullptr) std::cout << res->val << std::endl;
    52.     else std::cout << "null" << std::endl;
    53.  
    54.     return 0;
    55. }

    7--多数元素（169）

    主要思路：

            假设有一个桶，当一个桶为空时，放入一个新的元素；当一个桶不为空时，当准备放入一个新的元素时，如果新的元素与桶内的元素不相同，则不放入这个新元素且将桶内的一个元素拿出来；

            对于本题，最后桶剩下的元素肯定是多数元素，因为题目规定多数元素必定存在；具体到本题可以用一个计数器表示桶内的元素个数，当计数器为空时可以随意放入新的元素；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int majorityElement(std::vector<int>& nums) {
    7.         int count = 0, val = nums[0]; // count 表示桶内元素的个数， val表示桶内的元素值
    8.         for(int num : nums){
    9.             if(num == val) count++;
    10.             else{
    11.                 if(count == 0){ // 桶为空
    12.                     val = num;
    13.                     count = 1;
    14.                 }
    15.                 else{ // 桶不为空，抵消一个元素
    16.                     count--;
    17.                 }
    18.             }
    19.         }
    20.         return val;
    21.     }
    22. };
    23.  
    24. int main(int argc, char argv[]){
    25.     // nums = [3,2,3]
    26.     std::vector<int> test = {3, 2, 3};
    27.     Solution S1;
    28.     int res = S1.majorityElement(test);
    29.     std::cout << res << std::endl;
    30.     return 0;
    31. }

    8--打家劫舍（198）

    主要思路：

            访问到第i间房屋时，设dp[i][0]表示打劫第i间房屋，dp[i][1]表示不打劫第i间房屋，能够获得的最高金额；

            状态转移方程 dp[i][0] = dp[i-1][1] + nums[i]，dp[i][1] = dp[i-1][0]; 

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int rob(std::vector<int>& nums) {
    7.         std::vectorint>> dp(nums.size(), std::vector<int>(2, 0));
    8.         // 初始化
    9.         dp[0][0] = nums[0];
    10.         dp[0][1] = 0;
    11.         for(int i = 1; i < nums.size(); i++){
    12.             dp[i][0] = dp[i-1][1] + nums[i]; // 打劫房屋i，前一间房屋只能不被打劫
    13.             dp[i][1] = std::max(dp[i-1][0], dp[i-1][1]); // 不打劫房屋i，前一间房屋可以被打劫也可以不被打劫
    14.         }
    15.         return std::max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    16.     }
    17. };
    18.  
    19. int main(int argc, char *argv[]) {
    20.     std::vector<int> test = {1, 2, 3, 1};
    21.     Solution S1;
    22.     int res = S1.rob(test);
    23.     std::cout << res << std::endl;
    24.     return 0;
    25. }

    9--岛屿数量（200）

    主要思路：

            深度优先搜索，从(i, j)出发，递归搜索上下左右四个方向的陆地，将相连的陆地置为0；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int numIslands(std::vectorchar>>& grid) {
    7.         int m = grid.size(), n = grid[0].size();
    8.         int res = 0;
    9.         for(int i = 0; i < m; i++){
    10.             for(int j = 0; j < n; j++){
    11.                 if(grid[i][j] == '1'){
    12.                     res++;
    13.                     dfs(grid, i, j);
    14.                 }
    15.             }
    16.         }
    17.         return res;
    18.     }
    19.  
    20.     void dfs(std::vectorchar>>& grid, int i, int j){
    21.         if(i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0' || i < 0 || j < 0) return;
    22.         grid[i][j] = '0';
    23.         dfs(grid, i+1, j);
    24.         dfs(grid, i, j+1);
    25.         dfs(grid, i-1, j);
    26.         dfs(grid, i, j-1);
    27.     }
    28. };
    29.  
    30. int main(int argc, char *argv[]) {
    31.     std::vectorchar>> test = {{'1', '1', '0', '0', '0'}, 
    32.                                            {'1', '1', '0', '0', '0'},
    33.                                            {'0', '0', '1', '0', '0'},
    34.                                            {'0', '0', '0', '1', '1'}};
    35.     Solution S1;
    36.     int res = S1.numIslands(test);
    37.     std::cout << res << std::endl;
    38.     return 0;
    39. }

    10--反转链表（206）

    主要思路：

            头插法，使用虚拟头节点。

    1. #include 
    2.  
    3. struct ListNode {
    4.     int val;
    5.     ListNode *next;
    6.     ListNode() : val(0), next(nullptr) {}
    7.     ListNode(int x) : val(x), next(nullptr) {}
    8.     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. };
    10.  
    11. class Solution {
    12. public:
    13.     ListNode* reverseList(ListNode* head) {
    14.         if(head == nullptr) return nullptr;
    15.         ListNode* FHead = new ListNode(-1); // 虚拟头节点
    16.         FHead->next = head;
    17.         ListNode* tmp = head->next;
    18.         head->next= nullptr;
    19.         while(tmp != nullptr){
    20.             ListNode* next = tmp->next; // 记录下一个结点
    21.             // 头插
    22.             tmp->next = FHead->next;
    23.             FHead->next = tmp;
    24.             // 更新
    25.             tmp = next;
    26.         }
    27.         return FHead->next;
    28.     }
    29. };
    30.  
    31. int main(int argc, char *argv[]) {
    32.     ListNode *Node1 = new ListNode(1);
    33.     ListNode *Node2 = new ListNode(2);
    34.     ListNode *Node3 = new ListNode(3);
    35.     ListNode *Node4 = new ListNode(4);
    36.     ListNode *Node5 = new ListNode(5);
    37.  
    38.     Node1->next = Node2;
    39.     Node2->next = Node3;
    40.     Node3->next = Node4;
    41.     Node4->next = Node5;
    42.  
    43.     Solution S1;
    44.     ListNode *res = S1.reverseList(Node1);
    45.     ListNode *tmp = res;
    46.     while(tmp != nullptr){
    47.         std::cout << tmp->val << " ";
    48.         tmp = tmp->next;
    49.     }
    50.     return 0;
    51. }

  • 相关阅读:
    软件测试——从0开始的ios自动化测试(二)
    夏令时及java中常用方法
    Spring boot 实践Rabbitmq消息防丢失
    【RuoYi移动端】uni-app中的单击和双击事件
    使用神经网络实现对天气的预测
    java项目_第166期ssm多人命题系统_java毕业设计_计算机毕业设计
    基于主动视觉机制的深度学习--一个综合池化框架
    【前端学习记录】neffos插件与控制台交互
    R数据分析：用R建立预测模型
    1.什么是Angular?
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/133248745