备案控制台
开发者社区 人工智能 文章 正文

Leetcode hot100题 个人整理版（三）

2023-02-22 59
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Leetcode hot100题 个人整理版

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

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

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

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

class Solution {
public:
    int quick_selection(vector<int>& nums,int l,int r,int k){
        if (l==r)
            return nums[k];
        int x=nums[l];
        int i=l-1,j=r+1;
        while(i<j){
            do i++;while(nums[i]<x);
            do j--;while(nums[j]>x);
            if (i<j)
                swap(nums[i],nums[j]);
        }
        if (k<=j)
            return quick_selection(nums,l,j,k);
        else return quick_selection(nums,j+1,r,k);
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quick_selection(nums,0,nums.size()-1,nums.size()-k);
    }
};

221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n=matrix.size();
        int m=matrix[0].size();
        int res=0;
        vector<vector<int>> f(n,vector<int>(m,0));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if (i==j&&i==0)
                    f[i][j]=matrix[i][j]-'0';
                else if (i==0||j==0)
                    f[i][j]=matrix[i][j]-'0';
                else if (matrix[i][j]=='1')
                    f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
                res=max(res,f[i][j]);
            }
        }
        return res*res;
    }
};

226. 翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root==NULL)
            return root;
        if (root->left!=NULL)
            invertTree(root->left);
        if (root->right!=NULL)
            invertTree(root->right);
        swap(root->left,root->right);
        return root;
    }
};

234. 回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> stk;
        ListNode *p=head;
        while(p!=NULL){
            stk.push(p->val);
            p=p->next;
        }
        p=head;
        while(!stk.empty()){
            int t=stk.top();
            stk.pop();
            if (t!=p->val){
                return false;
            }
            p=p->next;
        }
        return true;
    }
};

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树T TT的两个节点 q，最近公共祖先表示为一个节点x，满足x是q的祖先且x xx的深度尽可能大（一个节点也可以是它自己的祖先）。”

class Solution {
public:
    unordered_map<TreeNode *,int> l;
    unordered_map<TreeNode *,TreeNode *>f;
    void dfs(TreeNode *root){
        if (root->left){
            f[root->left]=root;
            l[root->left]=l[root]+1;
            dfs(root->left);
        }
        if (root->right){
            f[root->right]=root;
            l[root->right]=l[root]+1;
            dfs(root->right);
        }
        return;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        f[root]=NULL;
        l[root]=0;
        dfs(root);
        int lp=l[p];
        int lq=l[q];
        while(lp>lq){
            p=f[p];
            lp=l[p];
        }
        while(lq>lp){
            q=f[q];
            lq=l[q];
        }
        while(p!=q){
            p=f[p];
            q=f[q];
        }
        return p;
    }
};

238. 除自身以外数组的乘积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> l(n,1);//左缀
        vector<int> r(n,1);//右缀
        for(int i=1;i<n;i++)
            l[i]=l[i-1]*nums[i-1];
        for(int i=n-2;i>=0;i--)
            r[i]=r[i+1]*nums[i+1];
        vector<int> res(n,1);
        for(int i=0;i<n;i++)
            res[i]=l[i]*r[i];
        return res;
    }
};

239. 滑动窗口最大值

给你一个整数数组snums，有一个大小为k kk的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        int n=nums.size();
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (!dq.empty() && i - k + 1 > dq.front())
                dq.pop_front();
            while (!dq.empty() && nums[dq.back()] <= nums[i])
                dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1)
                ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

240. 搜索二维矩阵 II

编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性：

每行的元素从左到右升序排列。

每列的元素从上到下升序排列。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()||matrix[0].empty())
            return false;
        int n=matrix.size();
        int m=matrix[0].size();
        int i=0,j=m-1;
        while(i<n&&j>=0){
            int t=matrix[i][j];
            if (t==target)
                return true;
            else if (t>target)
                j--;
            else i++;
        }
        return false;
    }
};

279. 完全平方数

给你一个整数n，返回和为n的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n+1,0x3f3f3f3f);
        f[0]=0;
        f[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j*j<=i;j++)
                f[i]=min(f[i],f[i-j*j]+1);
        }
        return f[n];
    }
};

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        int i=0,j=0;
        for(;i<n;i++){
            if (nums[i]!=0){
                nums[j]=nums[i];
                j++;
            }
        }
        for(;j<n;j++)
            nums[j]=0;
    }
};

