Leetcode 第394场周赛 问题和解法

2024-04-21 16:36

本文主要是介绍Leetcode 第394场周赛 问题和解法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

统计特殊字母的数量 I

给你一个字符串word。如果word中同时存在某个字母的小写形式和大写形式,则称这个字母为特殊字母。

返回word中特殊字母的数量。

示例 1:

输入:word = "aaAbcBC"输出:3解释:word 中的特殊字母是 'a''b''c'

解题思路

创建两个数组,如果对应字母有出现过就置为1,然后再判断即可。

class Solution {public int numberOfSpecialChars(String word) {int[]count=new int[26];int[]bigCount=new int[26];int len=word.length();for(char mid:word.toCharArray()){if (mid>='a'&&mid<='z'){count[mid-'a']=1;}if (mid>='A'&&mid<='Z'){bigCount[mid-'A']=1;}}int res=0;for(int i=0;i<26;i++){if (count[i]==1&&bigCount[i]==1){res++;}}return res;}
}

统计特殊字母的数量 II

给你一个字符串word。如果word中同时出现某个字母c的小写形式和大写形式,并且每个小写形式的c都出现在第一个大写形式的c之前,则称字母c是一个特殊字母。

返回word中特殊字母的数量。

示例 1:

输入:word = "aaAbcBC"输出:3解释:特殊字母是 'a''b''c'

解题思路

本题是第一题的变种,针对小写字母需要统计出现下标最大的值;针对大写字母需要统计出现下标最小的值,然后依次判断即可。

class Solution {public int numberOfSpecialChars(String word) {int[]count=new int[26];Arrays.fill(count,Integer.MIN_VALUE);int[]bigCount=new int[26];Arrays.fill(bigCount,Integer.MAX_VALUE);int len=word.length();char[]ca=word.toCharArray();for(int i=0;i<len;i++){if (ca[i]>='a'&&ca[i]<='z'){count[ca[i]-'a']=Math.max(i,count[ca[i]-'a']);}if (ca[i]>='A'&&ca[i]<='Z'){bigCount[ca[i]-'A']=Math.min(i,bigCount[ca[i]-'A']);}}int res=0;for(int i=0;i<26;i++){if (count[i]<bigCount[i]&&count[i]!=Integer.MIN_VALUE&&bigCount[i]!=Integer.MAX_VALUE){res++;}}return res;}
}

使矩阵满足条件的最少操作次数

给你一个大小为mxn的二维矩形grid。每次操作中,你可以将任一格子的值修改为任意非负整数。完成所有操作后,你需要确保每个格子grid[i][j]的值满足:

  • 如果下面相邻格子存在的话,它们的值相等,也就是grid[i][j]==grid[i+1][j](如果存在)。
  • 如果右边相邻格子存在的话,它们的值不相等,也就是grid[i][j]!=grid[i][j+1](如果存在)。

请你返回需要的最少操作数目。

示例 1:

输入:grid = [[1,0,2],[1,0,2]]输出:0解释:矩阵中所有格子已经满足要求。

在这里插入图片描述

解题思路

1.创建一个二维数组count. count[i][j]代表第i列有多少个数字j
2.遍历grid填充count数组
3.创建一个result数组, result[i][j]代表当第i列全部为数字j, 并且第0列当第i列所有数据都满足矩阵条件需要花费的最少操作次数
4.初始化第一列, result[0][i] = n - count[0][i];
5.每一列都只依赖前一列, 当前列可以为0-9的任意一个数字, 前一列的数字只要和当前列的数字不一样即可
那么result[i][x] = Math.min(result[i][x], (n - count[i][x]) + result[i - 1][y]);
6.最后我们只要查看最后一列为0-9需要花费的操作次数, 选择最小的即可

class Solution {public int minimumOperations(int[][] grid) {int n = grid.length;int m = grid[0].length;int[][] count = new int[m][10];for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){count[j][grid[i][j]] += 1;}}int[][] result = new int[m][10];for(int i = 0; i < m; i++){Arrays.fill(result[i], 0x3f3f3f3f);}for(int i = 0; i <= 9; i++){result[0][i] = n - count[0][i];}for(int i = 1; i < m; i++){for(int x = 0; x <= 9; x++){for(int y = 0; y <= 9; y++){if(x == y){continue;}result[i][x] = Math.min(result[i][x], (n - count[i][x]) + result[i - 1][y]);}}}int finalResult = 0x3f3f3f3f;for(int i = 0; i <= 9; i++){finalResult = Math.min(finalResult, result[m - 1][i]);}return finalResult;}}

最短路径中的边

给你一个n个节点的无向带权图,节点编号为0到n-1。图中总共有m条边,用二维数组edges表示,其中edges[i]=[ai,bi,wi]表示节点ai和bi之间有一条边权为wi的边。

对于节点0为出发点,节点n-1为结束点的所有最短路,你需要返回一个长度为m的boolean数组answer,如果edges[i]至少在其中一条最短路上,那么answer[i]为true,否则answer[i]为false。

请你返回数组answer。

注意,图可能不连通。

示例 1:

输入:n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]输出:[true,true,true,false,true,true,true,false]解释:以下为节点 0 出发到达节点 5 的 所有 最短路:路径 0 -> 1 -> 5 :边权和为 4 + 1 = 5 。
路径 0 -> 2 -> 3 -> 5 :边权和为 1 + 1 + 3 = 5 。
路径 0 -> 2 -> 3 -> 1 -> 5 :边权和为 1 + 1 + 2 + 1 = 5

在这里插入图片描述

解题思路

首先用 Dijkstra 算法(堆优化版本)计算出起点0到所有节点的最短路长度dis.
如果 dis[n -1] = ∞,说明无法从起点0到终点n-1,答案全为false。
否则,我们可以从终点n-1出发,倒着 DFS 或 BFS,设当前在点y,邻居为x,边权为 w,如果满足dis[x] + w = dis[y]则说明 x-y 这条边在从0到n-1的最短路上。

class Solution {public boolean[] findAnswer(int n, int[][] edges) {List<int[]>[] g = new ArrayList[n];Arrays.setAll(g, i -> new ArrayList<>());for (int i = 0; i < edges.length; i++) {int[] e = edges[i];int x = e[0], y = e[1], w = e[2];g[x].add(new int[]{y, w, i});g[y].add(new int[]{x, w, i});}long[] dis = new long[n];Arrays.fill(dis, Long.MAX_VALUE);dis[0] = 0;PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));pq.offer(new long[]{0, 0});while (!pq.isEmpty()) {long[] dxPair = pq.poll();long dx = dxPair[0];int x = (int) dxPair[1];if (dx > dis[x]) {continue;}for (int[] t : g[x]) {int y = t[0];int w = t[1];long newDis = dx + w;if (newDis < dis[y]) {dis[y] = newDis;pq.offer(new long[]{newDis, y});}}}boolean[] ans = new boolean[edges.length];// 图不连通if (dis[n - 1] == Long.MAX_VALUE) {return ans;}// 从终点出发 BFSboolean[] vis = new boolean[n];dfs(n - 1, g, dis, ans, vis);return ans;}private void dfs(int y, List<int[]>[] g, long[] dis, boolean[] ans, boolean[] vis) {vis[y] = true;for (int[] t : g[y]) {int x = t[0];int w = t[1];int i = t[2];if (dis[x] + w != dis[y]) {continue;}ans[i] = true;if (!vis[x]) {dfs(x, g, dis, ans, vis);}}}
}

来源

LeetCode

这篇关于Leetcode 第394场周赛 问题和解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/923541

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符