数学
leetcode238. 除自身以外数组的乘积
法一：乘积 = 当前数左边的乘积 * 当前数右边的乘积
leetcode169. 多数元素
法一：排序
法二：摩尔投票
leetcode343. 整数拆分
法一：数学推导
leetcode89. 格雷编码
法一：归纳法
leetcode1823. 找出游戏的获胜者
法一：递归
法二：迭代
leetcode400. 第 N 位数字
法一：直接计算
leetcode233. 数字 1 的个数
法一：逐位相加
leetcode238. 除自身以外数组的乘积
238. 除自身以外数组的乘积
https://leetcode.cn/problems/product-of-array-except-self/
法一：乘积 = 当前数左边的乘积 * 当前数右边的乘积
public class Method01 {public int[] productExceptSelf(int[] nums) {int n = nums.length; // 获取输入数组的长度int[] res = new int[n]; // 初始化结果数组res[0] = 1; // 有效地设置 res[0] 的初始值为 1// 第一个循环：计算每个位置左侧所有元素的乘积for (int i = 1; i < n; i++) {res[i] = res[i - 1] * nums[i - 1]; // res[i] 是 nums[0] 到 nums[i-1] 的乘积}int right = 1; // 初始化右侧乘积为 1// 第二个循环：从右到左，计算每个位置右侧所有元素的乘积，并与左侧乘积相乘for (int i = n - 2; i >= 0; i--) {right *= nums[i + 1]; // 计算右侧元素的乘积res[i] *= right; // 将右侧乘积与左侧乘积相乘，存储结果到 res[i]}return res; // 返回最终结果数组}
}
leetcode169. 多数元素
169. 多数元素https://leetcode.cn/problems/majority-element/
法一：排序
public class Method01 {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}
}法二：摩尔投票
public class Method02 {public int majorityElement(int[] nums) {int count = 0; // 计数器，初始化为 0int major_number = 0; // 存储当前的主要元素// 遍历数组中的每一个元素for (int num : nums) {// 当计数器为 0 时，更新主要元素为当前元素if (count == 0) {major_number = num; // 更新主要元素count++; // 计数器加 1} else {// 如果当前元素与主要元素相同，增加计数if (num == major_number) {count++; // 计数器加 1} else {count--; // 否则减少计数}}}return major_number; // 返回最终的主要元素}
}
leetcode343. 整数拆分
343. 整数拆分https://leetcode.cn/problems/integer-break/
法一：数学推导
public class Method01 {public int integerBreak(int n) {// 当 n 小于等于 3 时，返回 n - 1// 因为 2 只能拆分成 1 + 1，3 只能拆分成 1 + 2if (n <= 3) return n - 1;int beishu = n / 3; // 计算可以拆分为多少个 3int yushu = n % 3; // 计算 n 除以 3 的余数// 根据余数的值计算结果：// - 如果余数为 0，返回 3^(beishu-1) * 3// - 如果余数为 1，返回 3^(beishu-1) * 4// - 如果余数为 2，返回 3^(beishu-1) * 6return (int) Math.pow(3, beishu - 1) * (yushu == 0 ? 3 : yushu == 1 ? 4 : 6);}
}leetcode89. 格雷编码
89. 格雷编码https://leetcode.cn/problems/gray-code/
法一：归纳法
public class Method01 {public List<Integer> grayCode(int n) {List<Integer> res = new ArrayList<>(); // 创建一个列表用于存储结果res.add(0); // 将 0 添加到结果中，表示 Gray 码的起始值int head = 1; // 初始化头部值为 1// 外层循环迭代 n 次，每次增加一个二进制位for (int i = 0; i < n; i++) {int size = res.size(); // 当前结果列表的大小// 内层循环反向遍历已有结果列表，将新生成的 Gray 码添加到结果列表中for (int j = size - 1; j >= 0; j--) {res.add(res.get(j) + head); // 根据当前的头部值生成新的 Gray 码}head <<= 1; // 将头部值左移一位，以便为下一个二进制位生成 Gray 码}return res; // 返回最终生成的 Gray 码列表}
}leetcode1823. 找出游戏的获胜者
1823. 找出游戏的获胜者https://leetcode.cn/problems/find-the-winner-of-the-circular-game/
法一：递归
public class Method01 {public int findTheWinner(int n, int k) {if (n == 1) {return 1; // 当只有一个人时，赢家是第一人}// 使用递归公式计算赢家return (k + findTheWinner(n - 1, k) - 1) % n + 1;}
}法二：迭代
public class Method02 {public int findTheWinner(int n, int k) {int winner = 1; // 初始化赢家，假设在第一个人中选择赢家// 从第二个人开始迭代到第 n 个人for (int i = 2; i <= n; i++) {// 根据当前人数和步长计算赢家的位置winner = (k + winner - 1) % i + 1;}return winner; // 返回最终赢家}
}
leetcode400. 第 N 位数字
400. 第 N 位数字https://leetcode.cn/problems/nth-digit/
法一：直接计算
public class Method01 {// 该方法用于找到第n个数字public int findNthDigit(int n) {// count 表示当前位数下的数字总数long count = 9;// digit 表示当前数字的位数int digit = 1;// start 表示当前位数下的第一个数字long start = 1;// 当 n 大于当前位数下的数字总数时，继续循环while (n > count) {// 从 n 中减去当前位数下的数字总数n -= count;// 将 start 更新为下一个位数下的第一个数字start *= 10;// 将 digit 增加1，并更新 count 为下一个位数下的数字总数count = ++digit * 9 * start;}// 计算出第n个数字所在的数字long num = start + (n - 1) / digit;// 计算出第n个数字在 num 中的位置int index = (n - 1) % digit;// 返回 num 中对应位置的数字return Long.toString(num).charAt(index) - '0';}
}
leetcode233. 数字 1 的个数
233. 数字 1 的个数https://leetcode.cn/problems/number-of-digit-one/
法一：逐位相加
public class Method01 {// 计算从1到n的所有整数中，数字1出现的总次数public int countDigitOne(int n) {int digit = 1, res = 0; // digit表示当前处理的位数（个位、十位、百位等），res用于存储最终的结果int high = n / 10, cur = n % 10, low = 0; // high表示当前位的高位部分，cur表示当前位，low表示当前位的低位部分// 当high和cur都不为0时，循环继续while (high != 0 || cur != 0) {// 根据当前位的值更新结果if (cur == 0) {// 如果当前位为0，1出现的次数为high * digitres += high * digit;} else if (cur == 1) {// 如果当前位为1，1出现的次数为high * digit + low + 1res += high * digit + low + 1;} else {// 如果当前位大于1，1出现的次数为(high + 1) * digitres += (high + 1) * digit;}// 更新低位和当前位low += cur * digit; // 更新低位部分cur = high % 10; // 更新当前位high /= 10; // 更新高位部分digit *= 10; // 更新当前位数}// 返回计算得到的1出现的次数return res;}
}