287. 寻找重复数

给定一个包含n+1个整数的数组snums，其数字都在[1,n] 范围内（包括1和n），可知至少存在一个重复的整数。

假设nums只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组snums且只用常量级O(1)的额外空间。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow=0,fast=0;
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];
        }while(slow!=fast);
        slow=0;
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
};

297. 二叉树的序列化与反序列化

class Codec {
public:
    string path;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        dfs_s(root);
        return path;
    }
    void dfs_s(TreeNode* root) {
        if (!root) path += "#,";
        else {
            path += to_string(root->val) + ',';
            dfs_s(root->left);
            dfs_s(root->right);
        }
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data, u);
    }
    TreeNode* dfs_d(string& data, int& u) {
        if (data[u] == '#') {
            u += 2;
            return NULL;
        } else {
            int k = u;
            while (data[u] != ',') u ++ ;
            auto root = new TreeNode(stoi(data.substr(k, u - k)));
            u ++ ;
            root->left = dfs_d(data, u);
            root->right = dfs_d(data, u);
            return root;
        }
    }
};

301. 删除无效的括号

给你一个由若干括号和字母组成的字符串s，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

class Solution {
public:
    vector<string> ans;
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (auto x: s)
            if (x == '(') l ++ ;
            else if (x == ')') {
                if (l == 0) r ++ ;
                else l -- ;
            }
        dfs(s, 0, "", 0, l, r);
        return ans;
    }
    void dfs(string& s, int u, string path, int cnt, int l, int r) {
        if (u == s.size()) {
            if (!cnt) ans.push_back(path);
            return;
        }
        if (s[u] != '(' && s[u] != ')') dfs(s, u + 1, path + s[u], cnt, l, r);
        else if (s[u] == '(') {
            int k = u;
            while (k < s.size() && s[k] == '(') k ++ ;
            l -= k - u;
            for (int i = k - u; i >= 0; i -- ) {
                if (l >= 0) dfs(s, k, path, cnt, l, r);
                path += '(';
                cnt ++, l ++ ;
            }
        } else if (s[u] == ')') {
            int k = u;
            while (k < s.size() && s[k] == ')') k ++ ;
            r -= k - u;
            for (int i = k - u; i >= 0; i -- ) {
                if (cnt >= 0 && r >= 0) dfs(s, k, path, cnt, l, r);
                path += ')';
                cnt --, r ++ ;
            }
        }
    }
};

309. 最佳买卖股票时机含冷冻期

给定一个整数数组prices，其中prices[i]表示第i ii天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> f(n,vector<int>(3,0));
        f[0][1]=-prices[0];
        int res=0;
        for(int i=1;i<n;i++){
            f[i][0]=max(f[i-1][0],f[i-1][2]);
            f[i][1]=max(f[i-1][0]-prices[i],f[i-1][1]);
            f[i][2]=f[i-1][1]+prices[i];
        }
        return max(f[n-1][0],f[n-1][2]);
    }
};

312. 戳气球

有n个气球，编号为n−1，每个气球上都标有一个数字，这些数字存在数组nums中。

现在要求你戳破所有的气球。戳破第i ii个气球，你可以获得nums[i+1]枚硬币。 这里的i+1代表和i ii相邻的两个气球的序号。如果i−1或i+1超出了数组的边界，那么就当它是一个数字为1的气球。

求所能获得硬币的最大数量。

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        vector<int> a(n+2,1);
        for(int i=0;i<n;i++)
            a[i+1]=nums[i];
        vector<vector<int>> f(n+2,vector<int>(n+2,0));
        for(int len=3;len<=n+2;len++){
            for(int i=0;i+len-1<=n+1;i++){
                int j=i+len-1;
                for(int k=i+1;k<j;k++){
                    f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
                }
            }
        }
        return f[0][n+1];
    }
};

322. 零钱兑换

给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 −1。

你可以认为每种硬币的数量是无限的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(),coins.end());
        vector<int> f(amount+1,0x3f3f3f3f);
        f[0]=0;
        for(int i=1;i<=amount;i++){
            for(int coin:coins){
                if (i>=coin)
                    f[i]=min(f[i],f[i-coin]+1);
            }
        }
        if (f[amount]==0x3f3f3f3f)
            return -1;
        else return f[amount];
    }
};

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

