No.1 非递增顺序的最小子序列

★解题思路

排序之后从大到小选数即可. 代码展示

class Solution { 
   public List<Integer> minSubsequence(int[] nums) { 
       Arrays.sort(nums); 
       int sum = 0;  // nums 中全部元素的和 
       for (int num : nums) { 
           sum += num; 
       } 
       int resSum = 0; 
       List<Integer> res = new ArrayList<>(); 
       // 从大到小选数, 直到已经选出的数的和超过总和的一半 
       for (int i = nums.length - 1; i >= 0 && resSum * 2 <= sum; i--) { 
           res.add(nums[i]); 
           resSum += nums[i]; 
       } 
       return res; 
   } 
}

No.2 将二进制表示减到 1 的步骤数

★解题思路

模拟二进制大整数运算:

加 1 则模拟加法运算, 依次处理进位

除以 2 则直接从末尾删去一位即可.

为了在进位导致位数增加时处理方便, 我们将字符串倒过来处理. 代码展示

class Solution { 
   public int numSteps(String s) { 
       StringBuilder sb = new StringBuilder(s); 
       sb.reverse();  // 倒过来处理 
       int res = 0; 
       for (; sb.length() > 1; res++) { 
           if (sb.charAt(0) == '0') {  // 末位是 0, 是偶数, 除以 2, 直接删除末位 
               sb.deleteCharAt(0); 
           } else { 
               int carry = 1;  // 表示当前位的进位 
               // 当进位为 0 时就不需要再加了 
               for (int i = 0; 0 < carry && i < sb.length(); i++) { 
                   if (sb.charAt(i) == '1') {  // 当前位是 1, 加上 1 又需要进位 
                       sb.setCharAt(i, '0'); 
                       carry = 1; 
                   } else { 
                       sb.setCharAt(i, '1'); 
                       carry = 0; 
                   } 
               } 
               if (carry > 0) {  // 到最后还有一个进位, 说明位数需要加一 
                   sb.append('1'); 
               } 
           } 
       } 
       return res; 
   } 
}

No.3 最长快乐字符串

★解题思路

贪心法.

哪种字符剩的最多就往末尾添加一个该字符, 而如果该字符已经有连续的两个了, 那么添加第二多的. 直到无法再添加为止. 代码展示

class Pair { 
   public char chr; 
   public int cnt; 
   public Pair(char chr, int cnt) { 
       this.chr = chr; 
       this.cnt = cnt; 
   } 
} 

class Solution { 
   public String longestDiverseString(int a, int b, int c) { 
       Pair[] pairs = new Pair[3]; 
       pairs[0] = new Pair('a', a); 
       pairs[1] = new Pair('b', b); 
       pairs[2] = new Pair('c', c); 
       StringBuilder res = new StringBuilder();   
       // last1 = chr 而 last2 = '0' 表示目前末尾只有一个 chr 
       // last1 = last2 = chr 表示目前末尾已经有两个连续的 chr (即不能再添加 chr) 
       char last1 = '0', last2 = '0'; 
       while (true) { 
           // 排序, 按照剩余数量从大到小 
           Arrays.sort(pairs, (p1, p2) -> (p2.cnt - p1.cnt)); 
           // 如果末尾已经有两个连续的当前剩余最多的字符, 那么就不能添加它, 而是添加第二多的 
           int idx = pairs[0].chr == last2 ? 1 : 0; 
           if (pairs[idx].cnt == 0) {  // 无法再添加, 停止 
               break; 
           } 
           // 添加第 idx 多的字符 
           res.append(pairs[idx].chr); 
           pairs[idx].cnt--; 
           // 正确设置 last1 和 last2 
           if (last1 == pairs[idx].chr) { 
               last2 = pairs[idx].chr; 
           } else { 
               last1 = pairs[idx].chr; 
               last2 = '0'; 
           } 
       } 
       return res.toString(); 
   } 
}

No.4 石子游戏 III

★解题思路

动态规划问题.

定义状态: f[i] 表示面对 i 到 n-1 的石子时, 先手的人能拿到的最大和

状态转移: 考虑到当前的决策只有拿 1 个, 2 个或者 3 个, 所以在这三种决策中取最优的即可.

f[i] = max{ sum[i] - sum[i + j] + sum[i + j] - f[i + j] } 1 ≤ j ≤ 3 其中 sum[i] 表示 i 到 n - 1 的石子的分数总和, 即一个后缀和.

sum[i] - sum[i + j] 表示拿 j 个石子得到的分数 .

sum[i + j] - f[i + j] 表示拿了 j 个石子之后, 下一个人拿一轮后, 我们还能拿到的分数之和.

初始边界: f[n] = 0, f[other] = -inf

代码展示

class Solution { 
   public String stoneGameIII(int[] stoneValue) { 
       int n = stoneValue.length; 
       int[] sum = new int[n + 1]; 
       int[] f = new int[n + 1]; 
       Arrays.fill(f, Integer.MIN_VALUE); 
       f[n] = 0; 
       for (int i = n - 1; i >= 0; i--) { 
           sum[i] = stoneValue[i] + sum[i + 1]; 
           for (int j = 1; j <= Math.min(3, n - i); j++) { 
               f[i] = Math.max(f[i], sum[i] - sum[i + j] + sum[i + j] - f[i + j]); 
           } 
       } 
       if (f[0] * 2 == sum[0]) { 
           return "Tie"; 
       } else if (f[0] * 2 > sum[0]) { 
           return "Alice"; 
       } else { 
           return "Bob"; 
       } 
   } 
}

最终答案: f[0] 与 总和 - f[0] 比较, 前者就是先手的人 Alice 能拿到的最大分数, 后者则是 Bob 也取最优策略时的分数.