【LeetCode周赛】2022上半年题目精选集——思维题

文章目录

    • 2211. 统计道路上的碰撞次数(栈 || 脑筋急转弯)
      • 解法1:自己想的——使用栈
      • 解法2——思维:去掉左右两边往左右开的车
        • 代码写法1——找左右端点
        • 代码写法2——正则表达式去除+流处理api
          • 补充:replaceAll() 和 正则表达式
          • 补充:(int) s.chars().filter(c -> c == 'S').count(); 解释
    • 2227. 加密解密字符串 (逆向思维)
      • 思路
      • 代码1
      • 代码2
    • 2242. 节点序列的最大得分⭐⭐⭐⭐⭐ (有技巧的枚举)
      • 思路——有技巧的枚举(枚举中间的边)
      • 代码
    • 2306. 公司命名⭐⭐⭐⭐⭐(分类讨论)
    • 2317. 操作后的最大异或和(位运算)
      • 思路
      • 代码
  • 相关链接

2211. 统计道路上的碰撞次数(栈 || 脑筋急转弯)

2211. 统计道路上的碰撞次数

难度:1581
在这里插入图片描述
提示:

1 <= directions.length <= 10^5
directions[i] 的值为 'L'、'R' 或 'S'

解法1:自己想的——使用栈

受 2126. 摧毁小行星 这道题的启发,使用栈来处理这个问题。

当枚举到 ‘R’ 和 ‘S’ 时,先放入栈中不做处理;
当枚举到 ‘L’ 时,如果此时栈中不为空,那么它会发生碰撞并停下来,因此 ans ++ ,并放入栈中一个 ‘S’;

枚举完毕后,再来处理栈中的 ‘R’,只要 ‘R’ 的上方有 ‘S’ 存在,就会贡献一个 ans ++。

class Solution {
    public int countCollisions(String directions) {
        Deque<Character> stk = new ArrayDeque();
        int ans = 0;
        for (char ch: directions.toCharArray()) {
            if (ch == 'L') {
                if (!stk.isEmpty()) {
                    stk.push('S');
                    ++ans;
                }
            } else stk.push(ch);
        }
        boolean f = false;
        while (!stk.isEmpty()) {
            char ch = stk.pop();
            if (ch == 'R' && f) ++ans;
            if (ch != 'R') f = true;
        }
        return ans;
    }
}

时间复杂度是 O ( n ) O(n) O(n)

解法2——思维:去掉左右两边往左右开的车

去掉往左右两边开的车之后,剩下非停止的车必然会碰撞。

代码写法1——找左右端点

分别找到两边去掉之后的端点,枚举端点范围内的车辆,每个 L 和 R 都会贡献一个答案 ans++。

class Solution {
    public int countCollisions(String directions) {
        int n = directions.length(), l = 0, r = n - 1, ans = 0;
        while (l < n && directions.charAt(l) == 'L') ++l;
        while (r >= 0 && directions.charAt(r) == 'R') --r;
        for (int i = l; i <= r; ++i) {
            if (directions.charAt(i) != 'S') ++ans;
        }
        return ans;
    }
}

代码写法2——正则表达式去除+流处理api

class Solution {
    public int countCollisions(String s) {
        // 前缀向左的车不会发生碰撞
        s = s.replaceAll("^L+", ""); 
        // 后缀向右的车不会发生碰撞
        s = new StringBuilder(s).reverse().toString().replaceAll("^R+", ""); 
        // 剩下非停止的车必然会碰撞
        return s.length() - (int) s.chars().filter(c -> c == 'S').count(); 
    }
}
补充:replaceAll() 和 正则表达式

Java 中的 String 类的 replaceAll() 方法是用来使用给定的 replacement 字符串替换此字符串匹配给定的正则表达式的每个子字符串。
它的语法是:

public String replaceAll(String regex, String replacement)

其中,regex 是要替换的正则表达式,replacement 是用来替换每个匹配项的字符串。

关于正则表达式
在这里插入图片描述
更多关于正则表达式可见:正则表达式 - 廖雪峰的官方网站

本题中用到的 ^L+ 表示 匹配 1 个或多个位于字符串开头的 L。

补充:(int) s.chars().filter(c -> c == ‘S’).count(); 解释

对应代码中的这一句:

return s.length() - (int) s.chars().filter(c -> c == 'S').count(); 

由于解释太长,已经放在了:【Java语法小记】求字符串中某个字符的数量——IntStream流的使用 中。

2227. 加密解密字符串 (逆向思维)

2227. 加密解密字符串

难度:1944

在这里插入图片描述
提示:

1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
所有 keys[i] 和 dictionary[i] 互不相同
1 <= word1.length <= 2000
1 <= word2.length <= 200
所有 word1[i] 都出现在 keys 中
word2.length 是偶数
keys、values[i]、dictionary[i]、word1 和 word2 只含小写英文字母
至多调用 encrypt 和 decrypt 总计 200 次

思路

读懂题就已经很难了!

它初始给的代码框架长这样:

class Encrypter {

    public Encrypter(char[] keys, String[] values, String[] dictionary) {

    }
    
    public String encrypt(String word1) {

    }
    
    public int decrypt(String word2) {

    }
}

我们要填写构造方法加密方法计算解密后的数量方法

思路:

  • 构造方法用来定义一些会被使用到的数据结构。
  • 加密方法按照题目要求进行模拟即可。
  • 为了计算解密后出现在 dictionary 中字符串的数量,我们可以提前预处理出所有 dictionary 加密后的字符串并计数保存,这样在解密方法中直接查表就好了。

代码1

class Encrypter {
    char[] keys;
    String[] values, dictionary;
    Map<Character, Integer> m = new HashMap();
    Map<String, Integer> ans = new HashMap();

    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        this.keys = keys;
        this.values = values;
        this.dictionary = dictionary;
        // 存储key中字符和对应的下标
        for (int i = 0; i < keys.length; ++i) m.put(keys[i], i);
        // 提前计算加密结果
        for (String d: dictionary) {
            String dd = encrypt(d);
            // 这里使用 dd + d.length() 作为键是为了确保我们找的加密前字符串的长度是解密前字符串长度的1/2,直接使用dd的话会被最后一个样例卡住
            // 即a对应bb,bbbb应该被解密成aa,但abb这个字符串加密之后也会成为bbbb影响答案计算
            ans.merge(dd + d.length(), 1, Integer::sum);
        }
    }
    
    public String encrypt(String word1) {
        StringBuilder ans = new StringBuilder();
        for (char ch: word1.toCharArray()) {
            if (m.containsKey(ch)) ans.append(values[m.get(ch)]);
            else ans.append(ch);
        }
        return ans.toString();
    }
    
    public int decrypt(String word2) {
    	// 直接查表即可
        return ans.getOrDefault(word2 + (word2.length() / 2), 0);
    }
}

代码2

代码2的加密过程中,如果查询到了不在 key 中的字符,就会直接 return “” ,这样就使得加密过程产出的所有字符串都是全加密的(即字符串中的每个字符都映射成了新的字符串)。

这样也就避免了代码 1 注释中所说的问题:(

// 这里使用 dd + d.length() 作为键是为了确保我们找的加密前字符串的长度是解密前字符串长度的1/2,直接使用dd的话会被最后一个样例卡住
// 即a对应bb,bbbb应该被解密成aa,但abb这个字符串加密之后也会成为bbbb影响答案计算

而题目中的提示说明了 所有 word1[i] 都出现在 keys 中 ,所以不用担心这种写法对于加密结果的影响。

class Encrypter {
    Map<String, Integer> cnt = new HashMap();
    String[] map = new String[26];

    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        // 记录字符c对应keys中下标i所在的values[i]
        for (int i = 0; i < keys.length; ++i) {
            map[keys[i] - 'a'] = values[i];
        }
        // 预处理dictionary加密
        for (String s: dictionary) {
            String e = encrypt(s);
            cnt.merge(e, 1, Integer::sum);
        }
    }
    
    public String encrypt(String word1) {
        StringBuilder res = new StringBuilder();
        for (char ch: word1.toCharArray()) {
            String s = map[ch - 'a'];
            if (s == null) return "";
            res.append(s);
        }
        return res.toString();
    }
    
    public int decrypt(String word2) {
        return cnt.getOrDefault(word2, 0);
    }
}

2242. 节点序列的最大得分⭐⭐⭐⭐⭐ (有技巧的枚举)