class Solution {
public:
    vector<int> dfs(TreeNode *root){
        if (root==NULL)
            return {0,0};
        vector<int> f(2);
        auto l=dfs(root->left);
        auto r=dfs(root->right);
        f[0]=max(l[0],l[1])+max(r[0],r[1]);
        f[1]=l[0]+r[0]+root->val;
        return f;
    }
    int rob(TreeNode* root) {
        auto f=dfs(root);
        return max(f[0],f[1]);
    }
};

338. 比特位计数

给你一个整数n ，对于i<=n中的每个i，计算其二进制表示中 1 的个数 ，返回一个长度为n+1的数组ans作为答案。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> f(n+1);
        for(int i=1;i<=n;i++){
            f[i]=f[i>>1]+(i&1);
        }
        return f;
    }
};

347. 前 K 个高频元素

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

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (auto x: nums) cnt[x] ++ ;
        int n = nums.size();
        vector<int> s(n + 1);
        for (auto [x, c]: cnt) s[c] ++ ;
        int i = n, t = 0;
        while (t < k) t += s[i -- ];
        vector<int> res;
        for (auto [x, c]: cnt)
            if (c > i)
                res.push_back(x);
        return res;
    }
};

394. 字符串解码

class Solution {
public:
    string decodeString(string s) {
        int u = 0;
        return dfs(s, u);
    }
    string dfs(string& s, int& u) {
        string res;
        while (u < s.size() && s[u] != ']') {
            if (s[u] >= 'a' && s[u] <= 'z' || s[u] >= 'A' && s[u] <= 'Z') res += s[u ++ ];
            else if (s[u] >= '0' && s[u] <= '9') {
                int k = u;
                while (s[k] >= '0' && s[k] <= '9') k ++ ;
                int x = stoi(s.substr(u, k - u));
                u = k + 1;
                string y = dfs(s, u);
                u ++ ; // 过滤掉右括号
                while (x -- ) res += y;
            }
        }
        return res;
    }
};

399. 除法求值

给你一个变量对数equations和一个实数值数组values作为已知条件，其中equationsi=Ai,Bi和ivaluesi共同表示等式iAi/Bi=valuesi。每个Ai或iBi是一个表示单个变量的字符串。

另有一些以数组queries表示的问题，其中jqueriesj=Cj,Dj表示第j jj个问题，请你根据已知条件找出j=Cj/Dj=? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_set<string> vers;
        unordered_map<string, unordered_map<string, double>> d;
        for (int i = 0; i < equations.size(); i ++ ) {
            auto a = equations[i][0], b = equations[i][1];
            auto c = values[i];
            d[a][b] = c, d[b][a] = 1 / c;
            vers.insert(a), vers.insert(b);
        }
        for (auto k: vers)
            for (auto i: vers)
                for (auto j: vers)
                    if (d[i][k] && d[j][k])
                        d[i][j] = d[i][k] * d[k][j];
        vector<double> res;
        for (auto q: queries) {
            auto a = q[0], b = q[1];
            if (d[a][b]) res.push_back(d[a][b]);
            else res.push_back(-1);
        }
        return res;
    }
};

402. 移掉K位数字

class Solution {
public:
    string removeKdigits(string num, int k) {
        k = min(k, (int)num.size());
        string res;
        for (auto c: num) {
            while (k && res.size() && res.back() > c) {
                k -- ;
                res.pop_back();
            }
            res += c;
        }
        while (k -- ) res.pop_back();
        k = 0;
        while (k < res.size() && res[k] == '0') k ++ ;
        if (k == res.size()) res += '0';
        return res.substr(k);
    }
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组people表示队列中一些人的属性（不一定按顺序）。每个peoplei=hi,ki表示第i ii个人的身高为ihi，前面正好有ki个身高大于或等于hi的人。

请你重新构造并返回输入数组eople所表示的队列。返回的队列应该格式化为数组queue ，其中queuej=hj,kj是队列中第个人的属性（queue0是排在队列前面的人）。

class Solution {
public:
    int n;
    vector<int> tr;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
    }
    int query(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        n = people.size();
        tr.resize(n + 1);
        sort(people.begin(), people.end(), [](vector<int>a, vector<int>b) {
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        });
        vector<vector<int>> res(n);
        for (auto p: people) {
            int h = p[0], k = p[1];
            int l = 1, r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (mid - query(mid) >= k + 1) r = mid;
                else l = mid + 1;
            }
            res[r - 1] = p;
            add(r, 1);
        }
        return res;
    }
};
/*
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        auto cmp = [](const vector<int>& a, const vector<int>& b) {
            if(a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        };
        sort(people.begin(), people.end(), cmp);
        int n = people.size();
        vector<vector<int>> res(n);
        for(auto &p: people) {
            int k = p[1] + 1;
            for(auto &seg: res)
                if(seg.empty()) {
                    k --;
                    if(!k) {
                        seg = p;
                        break;
                    }
                }
        }
        return res;
    }
};
*/

