Leetcode - 144双周赛

ops/2024/11/28 22:12:21/

目录

一,3360. 移除石头游戏

二,3361. 两个字符串的切换距离

三,3362. 零数组变换 III

四,3363. 最多可收集的水果数目


一,3360. 移除石头游戏

本题直接模拟过程,可以额外使用一个布尔变量标记谁赢,也可以通过 a (a = 10)最终的奇偶性来判断谁赢。

代码如下:

class Solution {public boolean canAliceWin(int n) {int a = 10;while(n >= a){n -= a;a -= 1;}return a%2 == 1;}
}

二,3361. 两个字符串的切换距离

对于每一个下标 i,想要将 s[i] 转换成 t[i],题目给了两种做法:

  • 每次向前移动 1 次,例如:从字符 'b' 转换成字符 'a'  需要的代价为 previousCost['b']
  • 每次向后移动 1 次,例如:从字符 'b' 转换成字符 'c'  需要的代价为 nextCost['b']

所以可以使用前缀和进行预处理,这样在枚举 s,t 时可以在 O(1) 的时间算出使用操作一/操作二所需的代价,求其中最小代价,加入答案,最终获得的就是答案。

这里使用前缀和计算代价还是挺绕的,画个图理解一下:

class Solution {public long shiftDistance(String ss, String tt, int[] nextCost, int[] previousCost) {char[] s = ss.toCharArray();char[] t = tt.toCharArray();long[] next = new long[27];long[] pre = new long[27];for(int i=0; i<26; i++){next[i+1] = next[i] + nextCost[i];//向后pre[i+1] = pre[i] + previousCost[i];//向前}int n = s.length;long ans = 0;for(int i=0; i<n; i++){int l = s[i] - 'a' + 1, r = t[i] - 'a' + 1;long x = l <= r ? next[r-1] - next[l-1] : next[26] - next[l-1] + next[r-1];long y = l >= r ? pre[l] - pre[r] : pre[26] - pre[r] + pre[l];ans += Math.min(x, y);}return ans;}
} 

三,3362. 零数组变换 III

对于下标 i 来说,如果 nums[i] > 0 且之前已经全为0,如何挑选queries数组中的元素[L,R],当 L 满足条件时(L <= i),贪心的想,一定是 R 越大越好,这样可以包含的范围更广,后续的操作就会更少。所以需要一个最大堆来维护满足条件(L <= i)的右端点R,然后不断选取 R 最大的区间进行操作,直到当前 num[i] 为 0.

在枚举 nums 数组挑选queries的区域时,需要满足 i 在 [L,R] 的区间,所以需要先将 queries 数组按照左端点 L 进行排序。

剩下的就是使用差分数组去维护区间的-1/+1操作了。

代码如下:

class Solution {public int maxRemoval(int[] nums, int[][] queries) {PriorityQueue<Integer> que = new PriorityQueue<>((x,y)->y-x);Arrays.sort(queries,(x,y)->x[0]-y[0]);int n = nums.length;int[] diff = new int[n+1];int sum = 0, j = 0;for(int i=0; i<n; i++){sum += diff[i];while(j < queries.length && queries[j][0] <= i){que.offer(queries[j][1]);j++;}//满足 i 在 [L,R] 区间while(sum + nums[i] > 0 && !que.isEmpty() && que.peek() >= i){sum -= 1;diff[que.poll() + 1] += 1;}//sum + nums[i] > 0, 说明不管怎么操作都不能使得nums[i] = 0,直接返回-1if(sum + nums[i] > 0) return -1;}return que.size();}
}

四,3363. 最多可收集的水果数目

本题对每一个小朋友的移动进行计算:

  • 对于从(0,0)小朋友来说,想要在 n - 1 次移动时恰好到达(n-1,n-1)只有一种走法,就是沿着对角线走。
  • 对于从(0,n-1)的小朋友来说,这就是一个简单的走格子问题,就是从(0,n-1)走到 (n-1,n-1)所能收集的最大水果,且根据题意,它所能走的范围是对角线的上半部分,所以实际只要计算从(0,n-1)走到 (n-2,n-1)注:(n-1,n-1)在(0,0)的时候计算过了。
  • 同理,对于从(n-1,0)的小朋友来说,这就是一个简单的走格子问题,就是从(0,n-1)走到 (n-1,n-2)所能收集的最大水果,且根据题意,它所能走的范围是对角线的下半部分。为了更方便,我们可以复用上面的代码,只需要将数组按照对角线翻转一下就行。

代码如下:

class Solution {public int maxCollectedFruits(int[][] f) {int n = f.length;int ans = 0;for(int i=0; i<n; i++){ans += f[i][i];}memo = new int[n][n];for(int[] r : memo) Arrays.fill(r, -1);ans += dfs(0, n-1, f);for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {f[j][i] = f[i][j];}}for(int[] r : memo) Arrays.fill(r, -1);return dfs(0, n-1, f) + ans; }int[][] memo;int[] dirct = new int[]{-1, 0, 1};int dfs(int x, int y, int[][] f){int n = f.length;if(x == n-2) return f[x][y];if(memo[x][y] != -1) return memo[x][y];int res = 0;for(int d : dirct){int j = y + d;if(j >= n || j <= x+1) continue;//保证在对角线上方res = Math.max(res, dfs(x+1, j, f) + f[x][y]);}return memo[x][y] = res;}
}


http://www.ppmy.cn/ops/137486.html

相关文章

【探商宝】大数据获客平台在销售型企业中的应用

在当今竞争激烈的商业环境中&#xff0c;销售型企业越来越依赖于大数据技术来获取潜在客户和优化销售策略。以下是大数据获客平台在销售型企业中的应用的几个关键方面&#xff1a; 全面的数据整合能力&#xff1a; 大数据获客平台能够整合来自多个渠道和平台的企业数据&#xf…

Unity图形学之BRDF双向反射分布函数

1.描述了入射光线在非透明物体表面如何进行反射&#xff0c;也就是说多少光发生了漫反射&#xff0c;多少光发生了镜面反射 BRDF 函数计算的是“特定反射方向的光强与入射光强的比例” 2.各向异性 与 均向性 相反&#xff0c;是指在不同方向具有不同行为的性质&#xff0c;也就…

小程序-基于java+SpringBoot+Vue的网上花店微信小程序设计与实现

项目运行 1.运行环境&#xff1a;最好是java jdk 1.8&#xff0c;我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境&#xff1a;IDEA&#xff0c;Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境&#xff1a;Tomcat 7.x,8.x,9.x版本均可 4.硬件环境&#xff1a…

Leetcode(双指针习题思路总结,持续更新。。。)

讲解题目&#xff1a;两数之和 给定一个已按照 升序排列 的整数数组 numbers &#xff0c;请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 &#xff0c;所以答案数组应当满…

各种排序算法

前置知识 排序: 按照递增或者递减的顺序把数据排列好 稳定性: 值相等的元素在排序之后前后顺序是否发生了改变 内部排序: 数据放在内存上 外部排序: 数据放在磁盘上 内部排序 基于比较的排序 几大排序算法 1. 堆排序 特点: 思想: 1. 创建大根堆,把所有元素放在大根堆里…

Git旧文件覆盖引发思考

一天&#xff0c;我的同事过来找到我&#xff0c;和我讲&#xff1a;张叫兽&#xff0c;大事不好&#xff0c;我的文件被人覆盖了。git是真的不好用啊 git不好用&#xff1f;文件被覆盖&#xff1b;瞬间我似乎知道了什么&#xff0c;让我想到了某位男明星的语法&#xff1a;他…

C语言中使用动态内存

在前面介绍C语言的内存模型时知道C语言中将内存划分为多个区间&#xff1a;栈区、堆区、静态区、常量区、代码区。在方法内定义和使用的变量&#xff0c;如果没有使用static关键字修饰都是在栈区内&#xff0c;该区内定义的变量不需要我们管理&#xff0c;系统会自动申请和释放…

【设计模式】1. 构建器模式(Builder Pattern)是一种创建型设计模式

构建器模式&#xff08;Builder Pattern&#xff09;是一种创建型设计模式&#xff0c;用于分步骤构建复杂对象&#xff0c;同时允许按照不同的需求生成不同的表示。该模式将对象的构建过程与其表示分离&#xff0c;使得相同的构建过程可以创建不同的对象。 核心思想 构建器模…