2242. 节点序列的最大得分

难度:2304

在这里插入图片描述

思路——有技巧的枚举(枚举中间的边)

在这里插入图片描述

Q:为什么枚举中间的边效率最好?
A:因为枚举一条边的同时就会确定两个点,这时只需要再对这两个点找到相邻最大的点就可以了。

代码

class Solution {
    public int maximumScore(int[] scores, int[][] edges) {
        int n = scores.length;
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList());
        for (int[] edge: edges) {
            int x = edge[0], y = edge[1];
            g[x].add(new int[]{scores[y], y});
            g[y].add(new int[]{scores[x], x});
        }
        for (int i = 0; i < n; ++i) {
            // 如果和i相连的点的数量>3,就可以删掉只剩3个最大的
            // 这样删可以确保和它组成一个序列的另外3个值都不会被删掉
            // 即对于序列a-x-y-b,枚举到x的时候要保证a,y,b都不会被删掉
            // 删去其它的边是为了后面遍历的时候快一些
            if (g[i].size() > 3) {
                g[i].sort((a, b) -> (b[0] - a[0]));     // 按照score从大到小排序
                g[i] = new ArrayList<>(g[i].subList(0, 3));
            }
        }

        int ans = -1;
        // 枚举每个边作为中间的边
        for (int[] edge: edges) {
            int x = edge[0], y = edge[1];
            for (int[] p: g[x]) {
                int a = p[1];       // x旁边的节点号a
                for (int[] q: g[y]) {
                    int b = q[1];   // y旁边的节点号b
                    if (a != y && b != x && a != b) {
                        ans = Math.max(ans, p[0] + q[0] + scores[x] + scores[y]);
                    }
                }
            }
        }
        return ans;
    }   
}

2306. 公司命名⭐⭐⭐⭐⭐(分类讨论)

2306. 公司命名

难度:2305

在这里插入图片描述
提示:

2 <= ideas.length <= 5 * 10^4
1 <= ideas[i].length <= 10
ideas[i] 由小写英文字母组成
ideas 中的所有字符串 互不相同

从数据范围来看 O ( n 2 ) O(n^2) O(n2) 的算法是不行的。

因此我们来考虑:
在这里插入图片描述
核心思想就是将每个字符串的首字符和其余部分分开,分组统计,分别计算出 有i无j 和 有j无i 的组的数量,最后计算答案。

class Solution {
    public long distinctNames(String[] ideas) {
        // 按照ideas[1:]分组,记录这个组的首字母有哪些(通过mask存储)
        Map<String, Integer> group = new HashMap();
        for (String idea: ideas) {
            String t = idea.substring(1);
            group.put(t, group.getOrDefault(t, 0) | 1 << (idea.charAt(0) - 'a'));
        }

        long ans = 0;
        int[][] cnt = new int[26][26];              // cnt[i][j]表示没i有j的组的个数
        for (int mask: group.values()) {
            // 计算cnt[i][j]
            for (int i = 0; i < 26; ++i) {
                for (int j = i + 1; j < 26; ++j) {
                    if ((mask >> i & 1) == 0 && (mask >> j & 1) == 1) ++cnt[i][j];
                    else if ((mask >> i & 1) == 1 && (mask >> j & 1) == 0) ++cnt[j][i];
                }
            }
        }
        // 所有成对的 cnt[i][j]和cnt[j][i] 可以贡献方案数
        for (int i = 0; i < 26; ++i) {
            for (int j = i + 1; j < 26; ++j) {
                ans += cnt[i][j] * cnt[j][i];
            }
        }
        return ans * 2;
    }
}

2317. 操作后的最大异或和(位运算)

2317. 操作后的最大异或和

难度:1678
在这里插入图片描述

思路

先分析 nums[i] AND (nums[i] XOR x) 的结果:
由于是 AND ,所以 结果中 1 的数量一定小于 nums[i] 中 1 的数量;
由于 x 是任意取的,所以 nums[i] XOR x 可以获得任意数字,
因此 nums[i] AND (nums[i] XOR x) 的最终结果是可以删去 nums[i] 二进制表示中任意数量的 1

我们知道异或的性质是:相同得0,不同得1
要想获得最大值,那就将尽可能多的位置上变成 1。
可以要想变成 1 ,就必须是 1 和 0 之间得异或,即这个位置上本来就有 1 ,我们就可以将其保留下来。

