LeetCode HOT 100 --- 2021/7/29

た入场券 2022-09-01 14:58 136阅读 0赞

### 目录 ###

*  两数相加
 *  无重复字符的最长子串
 *  最长回文子串
 *  盛最多水的容器
 *  三数之和
 *  下一个排列
 *  搜索旋转排序数组

# 两数相加 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  十进制的加法。  
代码：

/** * 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* addTwoNumbers(ListNode* l1, ListNode* l2) { 
            ListNode *head = nullptr, *tail = nullptr;
            int carry = 0;
            while (l1 || l2) { 
                int n1 = l1 ? l1->val: 0;
                int n2 = l2 ? l2->val: 0;
                int sum = n1 + n2 + carry;
                if (!head) { 
                    head = tail = new ListNode(sum % 10);
                } else { 
                    tail->next = new ListNode(sum % 10);
                    tail = tail->next;
                }
                carry = sum / 10;
                if (l1) { 
                    l1 = l1->next;
                }
                if (l2) { 
                    l2 = l2->next;
                }
            }
            if (carry > 0) { 
                tail->next = new ListNode(carry);
            }
            return head;
        }
    };

# 无重复字符的最长子串 #

[剑指 Offer 48. 最长不含重复字符的子字符串][Offer 48.]

# 最长回文子串 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
方法一：  
  暴力求解：超时。  
代码：

class Solution { 
    public:
        string longestPalindrome(string s) { 
            int n = s.size();
            int maxLen = 0;
            string res = "";
            for(int i = 0; i < n; i++) { 
                for(int j = 0; j <= n - i; j++) { 
                    string sub = s.substr(i, j);
                    string temp = sub;
                    reverse(sub.begin(), sub.end());
                    if(temp == sub && temp.size() > maxLen) { 
                        maxLen = temp.size();
                        res = temp;
                    }
                }
            }
            return res;
        }
    };

方法二：  
  动态规划：设dp\[i\]\[j\]为true表示s\[i…j\]是一个回文串。  
  边界条件：

dp[i][i] = true;
    if s[i] == s[i + 1] then dp[i][i + 1] = true;

状态转移方程：

if dp[i + 1][j - 1] && s[i] == s[j] then dp[i][j] = true;

代码：

class Solution { 
    public:
        string longestPalindrome(string s) { 
            int n = s.size();
            vector<vector<bool>> dp(n, vector<bool>(n, false));
            string res = "";
            res += s[0];
            int maxLen = 1;
            //边界条件
            for(int i = 0; i < n; i++) { 
                dp[i][i] = true;
                if(i + 1 < n && s[i] == s[i + 1]) { 
                    dp[i][i + 1] = true;
                    maxLen = 2;
                    res = s.substr(i, 2);
                }
            }
            //转移方程，注意这里要从中心向外扩展
            for(int i = n - 1; i >= 0; i--) { 
                for(int j = i + 2; j < n; j++) { 
                    if(dp[i + 1][j - 1] && (s[i] == s[j])) { 
                        dp[i][j] = true;
                        if(j - i + 1 > maxLen) { 
                            res = s.substr(i, j - i + 1);;
                            maxLen = j - i + 1;
                        }
                    }   
                }
            }
            return res;
        }
    };

# 盛最多水的容器 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
分析：  
  依次枚举，枚举过程中保存最大值。设置两个指针，初始时分别指向两端。如果当前height\[l\] <= height\[r\]，那么我们只能移动较小的左指针，因为容器体积 = (r - l) \* min(height\[l\], height\[r\])，如果移动右指针，最小值可能不会变（也可能增加），距离减小，体积也会减小，所以我们移动左指针。同理，当height\[l\] > height\[r\]时移动右指针。  
代码：

class Solution { 
    public:
        int maxArea(vector<int>& height) { 
            int l = 0, r = height.size() - 1;
            int ans = 0;
            while(l < r) { 
                int x = (r - l) * min(height[l], height[r]);
                ans = max(ans, x);
                if(height[l] <= height[r]) { 
                    l++;
                }else { 
                    r--;
                }
            }
            return ans;
        }
    };

# 三数之和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]  
分析：  
  首先将数组进行排序。枚举第一个数，随后在其右侧区间利用二分法查找剩余的两个数，注意会有重复。  
代码：

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) 
        { 
            int n = nums.size();
            if(n < 3) { 
                return { };
            }
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            for(int i = 0; i < n; i++) { 
                if(nums[i] > 0) { 
                    continue;
                }
                if(i > 0 && nums[i] == nums[i - 1]) { 
                    continue;
                }
                int left = i + 1, right = n - 1;
                while(left < right) { 
                    if(nums[left] + nums[right] > -nums[i]) { 
                        right--;
                    }else if(nums[left] + nums[right] < -nums[i]) { 
                        left++;
                    }else { 
                        res.push_back({ nums[i], nums[left], nums[right]});
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left - 1]) { 
                            left++;
                        }
                        while(left < right && nums[right] == nums[right + 1]) { 
                            right--;
                        }
                    }
                }
            }
            return res;
        }
    };

# 下一个排列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
方法一：  
  利用c++封装好的next\_permutation。  
代码：

class Solution { 
    public:
        void nextPermutation(vector<int>& nums) { 
            if(next_permutation(nums.begin(), nums.end())) { 
                //do nothing
            }else { 
                sort(nums.begin(), nums.end());
            }
        }
    };

方法二：  
  参考官方题解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]  
代码：

class Solution { 
    public:
        void nextPermutation(vector<int>& nums) { 
            int i = nums.size() - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) { 
                i--;
            }
            if (i >= 0) { 
                int j = nums.size() - 1;
                while (j >= 0 && nums[i] >= nums[j]) { 
                    j--;
                }
                swap(nums[i], nums[j]);
            }
            reverse(nums.begin() + i + 1, nums.end());
        }
    };

# 搜索旋转排序数组 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]  
分析：  
  对一个数组，其左边部分是升序的，右边部分也是升序的，但是总体不一定升序，并且左半部分比右半部分大。比如9, 11, 12, 13, 1, 2, 3。对于此种“伪有序”的数组，也可以使用二分法查找，具体方法如下：  
  初始令l和r指向数组两端，如果当前nums\[mid\] == target，则返回；如果nums\[0\] <= nums\[mid\]，说明mid当前在左半边，进一步如果nums\[0\] <= target && target <= nums\[mid\]，则说明target在左半边的某个位置，执行r = mid - 1，否则l = mid + 1；如果nums\[0\] > nums\[mid\]，说明mid在右半部分的升序序列里面，进一步如果nums\[mid\] <= target && target <= nums\[n\]，说明target还在mid左边，执行r = mid - 1，否则执行l = mid + 1。  
代码：

class Solution { 
    public:
        int search(vector<int>& nums, int target) { 
            if (nums.size() == 0) { 
                return -1;
            }
            int n = nums.size() - 1;
            if (n == 0) { 
                return nums[0] == target ? 0 : -1;
            }
            int l = 0, r = n;
            while (l <= r) { 
                int mid = l + (r - l) / 2;
                if (nums[mid] == target) { 
                    return mid;
                }
                if (nums[0] <= nums[mid]) { 
                    // 左半边有序
                    if (nums[0] <= target && target <= nums[mid]) { 
                    // target的值在左半边
                        r = mid - 1;
                    }
                    else { 
                        l = mid + 1;
                    }
                }
                else { 
                    // 右半边有序
                    if (nums[mid] <= target && target <= nums[n]) { 
                    // target的值在右半边
                        l = mid + 1;
                    }
                    else { 
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/0e9d646375684f25a3d57765b3c91ef4.png
[Offer 48.]: https://blog.csdn.net/Cyril_KI/article/details/119064860
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/fd6d8093727d4007b32711c1e23641fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/49ac4a84d2f7448fbecca8163716ac10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/51d15e5d34854ca18fcf945c2ce7fd73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20220829/d872c40e61024c4fb157363ba8be8354.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]: /images/20220829/f9a8d9780bf44b31a167e381c4511b39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]: /images/20220829/67b7cd467abe45e587c37c470de19979.png