【刷题宝典NO.1】

Nim游戏

https://leetcode.cn/problems/nim-game/description/

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。

• 你们轮流进行自己的回合， 你作为先手 。

• 每一回合，轮到的人拿掉 1 - 3 块石头。

• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4 输出：false 解释：以下是可能的结果: 1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。 2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。 3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。 在所有结果中，你的朋友是赢家。

示例 2：

输入：n = 1 输出：true

示例 3：

输入：n = 2 输出：true

提示：

• 1 <= n <= 2^31 - 1

/**
题解：
因为是我先手，且每次可以拿掉1-3块石头
因为说的是桌子上有一堆石头，显然石头的数量要>3，因为<=3的时候，肯定都是我先赢
假设此时桌上的石头有4个
我先拿1个或者2个或者3个石头都是输掉比赛的结局
假设此时桌上有5个石头
只要我先拿1块，对方无论拿1块或者2块或者3块石头，都是我赢
但是我先拿2块或者3块，就一定会输，所以这种情况游戏的胜负是可控的
总结：
如果最后只剩下4块石头，无论采取什么策略，由于我是先手，那么我必输
可以对石头的块数进行对4取余，判断这个结果是否不等于0，不等于0的话就说明能赢，否则就是输*/
class Solution {public boolean canWinNim(int n) {return n % 4 != 0;}
}

灯泡开关

https://leetcode.cn/problems/bulb-switcher/submissions/477395544/

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

• 0 <= n <= 109

class Solution {public int bulbSwitch(int n) {// n = 14  , 3.xx// n = 15  , 3.xx// n = 16  , 4// 求小于等于 n 的完全平方数的个数return (int)Math.sqrt(n);}
}

除数博弈 

https://leetcode.cn/problems/divisor-game/description/

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：

• 选出任一 x，满足 0 < x < n 且 n % x == 0 。

• 用 n - x 替换黑板上的数字 n 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

示例 1：

输入：n = 2 输出：true 解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

输入：n = 3 输出：false 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

• 1 <= n <= 1000

class Solution {public boolean divisorGame(int n) {return n % 2 == 0;}
}

提莫攻击 

https://leetcode.cn/problems/teemo-attacking/description/

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的 总 秒数。

 

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

提示：

• 1 <= timeSeries.length <= 104
• 0 <= timeSeries[i], duration <= 107
• timeSeries 按 非递减 顺序排列

public class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int ans = 0; // 结果变量int expired = 0; // 每次中毒结束的时间位置(一开始为0，此时没中毒)for (int i = 0; i < timeSeries.length; i++) {// 1、如果发现当前的时间大于等于了最近一次中毒后得结束时间（说明此时没有中毒）if (timeSeries[i] >= expired) {// 此时收到攻击就中毒了，叠加时间ans += duration;} else {// 否则，如果发现当前的时间小于最近一次中毒后得结束时间// 由于中毒状态不可叠加// 新的中毒截止时间是 timeSeries[i] + duration// 上次中毒截止时间是 expired// 两者相减，获得持续中毒时间ans += timeSeries[i] + duration - expired;}// 更新中毒结束的时间位置expired = timeSeries[i] + duration;}// 返回结果return ans;}
}

 

至少是其他数字两倍的最大数 

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

示例 1：

输入：nums = [3,6,1,0]
输出：1
解释：6 是最大的整数，对于数组中的其他整数，6 至少是数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。

示例 2：

输入：nums = [1,2,3,4]
输出：-1
解释：4 没有超过 3 的两倍大，所以返回 -1 。