416. 分割等和子集

给你一个 只包含正整数的非空数组nums请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<10001> f;
        f[0] = 1;
        int sum = 0;
        for (auto x: nums) {
            f |= f << x;
            sum += x;
        }
        if (sum % 2) return false;
        return f[sum / 2];
    }
};

437. 路径总和 III

给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于 targetSum的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

class Solution {
public:
    unordered_map<int, int> cnt;
    int res = 0;
    int pathSum(TreeNode* root, int sum) {
        cnt[0] ++ ;
        dfs(root, sum, 0);
        return res;
    }
    void dfs(TreeNode* root, int sum, int cur) {
        if (!root) return;
        cur += root->val;
        res += cnt[cur - sum];
        cnt[cur] ++ ;
        dfs(root->left, sum, cur), dfs(root->right, sum, cur);
        cnt[cur] -- ;
    }
};

438. 找到字符串中所有字母异位词

给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> cnt;
        for (auto c: p) cnt[c] ++ ;
        vector<int> res;
        int tot = cnt.size();
        for (int i = 0, j = 0, satisfy = 0; i < s.size(); i ++ ) {
            if ( -- cnt[s[i]] == 0) satisfy ++ ;
            while (i - j + 1 > p.size()) {
                if (cnt[s[j]] == 0) satisfy -- ;
                cnt[s[j ++ ]] ++ ;
            }
            if (satisfy == tot) res.push_back(j);
        }
        return res;
    }
};

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

给你一个含n个整数的数组nums，其中numsi在区间[1,n]内。请你找出所有在[1,n]范围内但没有出现在nums中的数字，并以数组的形式返回结果。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (auto x: nums) {
            x = abs(x);
            if (nums[x - 1] > 0) nums[x - 1] *= -1;
        }
        vector<int> res;
        for (int i = 0; i < nums.size(); i ++ )
            if (nums[i] > 0)
                res.push_back(i + 1);
        return res;
    }
};

461. 汉明距离

class Solution {
public:
    int hammingDistance(int x, int y) {
        int res = 0;
        while (x || y) {
            res += (x & 1) ^ (y & 1);
            x >>= 1, y >>= 1;
        }
        return res;
    }
};

494. 目标和

给你一个整数数组nums和一个整数target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums=[2,1]，可以在2之前添加 ‘+’ ，在1之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。

返回可以通过上述方法构造的、运算结果等target的不同表达式的数目。

class Solution {
public:
    int findTargetSumWays(vector<int>& a, int S) {
        if (S < -1000 || S > 1000) return 0;
        int n = a.size(), Offset = 1000;
        vector<vector<int>> f(n + 1, vector<int>(2001));
        f[0][Offset] = 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = -1000; j <= 1000; j ++ ) {
                if (j - a[i - 1] >= -1000)
                    f[i][j + Offset] += f[i - 1][j - a[i - 1] + Offset];
                if (j + a[i - 1] <= 1000)
                    f[i][j + Offset] += f[i - 1][j + a[i - 1] + Offset];
            }
        return f[n][S + Offset];
    }
};

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

class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->right);
        int x = root->val;
        root->val += sum;
        sum += x;
        dfs(root->left);
    }
};

543. 二叉树的直径

class Solution {
public:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int left = dfs(root->left), right = dfs(root->right);
        ans = max(ans, left + right);
        return max(left, right) + 1;
    }
};

560. 和为K KK的子数组

给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的连续子数组的个数 。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + nums[i - 1];
        unordered_map<int, int> hash;
        hash[0] = 1;
        int res = 0;
        for (int i = 1; i <= n; i ++ ) {
            res += hash[s[i] - k];
            hash[s[i]] ++ ;
        }
        return res;
    }
};

581. 最短无序连续子数组

