No.1 Merge Strings Alternately

解题思路

简单的双指针遍历合并字符串

代码展示

public String mergeAlternately(String word1, String word2) { 
       if (word1 == null || word1.length() == 0) { 
           return word2; 
       } 
       if (word2 == null || word2.length() == 0) { 
           return word1; 
       } 
       int index = 0; 
       char[] res = new char[word1.length() + word2.length()]; 
       int i = 0, j = 0; 
       char[] w1 = word1.toCharArray(); 
       char[] w2 = word2.toCharArray(); 
       // 简单双指针归并两个字符数组 
       while (i < w1.length && j < w2.length) { 
           res[index++] = w1[i++]; 
           res[index++] = w2[j++]; 
       } 
       while (i < w1.length) { 
           res[index++] = w1[i++]; 
       } 
       while (j < w2.length) { 
           res[index++] = w2[j++]; 
       } 
       return new String(res); 
   }

No.2 Minimum Number of Operations to Move All Balls to Each Box

解题思路

前缀步数和 + 后缀步数和 确定所有的1移动到当前位置的消耗

• 前缀步数和：每一个的1从左往右移动到当前位置的步数之和
• 后缀步数和：每一个的1从右往左移动到当前位置的步数之和

代码展示

public int[] minOperations(String boxes) { 
       if (boxes == null || boxes.length() == 0) { 
           return null; 
       } 
       char[] boxArray = boxes.toCharArray(); 
       // 前缀步数和 
       int n = boxArray.length; 
       int[] prefixStepSum = new int[n]; 
       int curPreSum = 0; 
       int count1 = 0; 
       for (int i = 0; i < n; i++) { 
           prefixStepSum[i] += curPreSum; 
           if (boxArray[i] == '1') { 
               count1++; 
           } 
           curPreSum += count1; 
       } 

       // 后缀步数和 
       int[] sufStepSum = new int[n]; 
       int curSufSum = 0; 
       int count2 = 0; 
       for (int i = n - 1; i >= 0; i--) { 
           sufStepSum[i] += curSufSum; 
           if (boxArray[i] == '1') { 
               count2++; 
           } 
           curSufSum += count2; 
       } 

       // 计算结果 
       int[] res = new int[n]; 
       for (int i = 0 ; i < n; i++) { 
           res[i] = prefixStepSum[i] + sufStepSum[i]; 
       } 
       return res; 
   }

No.3 Maximum Score from Performing Multiplication Operations

解题思路

区间型动态规划

• dp[i][j]表示剩余数字 i ~ j 时可以获得的最大分数
• 状态转移：
• dp[i][j] = Math.max(mul[n - len] nums[i -1] + dp[i + 1][j], `mul[n - len] nums[j - 1] + dp[i][j - 1]);`
• 通过nums 和mul之间的长度关系可以优化时空复杂度，减少不必要的计算

代码展示

public int maximumScore(int[] nums, int[] mul) { 
       int n = nums.length; 
       int m = mul.length; 
       // 为了防止超时空间复杂度, 去除nums中永远不可能取到的那一部分 
       // m ~ n - m + 1 这一部分 
       if (n > 2 * m) { 
           int i = m; 
           int j = n - m; 
           while (j < n) { 
               nums[i++] = nums[j++]; 
           } 
           n = i; 
       } 
       int[][] dp = new int[2 * m + 1][2 * m + 1]; 
       // 最小区间从 n - m + 1 开始即可, 最后一步至少会剩余 n - m + 1 长度的nums 
       for (int len = n - m + 1; len <= n; len++) { 
           // 枚举左端点 
           for (int i = 1; i <= n - len + 1; i++) { 
               int j = i + len - 1; 
               // 在头尾中选择最大值, nums 区间长度与mul所取元素的对应关系为 
               // len ==> mul[n - len] 
               dp[i][j] = Math.max(mul[n - len] * nums[i -1] + dp[i + 1][j], 
                       mul[n - len] * nums[j - 1] + dp[i][j - 1]); 
           } 
       } 
       return dp[1][n]; 
   } 

No.4 Maximize Palindrome Length From Subsequences

解题思路

简化一下题目描述，相当于从S1 + S2的字符串中，找到一个最长回文子序列

• 区间型动态规划模板题
• 若s[i] == s[j]，dp[i][j] = dp[i + 1][j - 1] + 2;
• 否则，dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
• dp[i][j] 表示 i ~ j 这个区间可以构建的最长回文子序列
• 状态转移：

代码展示

public int longestPalindrome(String word1, String word2) { 
       int len1 = word1.length(); 
       int len2 = word2.length(); 
       int n = len1 + len2; 
       String s = word1 + word2; 
       char[] sArray =  s.toCharArray(); 
       int maxLength = 0; 
       // 字符串 i ~ j 中，最长回文子序列的长度为 dp[i][j] 
       int[][] dp = new int[n][n]; 
       // 区间长度从 1 开始 
       for (int len = 1 ; len <= n; len++) { 
           // 枚举左端点 
           for (int i = 0; i < n - len + 1; i++) { 
               // 计算右端点 
               int j = i + len - 1; 
               if (len == 1) { 
                   dp[i][j] = 1; 
               } 
               else { 
                   if (sArray[i] == sArray[j]){ 
                       dp[i][j] = dp[i + 1][j - 1] + 2; 
                   } else { 
                       // 跳过 s[i] 或者 s[j], 取更大的 
                       dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); 
                   } 
               } 

               // 需要保证两个子序列不为空, 且si == sj时才满足条件 
               if (i < len1 && j >= len1 && sArray[i] == sArray[j]) { 
                   maxLength = Math.max(maxLength, dp[i][j]); 
               } 
           } 
       } 
       return maxLength; 
   }