Leetcode-其他题目

Leetcode-其他题目

回溯

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的括号组合。

class Solution {
public:
    vector<string> result;
    void backtracking(vector<string> temp, int n, int nowleft, int nowright){
        if(temp.size() == n * 2){
            string res = "";
            for(int i=0;i<temp.size();i++){
                res += temp[i];
            }
            result.push_back(res);
            return;
        }
        if (nowleft < n){
            temp.push_back("(");
            backtracking(temp,n,nowleft+1,nowright);
            temp.pop_back();
        }
        if(nowright < n && nowright < nowleft){
            temp.push_back(")");
            backtracking(temp,n,nowleft,nowright+1);
            temp.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> temp;
        backtracking(temp,n,0,0);
        return result;
    }
};

31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int index = n-1;
        for(;index>=1;index--){
            if(nums[index] > nums[index-1]){
                break;
            }
        }
        if(index != 0){
            index -= 1;
            for(int i=n-1;i>=0;i--){
                if(nums[i] > nums[index]){
                    swap(nums[index], nums[i]);
                    reverse(nums.begin()+index+1,nums.end());
                    return;
                }
            }
        }
        else{
            reverse(nums.begin(), nums.end());
        }
    }
};

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution {
public:
    bool result = false;
    void DFS(int i, int j, int m, int n,int now, vector<vector<char>>& board,vector<vector<bool> > &visited,  string word){
        if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] == true || board[i][j] != word[now]){
            return;
        }
        if(now == word.size() - 1){
            result = true;
            return;
        }
        visited[i][j] = true;
        DFS(i+1,j,m,n,now+1,board,visited, word);
        DFS(i-1,j,m,n,now+1,board,visited, word);
        DFS(i,j+1,m,n,now+1,board,visited, word);
        DFS(i,j-1,m,n,now+1,board,visited, word);
        visited[i][j] = false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                vector<vector<bool> > visited(m, vector<bool>(n, false));
                DFS(i,j,m,n,0,board,visited, word);
                if(result){
                    return result;
                }
            }
        }
        return result;
    }
};

二叉树

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

class Solution {
public:
    vector<int> result;
    void inorder(TreeNode* root){
        if(root == NULL){
            return;
        }
        inorder(root->left);
        result.push_back(root->val);
        inorder(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root);
        return result;
    }
};

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

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int> > result;
        if(root == NULL){
            return result;
        }
        queue<TreeNode*> q;
        q.push(root);
        int sign = 0;
        while(!q.empty()){
            int t = q.size();
            vector<int> temp;
            for(int i=0;i<t;i++){
                TreeNode* x = q.front();
                q.pop();
                temp.push_back(x->val);
                if(x->left != NULL){
                    q.push(x->left);
                }
                if(x->right != NULL){
                    q.push(x->right);
                }
            }
            if(sign == 1){
                reverse(temp.begin(), temp.end());
            }
            result.push_back(temp);
            sign = 1 - sign;
        }
        return result;
    }
};

动态规划

64. 最小路径和

给定一个包含非负整数的 <em>m</em> x <em>n</em> 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > dp(m, vector<int>(n,0));
        dp[0][0] = grid[0][0];
        for(int i=1;i<m;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

数组

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2<sup>31</sup>,  2<sup>31 </sup>− 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
};

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 <strong>k</strong> 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
public:
    void quicksort(vector<int>& nums, int start, int end, int k){
        if(start >= end){
            return;
        }
        int x = nums[start];
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && nums[right] <= x){
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] > x){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = x;
        // start    left    end   
        // k
        if(k == left + 1){
            return;
        } else if(k < left+1){
            quicksort(nums, start, left-1,k);
        } else{
            quicksort(nums,left+1,end,k);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        quicksort(nums, 0, nums.size()-1,k);
        return nums[k-1];
    }
};

347. 前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