给你一个整数数组nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l + 1 < nums.size() && nums[l + 1] >= nums[l]) l ++ ;
        if (l == r) return 0;
        while (r - 1 >= 0 && nums[r - 1] <= nums[r]) r -- ;
        for (int i = l + 1; i < nums.size(); i ++ )
            while (l >= 0 && nums[l] > nums[i])
                l -- ;
        for (int i = r - 1; i >= 0; i -- )
            while (r < nums.size() && nums[r] < nums[i])
                r ++ ;
        return r - l - 1;
    }
};

617. 合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t2) swap(t1, t2);  // 可以保证t1一定不为空
        if (!t1) return NULL;
        if (t2) t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2 ? t2->left : NULL);
        t1->right = mergeTrees(t1->right, t2 ? t2->right : NULL);
        return t1;
    }
};

621. 任务调度器

给你一个用字符数组tasks表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在1个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个相同种类的任务之间必须有长度为整数n的冷却时间，因此至少有连续n个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> hash;
        for (auto c: tasks) hash[c] ++ ;
        int maxc = 0, cnt = 0;
        for (auto [k, v]: hash) maxc = max(maxc, v);
        for (auto [k, v]: hash)
            if (maxc == v)
                cnt ++ ;
        return max((int)tasks.size(), (maxc - 1) * (n + 1) + cnt);
    }
};

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            // 枚举长度为奇数的情况
            for (int j = i, k = i; j >= 0 && k < s.size(); j --, k ++ ) {
                if (s[j] != s[k]) break;
                res ++ ;
            }
            // 偶数情况
            for (int j = i, k = i + 1; j >= 0 && k < s.size(); j --, k ++ ) {
                if (s[j] != s[k]) break;
                res ++ ;
            }
        }
        return res;
    }
};

739. 每日温度

给定一个整数数组temperatures，表示每天的温度，返回一个数组nswer，其中answeri是指对于第i ii天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> stk;
        vector<int> res(T.size());
        for (int i = T.size() - 1; i >= 0; i -- ) {
            while (stk.size() && T[i] >= T[stk.top()]) stk.pop();
            if (stk.size()) res[i] = stk.top() - i;
            stk.push(i);
        }
        return res;
    }
};
文章标签：
人工智能
BI
索引
算法
调度
zombo_tany
目录
相关文章
程序员行者孙
|
1月前
|
图计算
接雨水（leetcode hot100）
接雨水（leetcode hot100）
程序员行者孙
9 1
程序员行者孙
|
1月前
滑动窗口最大值（leetcode hot100）
滑动窗口最大值（leetcode hot100）
程序员行者孙
20 0
玉面大蛟龙
|
Java
二叉树中的最大路径和（力扣热题HOT100 之 力扣124）java
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
玉面大蛟龙
114 0
二叉树中的最大路径和（力扣热题HOT100 之 力扣124）java
玉面大蛟龙
|
算法 Java
二叉树展开为链表（力扣热题HOT100 之 力扣114）Java
给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。
玉面大蛟龙
99 0
二叉树展开为链表（力扣热题HOT100 之 力扣114）Java
玉面大蛟龙
|
Java
最大正方形（力扣热题HOT100 之 力扣221）java动态规划
最大正方形（力扣热题HOT100 之 力扣221）java动态规划
玉面大蛟龙
85 0
最大正方形（力扣热题HOT100 之 力扣221）java动态规划
zombo_tany
|
机器学习/深度学习 存储 算法
Leetcode hot100题 个人整理版（一）
Leetcode hot100题 个人整理版
zombo_tany
88 0
Leetcode hot100题 个人整理版（一）
梦中追风的少年
|
存储 C语言
LeetCode 热题HOT100-两数之和（C语言）
LeetCode 热题HOT100-两数之和（简单）两种方法解答
梦中追风的少年
202 0
LeetCode 热题HOT100-两数之和（C语言）
玉面大蛟龙
|
Java
移动零（力扣热题HOT100 之 力扣283）java
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
玉面大蛟龙
68 0
玉面大蛟龙
|
算法 Java
最长连续序列（力扣热题HOT100 之 力扣128）Java
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
玉面大蛟龙
139 0
玉面大蛟龙
|
Java 索引
跳跃游戏（力扣热题HOT100 之 力扣55）Java 贪心
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。
玉面大蛟龙
72 0