目录
1. 多数元素
1.1. 题目描述
1.2. 解题思路
方法一：哈希表
方法二：排序
方法三：随机化
方法四：分治
方法五：Boyer-Moore 投票算法
2. 按规则计算统计结果
2.1. 题目描述
2.2. 解题思路
3. 整数拆分
3.1. 题目描述
3.2. 解题思路
方法一：动态规划
方法二：优化的动态规划
方法三：数学
4. 文件组合
4.1. 题目描述
4.2. 解题思路
方法一：枚举 + 暴力
方法二：枚举 + 数学优化
方法三：双指针
5. 破冰游戏
5.1. 题目描述
5.2. 解题思路
方法一：数学 + 递归
6. 数字 1 的个数
6.1. 题目描述
6.2. 解题思路
方法一：枚举每一数位上 111 的个数
7. 第 N 位数字
7.1. 题目描述
7.2. 解题思路
方法一：二分查找
方法二：直接计算
1. 多数元素
1.1. 题目描述
1.2. 解题思路
方法一：哈希表
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
} else {
counts.put(num, counts.get(num) + 1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = countNums(nums);
Map.Entry<Integer, Integer> majorityEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}
return majorityEntry.getKey();
}
}
方法二：排序
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
方法三：随机化
class Solution {
private int randRange(Random rand, int min, int max) {
return rand.nextInt(max - min) + min;
}
private int countOccurences(int[] nums, int num) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
public int majorityElement(int[] nums) {
Random rand = new Random();
int majorityCount = nums.length / 2;
while (true) {
int candidate = nums[randRange(rand, 0, nums.length)];
if (countOccurences(nums, candidate) > majorityCount) {
return candidate;
}
}
}
}
方法四：分治
class Solution {
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
private int majorityElementRec(int[] nums, int lo, int hi) {
// base case; the only element in an array of size 1 is the majority
// element.
if (lo == hi) {
return nums[lo];
}
// recurse on left and right halves of this slice.
int mid = (hi - lo) / 2 + lo;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid + 1, hi);
// if the two halves agree on the majority element, return it.
if (left == right) {
return left;
}
// otherwise, count each element and return the "winner".
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length - 1);
}
}
方法五：Boyer-Moore 投票算法
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
2. 按规则计算统计结果
2.1. 题目描述
2.2. 解题思路
class Solution {
public int[] statisticalResult(int[] arrayA) {
int len = arrayA.length;
if(len == 0) return new int[0];
int[] arrayB = new int[len];
arrayB[0] = 1;
int tmp = 1;
for(int i = 1; i < len; i++) {
arrayB[i] = arrayB[i - 1] * arrayA[i - 1];
}
for(int i = len - 2; i >= 0; i--) {
tmp *= arrayA[i + 1];
arrayB[i] *= tmp;
}
return arrayB;
}
}
3. 整数拆分
3.1. 题目描述
3.2. 解题思路
方法一：动态规划
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
int curMax = 0;
for (int j = 1; j < i; j++) {
curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
}
dp[i] = curMax;
}
return dp[n];
}
}
方法二：优化的动态规划
class Solution {
public int integerBreak(int n) {
if (n <= 3) {
return n - 1;
}
int[] dp = new int[n + 1];
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
}
return dp[n];
}
}方法三：数学
class Solution {
public int integerBreak(int n) {
if (n <= 3) {
return n - 1;
}
int quotient = n / 3;
int remainder = n % 3;
if (remainder == 0) {
return (int) Math.pow(3, quotient);
} else if (remainder == 1) {
return (int) Math.pow(3, quotient - 1) * 4;
} else {
return (int) Math.pow(3, quotient) * 2;
}
}
}
4. 文件组合
4.1. 题目描述
4.2. 解题思路
方法一：枚举 + 暴力
class Solution {
public int[][] fileCombination(int target) {
List<int[]> vec = new ArrayList<int[]>();
int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
for (int i = 1; i <= limit; ++i) {
for (int j = i;; ++j) {
sum += j;
if (sum > target) {
sum = 0;
break;
} else if (sum == target) {
int[] res = new int[j - i + 1];
for (int k = i; k <= j; ++k) {
res[k - i] = k;
}
vec.add(res);
sum = 0;
break;
}
}
}
return vec.toArray(new int[vec.size()][]);
}
}
方法二：枚举 + 数学优化
class Solution {
public int[][] fileCombination(int target) {
List<int[]> vec = new ArrayList<int[]>();
int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
for (int x = 1; x <= limit; ++x) {
long delta = 1 - 4 * (x - (long) x * x - 2 * target);
if (delta < 0) {
continue;
}
int delta_sqrt = (int) Math.sqrt(delta + 0.5);
if ((long) delta_sqrt * delta_sqrt == delta && (delta_sqrt - 1) % 2 == 0) {
int y = (-1 + delta_sqrt) / 2; // 另一个解(-1-delta_sqrt)/2必然小于0，不用考虑
if (x < y) {
int[] res = new int[y - x + 1];
for (int i = x; i <= y; ++i) {
res[i - x] = i;
}
vec.add(res);
}
}
}
return vec.toArray(new int[vec.size()][]);
}
}
方法三：双指针
class Solution {
public int[][] fileCombination(int target) {
List<int[]> vec = new ArrayList<int[]>();
for (int l = 1, r = 2; l < r;) {
int sum = (l + r) * (r - l + 1) / 2;
if (sum == target) {
int[] res = new int[r - l + 1];
for (int i = l; i <= r; ++i) {
res[i - l] = i;
}
vec.add(res);
l++;
} else if (sum < target) {
r++;
} else {
l++;
}
}
return vec.toArray(new int[vec.size()][]);
}
}
5. 破冰游戏
5.1. 题目描述
5.2. 解题思路
方法一：数学 + 递归
class Solution {
public int iceBreakingGame(int num, int target) {
int f = 0;
for (int i = 2; i != num + 1; ++i) {
f = (target + f) % i;
}
return f;
}
}
6. 数字 1 的个数
6.1. 题目描述
6.2. 解题思路
方法一：枚举每一数位上 111 的个数
class Solution {
public int countDigitOne(int n) {
// mulk 表示 10^k
// 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
// 但为了让代码看起来更加直观，这里保留了 k
long mulk = 1;
int ans = 0;
for (int k = 0; n >= mulk; ++k) {
ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
mulk *= 10;
}
return ans;
}
}
7. 第 N 位数字
7.1. 题目描述
7.2. 解题思路
方法一：二分查找
class Solution {
public int findNthDigit(int n) {
int low = 1, high = 9;
while (low < high) {
int mid = (high - low) / 2 + low;
if (totalDigits(mid) < n) {
low = mid + 1;
} else {
high = mid;
}
}
int d = low;
int prevDigits = totalDigits(d - 1);
int index = n - prevDigits - 1;
int start = (int) Math.pow(10, d - 1);
int num = start + index / d;
int digitIndex = index % d;
int digit = (num / (int) (Math.pow(10, d - digitIndex - 1))) % 10;
return digit;
}
public int totalDigits(int length) {
int digits = 0;
int curLength = 1, curCount = 9;
while (curLength <= length) {
digits += curLength * curCount;
curLength++;
curCount *= 10;
}
return digits;
}
}
方法二：直接计算
class Solution {
public int findNthDigit(int n) {
int d = 1, count = 9;
while (n > (long) d * count) {
n -= d * count;
d++;
count *= 10;
}
int index = n - 1;
int start = (int) Math.pow(10, d - 1);
int num = start + index / d;
int digitIndex = index % d;
int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10;
return digit;
}
}