class Solution {
public:
    void quicksort(vector<pair<int,int> >& nums, int start, int end, int k){
        if(start >= end){
            return;
        }
        pair<int,int> x = nums[start];
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && nums[right].second <= x.second){
                right--;
            }
            swap(nums[left],nums[right]);
            while(left < right && nums[left].second > x.second){
                left++;
            }
            swap(nums[left],nums[right]);
        }
        nums[left].first = x.first;
        nums[left].second = x.second;
        // start  left  end;
        if(k == left){
            return;
        } else if(k > left){
            quicksort(nums, left+1, end,k);
        } else{
            quicksort(nums, start, left-1,k);
        }

    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<pair<int, int> > result;
        unordered_map<int, int> mp;
        for(int i=0;i<nums.size();i++){
            mp[nums[i]]++;
        }
        for(auto it=mp.begin();it!= mp.end();it++){
            result.push_back({it->first, it->second});
        }
        quicksort(result, 0, result.size()-1,k);
        vector<int> res;
        for(int i=0;i<k;i++){
            res.push_back(result[i].first);
        }
        return res;
    }
};

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<bool> visit(s.size(),false);
        stack<pair<char,int> > st;
        for(int i=0;i<s.size();i++){
            if(st.empty() || s[i] == '(' || (s[i] == ')' && st.top().first == ')')){
                st.push({s[i],i});
                continue;
            }
            for(int j=st.top().second;j<=i;j++){
                visit[j] = true;
            }
            st.pop();
        }
        int maxlength = 0;
        int index = 0;
        while(index < visit.size()){
            int counttemp = 0;
            while(index < visit.size() && visit[index]){
                counttemp += 1;
                index += 1;
            }
            maxlength = max(maxlength, counttemp);
            while(index < visit.size() && !visit[index]){
                index += 1;
            }
        }
        return maxlength;
    }
};

2570. 合并两个二维数组 - 求和法

给你两个 二维 整数数组 nums1 和 nums2.

  • nums1[i] = [id<sub>i</sub>, val<sub>i</sub>] 表示编号为 id<sub>i</sub> 的数字对应的值等于 val<sub>i</sub> 。
  • nums2[i] = [id<sub>i</sub>, val<sub>i</sub>] 表示编号为 id<sub>i</sub> 的数字对应的值等于 val<sub>i</sub> 。

每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。

请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：

  • 只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
  • 每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则认为其对应的值等于 0 。

返回结果数组。返回的数组需要按 id 以递增顺序排列。

class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b){
        return a[0] < b[0];
    }
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        unordered_map<int, int> mp;
        for(int i=0;i<nums1.size();i++){
            if(mp.find(nums1[i][0]) != mp.end()){
                mp[nums1[i][0]] += nums1[i][1];
            } else{
                mp[nums1[i][0]] = nums1[i][1];
            }
        }
        for(int i=0;i<nums2.size();i++){
            if(mp.find(nums2[i][0]) != mp.end()){
                mp[nums2[i][0]] += nums2[i][1];
            } else{
                mp[nums2[i][0]] = nums2[i][1];
            }
        }
        vector<vector<int> > result;
        for(auto it = mp.begin(); it != mp.end();it++){
            result.push_back(vector<int> {it->first, it->second});
        }
        sort(result.begin(), result.end(), cmp);
        return result;
    }
};

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

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

48. 旋转图像

给定一个 *n * × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。**请不要 **使用另一个矩阵来旋转图像。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i=0;i< n / 2;i++){
            for(int j=0;j<(n+1) / 2;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-j-1][i];
                matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                matrix[j][n-i-1] = temp;
            }
        }
    }
};

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i] == 0){
                swap(nums[i], nums[left]);
                left += 1;
            }
        }
        for(int i=left;i<nums.size();i++){
            if(nums[i] == 1){
                swap(nums[i], nums[left]);
                left += 1;
            }
        }
    }
};

73. 矩阵置零

给定一个 <em>m</em> x <em>n</em> 的矩阵，如果一个元素为 0 ** ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。**

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> rowvector(m,false);
        vector<bool> colvector(n,false);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] == 0){
                    rowvector[i] = true;
                    colvector[j] = true;
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(rowvector[i] == true || colvector[j] == true){
                    matrix[i][j] = 0;
                }
            }
        }
        return;
    }
};

118. 杨辉三角

给定一个非负整数 numRows， 生成「杨辉三角」的前 *numRows *行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > result;
        vector<int> temp;
        temp.push_back(1);
        result.push_back(temp);
        if(numRows == 1){
            return result;
        }
        for(int i=2;i<=numRows;i++){
            vector<int> t;
            t.push_back(1);
            for(int j=1;j<i-1;j++){
                t.push_back(result[i-2][j-1] + result[i-2][j]);
            }
            t.push_back(1);
            result.push_back(t);
        }
        return result;
    }
};

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：* 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]

  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int right = n-1;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] < nums[right]){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
};

