lcpBi109

第一题检查数组是否是好的

方法一：

class Solution {
    public boolean isGood(int[] nums) {
        int n = nums.length;
        if (n < 2)
            return false;
        if (n == 2) {
            if (nums[0] == 1 && nums[1] == 1)
                return true;
            else
                return false;
        }
        int[] count = new int[201];
        int max = 0;
        for (int i = 0; i < n; ++i) {
            count[nums[i]]++;
            max = Math.max(max, nums[i]);
        }
        if (n < max + 1)
            return false;
//        if (nums[max - 2] != nums[max - 1])
//            return false;
        if (count[max] != 2)
            return false;
        for (int i = 1; i < n; ++i) {
            if (i == n || i == n - 1)
                break;
            if (count[i] != 1)
                return false;
        }
        return true;
    }
}

第二题将字符串中的元音字母排序

方法一：

class Solution {
    public String sortVowels(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder(s);
        List<Integer> emptyIndex = new LinkedList<>();
        int[] count = new int[128];
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (ch == 'a' || ch == 'A' || ch == 'e' || ch == 'E' || ch == 'i' || ch == 'I' || ch == 'o' || ch == 'O' || ch == 'u' || ch == 'U') {
                emptyIndex.add(i);
                ++count[ch];
            }
        }
        int[] temp = emptyIndex.stream().mapToInt(i->i).toArray();
        for (int i = 0; i < temp.length; ++i) {
            int index = temp[i];
            char ch = ' ';
            if (count['A'] > 0) {
                --count['A'];
                sb.setCharAt(index, 'A');
            }
            else if (count['E'] > 0) {
                sb.setCharAt(index, 'E');
                --count['E'];
            }
            else if (count['I'] > 0) {
                sb.setCharAt(index, 'I');
                --count['I'];
            }
            else if (count['O'] > 0) {
                sb.setCharAt(index, 'O');
                --count['O'];
            }
            else if (count['U'] > 0) {
                sb.setCharAt(index, 'U');
                --count['U'];
            }
            else if (count['a'] > 0) {
                sb.setCharAt(index, 'a');
                --count['a'];
            }
            else if (count['e'] > 0) {
                sb.setCharAt(index, 'e');
                --count['e'];
            }
            else if (count['i'] > 0) {
                sb.setCharAt(index, 'i');
                --count['i'];
            }
            else if (count['o'] > 0) {
                sb.setCharAt(index, 'o');
                --count['o'];
            }
            else if (count['u'] > 0) {
                sb.setCharAt(index, 'u');
                --count['u'];
            }
        }

        return sb.toString();
    }
}

第三题访问数组中的位置使分数最大

方法一：记忆化搜索

选或不选

class Solution {
    public long maxScore(int[] nums, int x) {
        this.nums = nums;
        this.x = x;
        n = nums.length;
        dp = new long[n][2];
        for (long[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(1, nums[0] % 2) + nums[0];
    }

    long[][] dp;

    private long dfs(int index, int k) {
        if (index == n)
            return 0;
        if (dp[index][k] != -1)
            return dp[index][k];
        int num = nums[index], v = num % 2;
        long pass = dfs(index + 1, k);
        long choose = dfs(index + 1, v) + num - (k != v ? x : 0);
        return dp[index][k] = Math.max(pass, choose);
    }

    int[] nums;
    int x, n;
}

第四题

2787. 将一个数字表示成幂的和的方案数

方法一：01背包

class Solution {
    public int numberOfWays(int n, int x) {
        int mod = (int) 1e9 + 7;
        // 01背包， 从1^x, 2^x,...,n^x里选物品，恰好能装满容量为n的背包的方案数
        int[][] dp = new int[n + 1][n + 1];
        // 没有物品，恰好装满容量为0的背包的方案数：1,什么都不装
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            int s = (int) Math.pow(i, x);
            for (int j = 0; j <= n; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= s)
                    dp[i][j] = (dp[i][j] +  dp[i - 1][j - s]) % mod;
            }
        }
        return dp[n][n];
    }
}

方法二：滚动数组

class Solution {
    public int numberOfWays(int n, int x) {
        int mod = (int) 1e9 + 7;
        // 01背包， 从1^x, 2^x,...,n^x里选物品，恰好能装满容量为n的背包的方案数
        int[] dp = new int[n + 1];
        // 没有物品，恰好装满容量为0的背包的方案数：1,什么都不装
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int s = (int) Math.pow(i, x);
            for (int j = n; j >= s; --j) {
                dp[j] = (dp[j] +  dp[j - s]) % mod;
            }
        }
        return dp[n];
    }
}

方法三：静态处理

所有x,n在static语句块中处理好

class Solution {
    static int[][] dp;
    static {
        int n = 300, x = 5;
        int mod = (int) 1e9 + 7;
        // 01背包， 从1^x, 2^x,...,n^x里选物品，恰好能装满容量为n的背包的方案数
        dp = new int[x][n + 1];
        // 没有物品，恰好装满容量为0的背包的方案数：1,什么都不装
        for (int i = 0; i < x; ++i)
            dp[i][0] = 1;
        for (int k = 1; k <= x; ++k) {
            for (int i = 1; i <= n; ++i) {
                int s = (int) Math.pow(i, k);
                for (int j = n; j >= s; --j) {
                    dp[k - 1][j] = (dp[k - 1][j] +  dp[k - 1][j - s]) % mod;
                }
            }
        }
    }
    public int numberOfWays(int n, int x) {
        return dp[x - 1][n];
    }
}