【LeetCode每日一题合集】2023.10.23-2023.10.29（简单的一周）

2678. 老人的数目（简单遍历模拟）

https://leetcode.cn/problems/number-of-senior-citizens/description/?envType=daily-question&envId=2023-10-23

class Solution {
    public int countSeniors(String[] details) {
        int ans = 0;
        for (String s: details) {
            int age = (s.charAt(11) - '0') * 10 + s.charAt(12) - '0';
            ans += age > 60? 1: 0;
        }
        return ans;
    }
}

会比下面的代码快一些。

class Solution {
    public int countSeniors(String[] details) {
        int ans = 0;
        for (String detail: details) {
            int age = Integer.parseInt(detail.substring(11, 13));
            ans += age > 60? 1: 0;
        }
        return ans;
    }
}

1155. 掷骰子等于目标和的方法数（动态规划）

https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/description/?envType=daily-question&envId=2023-10-24

提示：

1 <= n, k <= 30
1 <= target <= 1000

数据范围很小，采用三层循环。

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        long[][] dp = new long[n + 1][target + 1];
        final long MOD = (long)1e9 + 7;
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {          // 枚举骰子
            for (int j = 1; j <= k; j++) {      // 枚举当前面
                for (int x = 0; x <= target - j; ++x) { // 枚举上个骰子的和
                    dp[i][x + j] = (dp[i][x + j] + dp[i - 1][x]) % MOD;
                }
            }
        }
        return (int)dp[n][target];
    }
}

2698. 求一个整数的惩罚数（预处理+dfs回溯）

https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/description/?envType=daily-question&envId=2023-10-25

提示：
1 <= n <= 1000

class Solution {
    static int[] ans = new int[1001];
    static int target = 0;
    // 预处理
    static {
        for (int i = 1; i <= 1000; ++i) {
            if (op(i)) {
                ans[i] = ans[i - 1] + i * i;
            } else ans[i] = ans[i - 1];
        }
    }

    public int punishmentNumber(int n) {
        System.out.println(op(1));
        return ans[n];
    }

    // 判断x是否满足条件
    public static boolean op(int x) {
        String s = String.valueOf(x * x);
        target = x;
        return dfs(s, 0, 0);
    }

    public static boolean dfs(String s, int i, int t) {
        if (i == s.length() && t == target) return true;
        if (i >= s.length()) return false;
        boolean res = false;
        for (int j = i + 1; j <= s.length() && !res; ++j) {
            res |= dfs(s, j, t + Integer.parseInt(s.substring(i, j)));
        }
        return res;
    }
}

2520. 统计能整除数字的位数（简单模拟）

https://leetcode.cn/problems/count-the-digits-that-divide-a-number/description/?envType=daily-question&envId=2023-10-26

提示：
1 <= num <= 10^9
num 的数位中不含 0

class Solution {
    public int countDigits(int num) {
        int t = num, ans = 0;
        while (t != 0) {
            if (num % (t % 10) == 0) ans++;
            t /= 10;
        }
        return ans;
    }
}

1465. 切割后面积最大的蛋糕（贪心）

https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/?envType=daily-question&envId=2023-10-27

贪心得想，任意两个长和宽都可以组合起来。那么最大面积就是由最大的长和宽组合起来的结果。

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        int m = horizontalCuts.length, n = verticalCuts.length;
        int mxH = Math.max(h - horizontalCuts[m - 1], horizontalCuts[0]), mxW = Math.max(w - verticalCuts[n - 1], verticalCuts[0]);
        for (int i = 1; i < m; ++i) mxH = Math.max(mxH, horizontalCuts[i] - horizontalCuts[i - 1]);
        for (int i = 1; i < n; ++i) mxW = Math.max(mxW, verticalCuts[i] - verticalCuts[i - 1]);
        return (int)((long)mxH * mxW % (long)(1e9 + 7));
    }
}

2558. 从数量最多的堆取走礼物（优先队列）

https://leetcode.cn/problems/take-gifts-from-the-richest-pile/description/?envType=daily-question&envId=2023-10-28

提示：
1 <= gifts.length <= 10^3
1 <= gifts[i] <= 10^9
1 <= k <= 10^3

class Solution {
    public long pickGifts(int[] gifts, int k) {
        long s = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int g: gifts) {
            s += g;
            pq.offer(g);
        }
        for (int i = 0 ; i < k; ++i) {
            int v = pq.poll(), x = (int)Math.sqrt(v);
            s -= v - x;
            pq.offer(x);
        }
        return s;
    }
}

274. H 指数（二分查找）

https://leetcode.cn/problems/h-index/description/?envType=daily-question&envId=2023-10-29

提示：

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

先排序，再二分

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length, l = 0, r = n; // 二分h
        while (l < r) {
            int mid = l + r + 1 >> 1, v = citations[n - mid];
            if (v >= mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
}

O(n)计数排序

见：https://leetcode.cn/problems/h-index/solutions/869042/h-zhi-shu-by-leetcode-solution-fnhl/

倒序枚举统计引用数量>=i的论文数量。

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length, tot = 0;
        int[] cnt = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            cnt[Math.min(citations[i], n)]++;
        }
        for (int i = n; i >= 0; --i) {
            tot += cnt[i];
            if (tot >= i) return i;
        }
        return 0;
    }
}