/**
题解:我们只需要找出两个数字：最大的数，第二大的数
因为最大数都是第二大数的两倍了，最大数肯定也是其它数的两倍
所以我们只需要遍历一次，在这个遍历过程中确定最大值和第二大的值，同时记录最大值的下标，根据要求进行返回*/
class Solution {public int dominantIndex(int[] nums) {// 最大数int biggest = -1;// 第二大数int bigger = -1;// 最大数所在的索引int index = 0;// 遍历数组 numsfor (int i = 0; i < nums.length; i++) {int num = nums[i];// 如果发现当前元素的值大于了之前找到的最大数if (num > biggest) {// 更新第二大数bigger = biggest;// 更新最大数为 numbiggest = num;// 记录最大数的索引index = i;} else if (num > bigger) {// 更新第二大数bigger = num;}}// 判断一下最大数是否是第二大数的两倍// 如果是，则返回最大数的索引 index// 否则，返回 -1return (biggest >= bigger * 2) ? index : -1;}
}

比赛中的配对次数

给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：

• 如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
• 如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。

返回在比赛中进行的配对次数，直到决出获胜队伍为止。

示例 1：

输入：n = 7
输出：6
解释：比赛详情：
- 第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
- 第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6

示例 2：

输入：n = 14
输出：13
解释：比赛详情：
- 第 1 轮：队伍数 = 14 ，配对次数 = 7 ，7 支队伍晋级。
- 第 2 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。 
- 第 3 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 4 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 7 + 3 + 2 + 1 = 13

提示：

• 1 <= n <= 200

public class Solution {// 计算比赛中的配对次数public int numberOfMatches(int n) {// 结果变量int ans = 0;// 不断的配对比赛，直到剩下一支队伍为止while (n > 1) {// 偶数支队伍if (n % 2 == 0) {// 总共进行 n / 2 场比赛ans += n / 2;// 同时剩下了 n / 2 支队伍n /= 2;} else {// 奇数支队伍// 总共进行 （ n - 1 ） / 2 场比赛ans += (n - 1) / 2;// 同时剩下了 (n - 1) / 2 + 1 支队伍n = (n - 1) / 2 + 1;}}// 获取结果return ans;}
}

【模拟】科大讯飞2023非凡计划-汤姆和杰瑞 

题目描述与示例

题目描述

汤姆在集市上买了1公斤奶酪回家。然而，趁汤姆不在时，杰瑞来偷了A/B公斤的奶酪。问杰瑞偷了奶酪后，汤姆还有多少奶酪?

输入描述

第—行给出两个整数A,B。1 ≤ A < B ≤ 9

输出描述

输出杰瑞偷了奶酪后，汤姆还有多少奶酪。以分数的形式表示，分子和分母用空格间隔。(输出必须满足分母为B)

示例

输入

2 7

输出

5 7

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int A = scanner.nextInt();int B = scanner.nextInt();System.out.println(B - A + " " + B);}
}

【模拟】OPPO2023秋招提前批-小欧的圆覆盖 

题目描述与示例

题目描述

在平面直角坐标系上有一个矩形，和一个定点P。小欧希望以点P为圆心画一个圆覆盖这个矩形，请你求出圆面积的最小值。注：π取3.1415926536

输入描述

第一行输入四个整数x1,y1,x2,y2，代表矩形左下角坐标为(x1,y1)，右上角坐标为(x2,y2)。

第二行输入两个整数xp,yp，代表点P的坐标为(xp,yp)。

输出描述

一个浮点数，代表圆的最小面积。如果你的答案和标准答案的相对误差不超过10^-4，则认为你的答案正确。

示例

输入

0 0 1 1 0 0

输出

6.2831853

解题思路

本题是非常简单的数学模拟题。

为了使得以P为圆心的圆可以覆盖到整个矩形，仅需要枚举圆心P到矩形四个顶点的距离，对四个距离取最大值即可。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int x1 = scanner.nextInt();int y1 = scanner.nextInt();int x2 = scanner.nextInt();int y2 = scanner.nextInt();int x0 = scanner.nextInt();int y0 = scanner.nextInt();double r1 = calDis(x0, y0, x1, y1);double r2 = calDis(x0, y0, x1, y2);double r3 = calDis(x0, y0, x2, y1);double r4 = calDis(x0, y0, x2, y2);double r = Math.max(Math.max(r1, r2), Math.max(r3, r4));double pi = 3.1415926536;double area = r * r * pi;System.out.println(area);}public static double calDis(int x1, int y1, int x2, int y2) {return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));}
}

【模拟】科大讯飞2023非凡计划-数组的最小距离 

题目描述与示例

题目描述

小红定义两个数组a和b之间的距离为

即每个位置的差的绝对值之和，其中n为数组的长度。小红现在可以进行任意次操作，选择任意数组的任意一个元素，使其乘以-1。

小红希望最终两个数组的距离尽可能小。你能帮帮她吗?

输入描述

第一行输入一个正整数， 代表两个数组的长度。

第二行输入n个整数ai，代表第一个数组。

第三行输入n个整数bi，代表第二个数组。

输出描述

一个整数，代表两个数组的最小距离。

示例

输入

3

1 2 3

-3 2 -1

输出

4

解题思路

由于我们可以任意地选择a数组或b数组中的任意一个元素进行操作，对于第i个位置的两个元素差值a[i]-b[i]而言，通过对a[i]或者b[i]进行乘-1的操作可以获得以下四种情况

• a[i]-b[i]

• a[i]+b[i]

• -a[i]-b[i]

• -a[i]+b[i]

取绝对值号后，实际上只有两种情况

• abs(a[i]-b[i]) = abs(-a[i]+b[i])

• abs(a[i]+b[i]) = abs(-a[i]-b[i])

故总的答案应该为每一个位置的abs(a[i]-b[i])和abs(a[i]+b[i])中的较小值，再进行求和。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] a = new int[n];int[] b = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}for (int i = 0; i < n; i++) {b[i] = scanner.nextInt();}int ans = 0;for (int i = 0; i < n; i++) {ans += Math.min(Math.abs(a[i] - b[i]), Math.abs(a[i] + b[i]));}System.out.println(ans);}
}