当前位置：首页 > news >正文

【LeetCode每日一题】2024年8月第一周（上）

news 来源：原创 2024/9/22 11:23:31

2024.7.30 中等

链接：2961. 双模幂运算

（1）题目描述：

（2）示例：

（3）分析：

① 在计算中，反复用到了%10，说明返回的只要取个位即可，对应底数也取个位===》个位只由个位决定，那么很显然对于第一个下标，其只要取得个位就行

② 求次方用到一个循环，因为对于任何个位数的次方，经过4次方后，个位会变为其本身。

比如：2 4 8 16 32==>个位上是：2 4 8 6 2……

（4）代码：

class Solution {public List<Integer> getGoodIndices(int[][] variables, int target) {// Scanner sc=new Scanner(System.in);List<Integer> arr = new ArrayList<>();int i = 0;int a, b, c, ab, m;//分析：在计算中%10，返回的只要取个位即可，对应底数也取个位===》个位只由个位决定for (int[] aq : variables) {a = aq[0] % 10; //定位很显然对于第一个下标，其只要取得个位就行b = (aq[1] % 4 == 0 ? 4 : aq[1] % 4);//这里用到一个循环，因为对于任何个位数的次方，经过4次方后，个位会变为其本身。//比如：2 4 8 16 32==>个位上是：2 4 8 6 2……c = aq[2];//以下就是获取结果的代码化ab = getChu(a, b, 10);m = aq[3];if (getChu(ab, c, m) == target) {arr.add(i);};i++;}return arr;}public int getChu(int chengshu, int jieshu, int m) {int t = 1;for (int i = 0; i < jieshu; i++) {t = (t * chengshu) % m;}return t;}
}

（5）碎碎念：

看题解，好多用到快速幂的，我这大多都是想到啥写啥，哈哈

2024.7.31 中等

链接：3111. 覆盖所有点的最少矩形数目

（1）题目描述：

（2）示例

（3）分析

很显然，本题目中，对y的要求几乎没有，因为最高点位y=yMAX 处，肯定有点存在，所以，只要能让二维数组排序即可==> Arrays.sort(points,(b,a)->b[0]-a[0]) 排序好了之后，实际上就是一个距离判断的题，依据w来判断是否新增。

（4）代码

class Solution {public int minRectanglesToCoverPoints(int[][] points, int w) {//很显然，本题目中，对y的要求几乎没有，因为最高点位y=yMAX 处，肯定有点存在//所以，只要能让二维数组排序即可==>Arrays.sort(points,(b,a)->b[0]-a[0]); //非常好用！// 二维数据实际上也是一维数组，依据首元素判断，大的返回true，对应放后面int begin=points[0][0]; int next=points[0][0]; //定位初始值int sum=1;for(int[] a: points){next = a[0];if( next - begin > w){sum++; //只要间隔超过w，就新增begin=next; //更新位置}}return sum;}
}

（5）碎碎念

很棒！前些天写代码刚用到stream中的sorted，一时间想到了Arrays.sort和比较器。

2024.8.01 简单

链接：LCP 40. 心算挑战

（1）题目描述：

（2）示例

（3）分析

求最大，首先要对数据进行排序，判断为偶数，那么我们可以先得出最大的cnt张。如果为偶数，直接返回，不是,说明需要舍弃一个奇数加一个偶数，或者加一个奇数去一个偶数。如此就需要具体分析：无非：

① 在后续找到：最大的奇数，与选中cnt个里的最小的偶数进行替换；

② 或者：最大的偶数，与cnt个中最小的奇数进行替换。

两者去最大值即可，用同一个值表示，取最大即可

（4）代码

import java.util.Arrays;class Solution {public int maxmiumScore(int[] cards, int cnt) {Arrays.sort(cards);int sum = 0;int returnSum=0;int ji = 0; // 最小的奇数int ou = 0; // 最小的偶数int temp = cards.length - 1;for (int i = temp; i > temp - cnt; i--) {if (cards[i] % 2 == 1) {ji = cards[i]; // 记录当前最小奇数} else {ou = cards[i]; // 记录当前最小偶数}sum += cards[i];}if (sum % 2 == 0) {return sum; // 总和为偶数，直接返回}//在后续找到：最大的奇数，与选中cnt个里的最小的偶数进行替换；//或者：最大的偶数，与cnt个中最小的奇数进行替换。for (int i = cards.length - cnt - 1; i >= 0; i--) {if ((cards[i] & 1) != 0) {//下一个为奇数的情况if (ou != 0) {//排除cnt只有1的情况，和只有偶的情况returnSum = Math.max(returnSum, sum - ou + cards[i]);break;}}}for (int i = cards.length - cnt - 1; i >= 0; i--) {if ((cards[i] & 1) == 0) {if (ji != 0) {returnSum = Math.max(returnSum, sum - ji + cards[i]);break;}}}return returnSum;}
}

（5）碎碎念

你管这叫，简单题？

2024.8.02 中等

链接：128. 直角三角形

（1）题目描述：

（2）示例

（3）分析

对问题定位：要求一行内存在：至少2个1，一列内至少2个1，才有可能出现三角形，这是基本要求，再次转换 ==》数学题，找到定位点（交点），看横竖上有几个点比如横m，竖n，计算公式就是 (m-1)*(n-1) 。

（4）代码

class Solution {public long numberOfRightTriangles(int[][] grid) {// 对问题定位：要求一行内存在：至少2个1，一列内至少2个1，才有可能出现三角形// 再次转换==》数学题int len = grid.length;// 二维数组长int zlen = grid[0].length;// 一维数组长int[] col = new int[len];// 行int[] low = new int[zlen];// 列for (int i = 0; i < len; i++) {col[i] = 0;for (int j = 0; j < zlen; j++) {col[i] += grid[i][j];low[j] += grid[i][j];}}//获取之后long sum = 0;//int超了！卡死个人for (int i = 0; i < len; i++) {for (int j = 0; j < zlen; j++) {//以单纯的行列 无法指定唯一的交点--反转-->//借助点==》求三角形，公式如下，if (grid[i][j]==1) {sum += (col[i] - 1) * (low[j] - 1);}}}return sum;}
}