链表

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int cur = 0;
        ListNode* head = new ListNode(-1);
        ListNode* l3 = head;
        while(l1 != NULL || l2 != NULL){
            int target;
            if(l1 == NULL){
                target = l2->val + cur;
                l2 = l2->next;
            } else if(l2 == NULL){
                target = l1->val + cur;
                l1 = l1->next;
            } else{
                target = l1->val + l2->val + cur;
                l1 = l1->next;
                l2 = l2->next;
            }
            if (target >= 10){
                cur = 1;
                target -= 10;
            } else{
                cur = 0;
            }
            l3->next = new ListNode(target);
            l3 = l3->next;
        }
        if(cur == 1){
            l3->next = new ListNode(1);
        }
        return head->next;
    }
};

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* head = dummy;
        while(list1 != NULL && list2 != NULL){
            if(list1->val < list2->val){
                dummy->next = list1;
                dummy = dummy->next;
                list1 = list1->next;
            } else{
                dummy->next = list2;
                dummy = dummy->next;
                list2 = list2->next;
            }
        }
        if(list1 != NULL){
            dummy->next = list1;
        }
        if(list2 != NULL){
            dummy->next = list2;
        }
        return head->next;
    }
};

哈希表

字符串

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1){
            return s;
        }
        vector<queue<char> > vt(numRows);
        int nowindex = 0;
        int reverse = false;
        for(int i=0;i<s.size();i++){
            vt[nowindex].push(s[i]);
            if(nowindex == 0 && reverse == true){
                reverse = false;
                nowindex += 1;
            } else if (nowindex == numRows-1 && reverse == false){
                reverse = true;
                nowindex -= 1;
            } else {
                if(reverse == false){
                    nowindex += 1;
                } else{
                    nowindex -= 1;
                }
            }
        }
        string resultstring = "";
        for(int i=0;i<vt.size();i++){
            while(!vt[i].empty()){
                resultstring += vt[i].front();
                vt[i].pop();
            }
        }
        return resultstring;
    }
};

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  5. 如果整数数超过 32 位有符号整数范围 [−2<sup>31</sup>,  2<sup>31 </sup>− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2<sup>31</sup> 的整数应该被固定为 −2<sup>31</sup> ，大于 2<sup>31 </sup>− 1 的整数应该被固定为 2<sup>31 </sup>− 1 。
  6. 返回整数作为最终结果。

注意：

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
class Solution {
public:
    int myAtoi(string s) {
        int res = 0;
        bool havenumsign = false;
        bool negativesign = false;
        bool fakebigsign = false;
        for(int i=0;i<s.size();i++){
            if(s[i] == ' ' && havenumsign == false){
                continue;
            }
            if(s[i] == '-' && havenumsign == false){
                negativesign = true;
                havenumsign = true;
                continue;
            }
            if(s[i] == '+' && havenumsign == false){
                havenumsign = true;
                continue;
            }
            if(s[i] >= '0' && s[i] <= '9'){
                havenumsign = true;
                if(res > (INT_MAX - s[i] + '0') / 10){
                    res = INT_MAX;
                    fakebigsign = true;
                    break;
                }
                res = res * 10 - '0' + s[i];
                continue;
            }
            if(havenumsign == true){
                break;
            }
            break;
        }
        if (negativesign){
            if(res == INT_MAX && fakebigsign){
                return INT_MIN;
            }
            return -res;
        }
        return res;
    }
};

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

class Solution
{
public:
    string intToRoman(int num)
    {
        pair<int, string> valueSymbols[] = {
            {1000, "M"},
            {900, "CM"},
            {500, "D"},
            {400, "CD"},
            {100, "C"},
            {90, "XC"},
            {50, "L"},
            {40, "XL"},
            {10, "X"},
            {9, "IX"},
            {5, "V"},
            {4, "IV"},
            {1, "I"},
        };
        string roman;
        for (auto &[value, symbol] : valueSymbols)
        {
            while (num >= value)
            {
                num -= value;
                roman += symbol;
            }
            if (num == 0)
            {
                break;
            }
        }
        return roman;
    }
};

图论

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] ，表示如果要学习课程 a<sub>i</sub> 则 必须 先学习课程 b<sub>i</sub> ~ ~ 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> totalnum(numCourses,0);
        vector<vector<int> > matrix(numCourses, vector<int>(0,0));
        for(int i=0;i<prerequisites.size();i++){
            totalnum[prerequisites[i][0]] += 1;
            matrix[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        bool judge = true;
        while(judge){
            judge = false;
            for(int i=0;i<numCourses;i++){
                if(totalnum[i] == 0){
                    judge = true;
                    for(int j=0;j<matrix[i].size();j++){
                        totalnum[matrix[i][j]] -= 1;
                    }
                    totalnum[i] = -1;
                }
            }
        }
        for(int i=0;i<numCourses;i++){
            if(totalnum[i] != -1){
                return false;
            }
        }
        return true;
    }
};

