您现在的位置是:首页 > 正文

leetcode解题思路分析(一百二十三)1018 - 1024 题

2024-01-30 20:26:36阅读 2
  1. 可被 5 整除的二进制前缀
    给定一个二进制数组 nums ( 索引从0开始 )。我们将xi 定义为其二进制表示形式为子数组 nums[0…i] (从最高有效位到最低有效位)。例如,如果 nums =[1,0,1] ,那么 x0 = 1, x1 = 2, 和 x2 = 5。返回布尔值列表 answer,只有当 xi 可以被 5 整除时,答案 answer[i] 为 true,否则为 false。

本题的关键在于如果一直保存子数组的数,则一定会溢出。因此考虑对原递推公式分析,发现直接使用余数做递推也是可以的,由此得到解。

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) 
    {
        int          remain = 0;
        vector<bool> bRetVec;

        for (int i = 0; i < nums.size(); ++i)
        {
            remain = ((remain << 1) + nums[i]) % 5;
            bRetVec.push_back(remain == 0);
        }

        return bRetVec;
    }
};
  1. 链表中的下一个更大节点
    给定一个长度为 n 的链表 head对于列表中的每个节点,查找下一个 更大节点 的值。也就是说,对于每个节点,找到它旁边的第一个节点的值,这个节点的值 严格大于 它的值。返回一个整数数组 answer ,其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点,设置 answer[i] = 0 。

通过单调栈记录没有找到更大值的节点信息

