No.1 分割字符串的最大得分

★解题思路

枚举分割的位置, 数该位置之前有多少个 0, 之后有多少个 1 即可.

我们可以通过预处理出前缀和以及后缀和来快速计算某个位置之前有多少个 0, 之后有多少个 1.

代码展示

class Solution { 
   public int maxScore(String s) { 
       if (s == null || s.length() == 0) { 
           return 0; 
       } 
       int n = s.length(); 
       char[] str = s.toCharArray(); 
       int[] leftZero = new int[n];  // leftZero[i] 表示 [0, i] 有多少个 0 
       int[] rightOne = new int[n];  // rightOne[i] 表示 [i, n) 有多少个 1 
       leftZero[0] = str[0] == '0' ? 1 : 0; 
       for (int i = 1; i < n; i++) { 
           leftZero[i] = leftZero[i - 1] + (str[i] == '0' ? 1 : 0); 
       } 
       rightOne[n - 1] = str[n - 1] == '1' ? 1 : 0; 
       for (int i = n - 2; i >= 0; i--) { 
           rightOne[i] = rightOne[i + 1] + (str[i] == '1' ? 1 : 0); 
       } 
       int res = 0; 
       // 枚举分割位置, [0, i] 为左半, (i, n) 为右半 
       for (int i = 1; i < n; i++) { 
           res = Math.max(res, leftZero[i - 1] + rightOne[i]); 
       } 
       return res; 
   } 
}

No.2 可获得的最大点数

★解题思路

这个题目与第一题有一定相似之处. 直接枚举有多少个数从开头取, 有多少个数从尾部取即可.

从开头取的数的和可以通过预处理的前缀和快速得到, 而从尾部取的对应后缀和.

代码展示

class Solution { 
   public int maxScore(int[] cardPoints, int k) { 
       int n = cardPoints.length; 
       // 预处理前缀和以及后缀和 
       int[] prefixSum = new int[n]; 
       int[] sufixSum = new int[n]; 
       prefixSum[0] = cardPoints[0]; 
       for (int i = 1; i < n; i++) { 
           prefixSum[i] = prefixSum[i - 1] + cardPoints[i]; 
       } 
       sufixSum[n - 1] = cardPoints[n - 1]; 
       for (int i = n - 2; i >= 0; i--) { 
           sufixSum[i] = sufixSum[i + 1] + cardPoints[i]; 
       } 
       if (k >= n) { 
           return prefixSum[n - 1]; 
       } 
       int res = Math.max(prefixSum[k - 1], sufixSum[n - k]);  // 特例, 全从开头/尾部 
       // 枚举从开头取多少个 (i + 1), 从尾部取多少个 (k - i - 1) 
       for (int i = 0; i < k - 1; i++) { 
           res = Math.max(res, prefixSum[i] + sufixSum[n - k + i + 1]); 
       } 
       return res; 
   } 
}

No.3对角线遍历 II

★解题思路

计算每个位置的排名, 然后根据排名构造答案数组, 详见代码注释.

代码展示

class Solution { 
   public int[] findDiagonalOrder(List<List<Integer>> nums) { 
       // 由于每个列表可能长短不一, 所以排名不一定连续, 所以使用 Map 记录排名 
       Map<Long,Integer> rank = new HashMap<>(); 
       long minRank = Integer.MAX_VALUE, maxRank = Integer.MIN_VALUE; 
       for (int x = 0; x < nums.size(); x++) { 
           for (int y = 0; y < nums.get(x).size(); y++) { 
               // 一个位于 (x, y) 的数, 排在它前面的有 (1 + x + y) * (x + y) 个 
               // (因为它前面有 x + y 条对角线, 每条对角线的元素数量为 1, 2, 3 ...) 
               // (该元素是当前对角线的第 y 个) 
               long r = (long)(1 + x + y) * (x + y) / 2 + y; 
               rank.put(r, nums.get(x).get(y)); 
               minRank = Math.min(minRank, r); 
               maxRank = Math.max(maxRank, r); 
           } 
       } 
       // 取出 key, 排序, 提取答案 
       long[] keys = rank.keySet().stream().mapToLong(i -> i).toArray(); 
       Arrays.sort(keys); 
       int[] res = new int[keys.length]; 
       for (int i = 0; i < res.length; i++) { 
           res[i] = rank.get(keys[i]); 
       } 
       return res; 
   } 
}

No.4带限制的子序列和

★解题思路

动态规划问题.

定义状态: dp[i] 表示以 nums[i] 结尾的最大和是多少

状态转移: 枚举上一个数字是谁 dp[i] = max{ dp[j], 0 } + nums[i] i - j < k

优化: 直接转移会超时, 时间复杂度 o(n^2), 所以使用单调队列来优化转移过程: 如果 j1 < j2 & dp[j1] < dp[j2] 那么 j1 一定不会再被用来转移 ( j2 一定更优)

代码展示

class Pair { 
   public int idx, sum; 
   public Pair(int idx, int sum) { 
       this.idx = idx; 
       this.sum = sum; 
   } 
} 

class Solution { 
   public int constrainedSubsetSum(int[] nums, int k) { 
       int n = nums.length; 
       LinkedList<Pair> que = new LinkedList<>();  // 单调队列 
       int res = nums[0]; 
       que.add(new Pair(0, nums[0])); 
       for (int i = 1; i < n; i++) { 
           // 把距离超过 k 的删去 
           while (!que.isEmpty() && k < i - que.getFirst().idx) { 
               que.pollFirst(); 
           } 
           // 计算 dp[i] 
           Pair dpi = new Pair(i, nums[i]); 
           if (!que.isEmpty()) { 
               dpi.sum = Math.max(dpi.sum, nums[i] + que.getFirst().sum); 
           } 
           res = Math.max(res, dpi.sum); 
           // 将 dp[i] 入队 
           while (!que.isEmpty() && que.getLast().sum < dpi.sum) { 
               que.pollLast(); 
           } 
           que.add(dpi); 
       } 
       return res; 
   } 
}