leetcode2023-08-11

K 次调整数组大小浪费的最小总空间

class Solution {
    public int minSpaceWastedKResizing(int[] nums, int k) {
        int n = nums.length;
        int[][] g = new int[n][n];
        for (int i = 0; i < n; ++i) {
            int max = Integer.MIN_VALUE;
            int sum = 0;
            for (int j = i; j < n; ++j) {
                max = Math.max(max, nums[j]);
                sum += nums[j];
                g[i][j] = max * (j - i + 1) - sum;
            }
        }

        int[][] dp = new int[n][k + 2];

        for (int[] d : dp) {
            Arrays.fill(d, Integer.MAX_VALUE / 2);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k + 1; j++) {
                for (int l = 0; l <= i; l++) {
                    dp[i][j] = Math.min(dp[i][j], (l == 0 ? 0 : dp[l-1][j-1]) + g[l][i]);
                }
            
            }
        }

        return dp[n - 1][k + 1];
    }
}

构造元素不等于两相邻元素平均值的数组

class Solution {
    public int[] rearrangeArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] ans = new int[n];
        int left = 0;
        int right = n - 1;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                ans[i] = nums[left++];
            } else {
                ans[i] = nums[right--];
            }
        }
        return ans;
    }
}

最小化目标值与所选元素的差

class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        int n = mat.length;
        int m = mat[0].length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;
        int overMax = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int tmpMin = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
                if(overMax != Integer.MAX_VALUE){
                    tmpMin = Math.min(mat[i][j] + overMax, tmpMin);
                }
                for (int k = 0; k < target + 1; k++) {
                    if(dp[i][k]){
                        if(k + mat[i][j] < target + 1){
                            dp[i + 1][k + mat[i][j]] = true;
                        }else{
                            tmpMin = Math.min(tmpMin, k + mat[i][j]);
                        }
                    }
                }
            }
            overMax = tmpMin;
        }
        int lessMax = Integer.MAX_VALUE;
        for (int i = target; i >= 0; i--) {
            if(dp[n][i]){
                lessMax = target - i;
                break;
            }

        }
        return Math.min(lessMax, overMax - target);
    }
}

完成任务的最少工作时间段

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        int m = 1 << n;
        final int INF = 20; 
        int[] dp = new int[m];
        Arrays.fill(dp, INF);
        for (int i = 1; i < m; ++i) {
            int state = i, idx = 0;
            int spend = 0;
            while (state > 0) {
                int bit = state & 1;
                if (bit == 1) {
                    spend += tasks[idx];
                }
                state >>= 1;
                idx++;
            }
            if (spend <= sessionTime) {
                // 阶段i在一个时间点内就能完成
                dp[i] = 1;
            }
        }
        
        for (int i = 1; i < m; ++i) {
            if (dp[i] == 1) {
                continue;
            }
            int split = i >> 1;
            for (int j = (i - 1) & i; j > split; j = (j - 1) & i) {
                dp[i] = Math.min(dp[i], dp[j] + dp[i ^ j]);
            }
        }
        return dp[m - 1];
    }
}

访问完所有房间的第一天

class Solution {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int mod = 1_000_000_000 + 7;
        int n = nextVisit.length;
        long[] dp = new long[n];
        dp[0] = 1;
        for (int i = 1; i < n; ++i) {
            // 根据题意可知 访问到x点时， 前面所有的点的访问次数必为偶数 设dp[x] 为第一次访问到x时 所需要的天数 dp[x] - dp[y] y < x就是 从第一次访问到y点 到 第一次访问 x 点 需要的天数

            dp[i] = (mod + 2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2) % mod;
        }
        return (int) ((dp[n - 1] - 1 + mod) % mod);
    }
}