=》有 1 就保留 1 ,这是 或运算 的性质。

因此最终结果就是所有数字 或 起来的结果。

代码

class Solution {
    public int maximumXOR(int[] nums) {
        int ans = 0;
        for (int num: nums) ans |= num;
        return ans;
    }
}

相关链接

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/34733.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python图像处理实战(三)—图像几何变换

&#x1f680;写在前面&#x1f680; &#x1f58a;个人主页&#xff1a;https://blog.csdn.net/m0_52051577?typeblog &#x1f381;欢迎各位大佬支持点赞收藏&#xff0c;三连必回&#xff01;&#xff01; &#x1f508;本人新开系列专栏—python图像处理 ❀愿每一个骤雨初…

c语言修炼之猜数字游戏

前言 小伙伴们&#xff0c;今天来学习猜数字游戏叭&#xff01;废话不多说&#xff0c;让我们一起开始学习叭! 思路&#xff1a; 一打开游戏就出现一个菜单然后可以让我们选择是进入游戏还是退出游戏&#xff01; #include<stdio.h> void menu() {printf("*****…

【MySQL】基本查询之表的增删改查

【MySQL】表的增删改查 一、插入操作----insert1.1 简单插入1.2 插入时是否更新----ON DUPLICATE KEY UPDATE1.3 插入时替换----REPLACE 二、查询----select2.1 简单查询与去重2.2 基本查询----where条件2.2.3 案列演示 2.4 排序----order by 三、修改操作----update四、删除--…

Lua学习笔记:浅谈table的实现

前言 本篇在讲什么 Lua中的table的实现 本篇适合什么 适合初学Lua的小白 本篇需要什么 对Lua语法有简单认知 依赖Sublime Text编辑器 本篇的特色 具有全流程的图文教学 重实践&#xff0c;轻理论&#xff0c;快速上手 提供全流程的源码内容 ★提高阅读体验★ &…

大数据Doris(五十三):MySQL Dump 导出

文章目录 MySQL dump 导出 一、Dump导出案例 二、注意事项 MySQL Dump 导出 mysqldump是一个常用的 MySQL 数据库备份工具&#xff0c;它可以将 MySQL 数据库中的数据导出为 SQL 格式的文件&#xff0c;从而实现对数据的备份、迁移和恢复等操作。Doris 在0.15 之后的版本已…

青岛大学_王卓老师【数据结构与算法】Week04_03_双向链表_学习笔记

本文是个人学习笔记&#xff0c;素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享&#xff0c;另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权&#xff0c;请留言作删文处理。 课程视频链接&#xff1a; 数据结构与算法基础–…

Spring Boot 集成 Redisson分布式锁

Redisson 是一种基于 Redis 的 Java 驻留集群的分布式对象和服务库&#xff0c;可以为我们提供丰富的分布式锁和线程安全集合的实现。在 Spring Boot 应用程序中使用 Redisson 可以方便地实现分布式应用程序的某些方面&#xff0c;例如分布式锁、分布式集合、分布式事件发布和订…

Oracle数据库软件安装与卸载

Oracle数据库软件安装与卸载 实验目的及要求 学习Oracle12c数据库服务器软件和客户端软件的安 装与卸载,掌握客户端服务名的设置,建立客户端与服务器的网络连接,熟悉windows操作系统中Oracle相关服务的操作。理解数据库管理的基本架构。 &#xff08;1&#xff09;熟悉Oracle…

基于SpringBoot+SpringCloud+vue的智慧养老平台设计与实现

博主介绍&#xff1a; 大家好&#xff0c;我是一名在Java圈混迹十余年的程序员&#xff0c;精通Java编程语言&#xff0c;同时也熟练掌握微信小程序、Python和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我擅长在JavaWeb、SSH、SSM、SpringBoot等框架…

虚拟机上用docker + nginx跑前端并支持https和http

情况是这样&#xff0c;我在虚拟机上&#xff0c;使用docker跑前端&#xff0c;需要这个前端支持https&#xff0c;原http的话自动跳转到https。另外&#xff0c;前端部署使用了负载均衡&#xff0c;即使用了3个docker跑前端&#xff1a;1个入口&#xff0c;另外2个是前端&…