栈与队列

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10<sup>-5</sup> 以内的答案将被接受。
class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;

    MedianFinder() {
  
    }
  
    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }
  
    double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0; 
    }
};

双指针法

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int result = 0;
        unordered_set<char> st;
        int left = 0;
        for(int right=0; right<s.size(); right++){
            while(st.find(s[right]) != st.end()){
                st.erase(s[left]);
                left++;
            }
            st.insert(s[right]);
            result = max(result, right - left + 1);
        }
        return result;
    }
};

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        bool next;
        int sign = (m + n) / 2; 
        if((m + n) % 2 == 1){
            next = false;
        } else{
            sign -= 1;
            next = true;
        }
        int res1 = 0;
        int res2 = 0;
        int globalindex = 0;
        int nums1index = 0;
        int nums2index = 0;
        while(globalindex <= sign){
            if(nums1index < m && nums2index < n){
                if(nums1[nums1index] < nums2[nums2index]){
                    res1 = nums1[nums1index];
                    nums1index += 1;
                } else{
                    res1 = nums2[nums2index];
                    nums2index += 1;
                }
            } else if (nums1index < m){
                res1 = nums1[nums1index];
                nums1index += 1;
            } else {
                res1 = nums2[nums2index];
                nums2index += 1;
            }
            globalindex += 1;
        }
        if(next == false){
            return res1;
        }
        if(nums1index < m && nums2index < n){
            if(nums1[nums1index] < nums2[nums2index]){
                res2 = nums1[nums1index];
            } else{
                res2 = nums2[nums2index];
            }
        } else if (nums1index < m){
            res2 = nums1[nums1index];
        } else {
            res2 = nums2[nums2index];
        }
        return ((double)res1 + (double)res2) / 2.0;
    }
};

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

class Solution {
public:
    string longestPalindrome(string s) {
        vector<int> result = {0,0};
        for(int i=0;i<s.size()-1;i++){
            int left = i;
            int right = i;
            while(left >= 0 && right < s.size()){
                if(s[left] == s[right]){
                    if(result[1] - result[0] < right - left){
                        result[1] = right;
                        result[0] = left;
                    }
                    right += 1;
                    left -= 1;
                } else{
                    break;
                }
            }
            left = i;
            right = i+1;
            while(left >= 0 && right < s.size()){
                if(s[left] == s[right]){
                    if(result[1] - result[0] < right - left){
                        result[1] = right;
                        result[0] = left;
                    }
                    right += 1;
                    left -= 1;
                } else{
                    break;
                }
            }
        }
        return s.substr(result[0], result[1]-result[0] + 1);
    }
};

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。
class Solution {
public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        int left = 0;
        int right = s.size() - 1;
        while(left < right){
            if(s[left] != s[right]){
                return false;
            }
            left += 1;
            right -= 1;
        }
        return true;
    }
};

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

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

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index = m + n - 1;
        m -= 1;
        n -= 1;
        while(index >= 0){
            if(m < 0){
                nums1[index] = nums2[n];
                n--;
            } else if (n < 0){
                nums1[index] = nums1[m];
                m--;
            } else{
                if(nums1[m] > nums2[n]){
                    nums1[index] = nums1[m];
                    m--;
                } else{
                    nums1[index] = nums2[n];
                    n--;
                }
            }
            index--;
        }
        return;
    }
};

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

class Solution {
public:
    ListNode* merge(vector<ListNode*>& lists, int start, int end){
        if(start > end){
            return NULL;
        }
        if(start == end){
            return lists[start];
        }
        int mid = (end - start) / 2 + start;
        ListNode* first = merge(lists, start, mid);
        ListNode* second = merge(lists, mid + 1, end);
        if(first == NULL){
            return second;
        }
        if(second == NULL){
            return first;
        }
        ListNode* head = new ListNode(0);
        ListNode* p = head;
        while(first != NULL && second != NULL){
            if(first->val < second->val){
                p->next = first;
                first = first->next;
            } else{
                p->next = second;
                second = second->next;
            }
            p = p->next;
        }
        if(first != NULL){
            p->next = first;
        } else{
            p->next = second;
        }
        return head->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size()-1);
    }
};
Study
#Algorithm #C++ #Leetcode
Leetcode-其他题目
https://zhangzhao219.github.io/2024/04/14/Leetcode/Leetcode-others/
作者
Zhang Zhao
发布于
2024年4月14日
许可协议