/**
 * 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:
    vector<int> nextLargerNodes(ListNode* head) 
    {
        vector<int> ret;
        ListNode*   pNode = head;
        stack<int>  ValStack;

        while (pNode)
        {
            ret.push_back(pNode->val);
            pNode = pNode->next;
        }

        ValStack.push(0);

        for (int i = 1; i < ret.size(); ++i)
        {
            while (ValStack.size() > 0 && ret[ValStack.top()] < ret[i])
            {
                int pos = ValStack.top();
                ValStack.pop();
                ret[pos] = ret[i];
            }
            ValStack.push(i);
        }

        while (ValStack.size() > 0)
        {
            ret[ValStack.top()] = 0;
            ValStack.pop();
        }

        return ret;
    }
};
  1. 飞地的数量
    给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

可以用DFS/BFS或者并查集来做

class UnionFind {
public:
    UnionFind(const vector<vector<int>> & grid) {
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);
        this->onEdge = vector<bool>(m * n, false);
        this->rank = vector<int>(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        onEdge[index] = true;
                    }
                }
            }
        }
    }

    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    void uni(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
                onEdge[rooty] = onEdge[rooty] | onEdge[rootx];
            } else {
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
                rank[rootx]++;
            }
        }
    }

    bool isOnEdge(int i) {
        return onEdge[find(i)];
    }
private:
    vector<int> parent;
    vector<bool> onEdge;
    vector<int> rank;    
};

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        UnionFind uf(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == 1) {
                        uf.uni(index, index + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1) {
                        uf.uni(index, index + n);
                    }
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !uf.isOnEdge(i * n + j)) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
};

  1. 删除最外层的括号
    对 s 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 s 。

本题思路也是单调栈,但是因为s一定是有效的,所以不需要真的用栈,直接一个int计数就可以了

class Solution {
public:
    string removeOuterParentheses(string s) 
    {
        int    nCnt = 0;
        string ret;
        int    nStackCnt = 0;

        for (auto c : s)
        {
            if (c == '(')
            {
                nStackCnt++;
            }
            else
            {
                if (nStackCnt > 1)
                {
                    while (nStackCnt > 1)
                    {
                        ret += '(';
                        nStackCnt--;
                        nCnt++;
                    }
                    ret += c;
                    nCnt--;
                }
                else
                {
                    if (nCnt)
                    {
                        ret += c;
                        nCnt--;
                    }
                    else
                    {
                        nStackCnt--;
                    }
                }
            }
        }

        return ret;
    }
};
  1. 从根到叶的二进制数之和
    给出一棵二叉树,其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如,如果路径为 0 -> 1 -> 1 -> 0 -> 1,那么它表示二进制数 01101,也就是 13 。
    对树上的每一片叶子,我们都要找出从根到该叶子的路径所表示的数字。
    返回这些数字之和。题目数据保证答案是一个 32 位 整数。

DFS或者BFS即可

/**
 * 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:
    int dfs(TreeNode *root, int val) {
        if (root == nullptr) {
            return 0;
        }
        val = (val << 1) | root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return val;
        }
        return dfs(root->left, val) + dfs(root->right, val);
    }

    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }
};

  1. 驼峰式匹配
    如果我们可以将小写字母插入模式串 pattern 得到待查询项 query,那么待查询项与给定模式串匹配。(我们可以在任何位置插入每个字符,也可以插入 0 个字符。)给定待查询列表 queries,和模式串 pattern,返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时, answer[i] 才为 true,否则为 false。

读懂题意遍历就完事了

class Solution {
public:
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> res;
        for (const auto& q : queries) {
            if (canMatch(q, pattern)) {
                res.push_back(true);
            } else {
                res.push_back(false);
            }
        }

        return res;
    }

private:
    bool canMatch(const string& q, const string& pattern) {
        int i = 0;
        int j = 0;
        int M = q.size();
        int N = pattern.size();
        while (i < M) {
            if (j < N && q[i] == pattern[j]) {
                i++;
                j++;
            } else if (isupper(q[i])) {
                return false;
            } else {
                i++;
            }
        }

        return i == M && j == N;
    }
};

  1. 视频拼接
    你将会获得一系列视频片段,这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。使用数组 clips 描述所有的视频片段,其中 clips[i] = [starti, endi] 表示:某个视频片段开始于 starti 并于 endi 结束。甚至可以对这些片段自由地再剪辑:例如,片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, time])。返回所需片段的最小数目,如果无法完成该任务,则返回 -1 。

本质上是一个贪心问题,枚举每一个位置,假设当枚举到位置 i 时,记左端点不大于 i 的所有子区间的最远右端点为 last。这样 就代表了当前能覆盖到的最远的右端点。每次我们枚举到一个新位置,都更新last 。如果更新后那么说明下一个位置无法被覆盖,我们无法完成目标。同时我们还需要记录上一个被使用的子区间的结束位置为pre,每次我们越过一个被使用的子区间,就说明我们要启用一个新子区间,这个新子区间的结束位置即为当前。也就是说明我们用完了一个被使用的子区间。

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        vector<int> maxn(time);
        int last = 0, ret = 0, pre = 0;
        for (vector<int>& it : clips) {
            if (it[0] < time) {
                maxn[it[0]] = max(maxn[it[0]], it[1]);
            }
        }
        for (int i = 0; i < time; i++) {
            last = max(last, maxn[i]);
            if (i == last) {
                return -1;
            }
            if (i == pre) {
                ret++;
                pre = last;
            }
        }
        return ret;
    }
};


网站文章

  • 新书推荐 |《工业机器人系统及应用》

    新书推荐 |《工业机器人系统及应用》

    新书推荐《工业机器人系统及应用》点击上图了解及购买本书由机器人领域的两位技术专家和资深教授联袂撰写,聚焦于工业机器人,涵盖其组成结构、电气控制及实践应用,为机器人的设计、生产、布置、操作...

    2024-01-30 20:26:29
  • Linux/Ubuntu下使用命令开放端口的办法

    Linux/Ubuntu下使用命令开放端口的办法

    一.安装iptables:一般情况下,Ubuntu安装好的时候,iptables会被安装上。如果没有,执行下面命令$ sudo apt-get update$ sudo apt-get install iptables二.安装完后,开放8000端口,使用下面命令:$ sudo iptables -I INPUT -p tcp --dport 8000 -j ACCEPT三.保存规...

    2024-01-30 20:26:02
  • js中两个等号(==)和三个等号(===)的区别

    1. &quot;==&quot;表示:equality -&gt; 等同 的意思,&quot;==&quot;使用两个等号时,如果两边值的类型不同的时候,是要先先进行类型转换后,才能做比较。2. &quot;===&quot;表示:identity -&gt; 恒等 的意思,&quot;===&quot;使用三个等号时,是不需要做类型转换的,如果两边值的类型不同,就表示一定是不等的。...

    2024-01-30 20:25:55
  • skywalking系列-nacos配置

    动态配置nacos配置 可动态配置skywalking服务端配置信息 key==Nacos DataId在开启nacos为 configuration配置中心时必须配置以下key,如果没有以下配置oa...

    2024-01-30 20:25:48
  • 微信小程序分页加载数据~上拉加载更多~小程序云数据库的分页加载

    我们在开发小程序时,一个列表里难免会有很多条数据,比如我们一个列表有1000条数据,我们一下加载出来,而不做分页,将会严重影响性能。所以这一节,我们来讲讲小程序分页加载数据的实现。老规矩,先看效果图可以看到我们每页显示10条数据,当滑动到底部时,会加载第二页的数据,再往下滑动,就加载第三页的数据。由于我们一共21条数据,所以第三页加载完以后,会有一个“已加载全部数据”的提示。本节知识点...

    2024-01-30 20:25:42
  • 计算机表格中如何计算数据透视表,Excel中如何在数据透视表中进行计算

    会计工作中离不开excel电子表格软件,它不仅具有数据输入、输出、显示、分类、统计、查询等数据处理的基本功能,还具有强大的数据分析功能与程序执行自动化功能,为会计人员的工作提供了许多便利。数据透视表是...

    2024-01-30 20:25:13
  • Maven中pom文件引入依赖标签dependency的scope属性

    依赖中引入了主要用于管理依赖关系的作用范围,目前依赖项的作用域可以使用五个值,compile、runtime、test、provided和systemcompile:依赖项的默认作用范围,即当没有指定...

    2024-01-30 20:25:07
  • Python之爬虫-- Requests

    目录Requests-献给人类一、简介二、安装方式三、 GET请求四、POST请求 五、显示json文件六、代理(proxies参数) 七、用户验证八、Cookies 和 Session1、Cookies2、Session九、SSL证书验证https请求验证ssl证书(有一些网站的ssl证书是自己写的,比如12306和360)Requests...

    2024-01-30 20:24:34
  • 控制台查看网页的宽高随浏览器缩放而缩放

    控制台查看网页的宽高随浏览器缩放而缩放

    记住这些代码 随时查看浏览器得宽度高度以及分辨率

    2024-01-30 20:24:27
  • 创建自己的yum源

    创建自己的yum源

    创建自己的yum源2013-02-28 09:18 2328人阅读 评论(0) 收藏 举报 分类:Linux(172) 目录(?)[+]转自:http://www.bsdmap.com/2011/07/06/createrepo/创建自己的yum源  最终还是决定使用rpm来管理系统上“定制”的

    2024-01-30 20:24:19