【macOS 系列】mac设置截屏或其他操作的默认保存位置

1、第一步、在用户/图片文件夹下&#xff0c;新建“截图”文件夹 2、第二步、打开终端&#xff0c;输入defaults write com.apple.screencapture location ~/Pictures/截图/后回车 3、第三步、操作完成后&#xff0c;再次输入killall SystemUIServer后回车 如果你在web前端开发…

clickhouse中时间戳转换--网上都没有,自己总结的

第一种&#xff1a; 库里时间戳为13位时&#xff1a; 类似这种13位的时间戳&#xff1a;1476141341051 怎么转换成正常的日期&#xff1a; 如果库里存的string类型&#xff0c;需要toUInt64(date_time) date_time的值为&#xff1a;1476141341051 然后利用toDateTime&…

远古 Windows 98 SE 和 putty 0.63 连接 SSH

远古 Windows 98 SE 和 putty 0.63 连接 SSH 不忘初心一、故障表现二、产生原因三、解决办法四、重启 SSHD 服务生交配置参考 作者&#xff1a;高玉涵 时间&#xff1a;2023.7.1 操作系统&#xff1a; Windows 98 第二版 4.10.2222 A Linux version 5.19.0-32-generic (build…

Redis实战——商户查询(二)

缓存穿透 缓存穿透 &#xff1a;客户端请求的数据在缓存中和数据库中都不存在&#xff0c;这样缓存永远不会生效&#xff0c;这样的请求都会访问到数据库&#xff0c;这样的大量请求同时过来访问这种不存在的数据&#xff0c;这些请求就都会访问到数据库&#xff0c;对数据库造…

基于smardaten无代码开发舆情分析系统

一、前言 在日常生活中&#xff0c;有各种各样的资讯、社交平台。这些平台充斥着大量信息&#xff0c;这些信息中隐含了许多有用数据&#xff0c;但是这些数据无法之间获取&#xff0c;且难以展示&#xff0c;于是就有了舆情分析系统。 舆情分析系统是一个综合的系统&#xf…

基于minsit数据集的图像分类任务|CNN简单应用项目

Github地址 Image-classification-task-based-on-minsit-datasethttps://github.com/Yufccode/CollegeWorks/tree/main/ImageProcessing/Image-classification-task-based-on-minsit-dataset README 摘要 本次实验报告用两种方式完成了基于minst数据集完成了图像的分类任务…

被吐槽 GitHub仓 库太大,直接 600M 瘦身到 6M,这下舒服了

前言 忙里偷闲学习了点技术写了点demo代码&#xff0c;打算提交到我那 2000Star 的Github仓库上&#xff0c;居然发现有5个Issues&#xff0c;最近的一条日期已经是2022/8/1了&#xff0c;以前我还真没留意过这些&#xff0c;我这人懒得很&#xff0c;本地代码提交成功基本就不…

Python dict keys方法:获取字典中键的序列【将keys转为list】

描述 dict.keys()方法是Python的字典方法&#xff0c;它将字典中的所有键组成一个可迭代序列并返回。 使用示例 >>> list({Chinasoft:China, Microsoft:USA}.keys()) [Chinasoft, Microsoft] >>> test_dict {Chinasoft:China, Microsoft:USA, Sony:Japan,…

【计算机视觉 | 目标检测】arxiv 计算机视觉关于目标检测的学术速递(7 月 4 日论文合集)

文章目录 一、检测相关(15篇)1.1 Artifacts Mapping: Multi-Modal Semantic Mapping for Object Detection and 3D Localization1.2 Shi-NeSS: Detecting Good and Stable Keypoints with a Neural Stability Score1.3 HODINet: High-Order Discrepant Interaction Network for…

机器学习一:线性回归

1 知识预警 1.1 线性代数 ( A T ) T A (A^\mathrm{T})^\mathrm{T}A (AT)TA$ ( A B ) T A T B T (AB)^\mathrm{T}A^\mathrm{T}B^\mathrm{T} (AB)TATBT ( λ A ) T λ A T (\lambda A)^\mathrm{T}\lambda A^\mathrm{T} (λA)TλAT ( A B ) T B T A T (AB)^\mathrm{T}B^…