No.1 检查数组是否经排序和轮转得到

解题思路

枚举、检查。

代码展示

class Solution { 
   public boolean check(int[] nums) { 
       for (int i = 0; i < nums.length; i++) { 
           if (check(nums, i)) { 
               return true; 
           } 
       } 
       return false; 
   } 

   private boolean check(int[] nums, int i) { 
       for (int j = 1; j < nums.length; j++) { 
           if (nums[(i + j - 1 + nums.length) % nums.length] > nums[(i + j) % nums.length]) { 
               return false; 
           } 
       } 
       return true; 
   } 
}

No.2 移除石子的最大得分

解题思路

贪心，每次移除最多的和最少的。

代码展示

class Solution { 
   public int maximumScore(int a, int b, int c) { 
       int res = 0; 
       int[] nums = {a, b, c}; 
       Arrays.sort(nums); 
       for (; nums[1] != 0; res++) { 
           if (nums[0] == 0) { 
               nums[1]--; 
           } else { 
               nums[0]--; 
           } 
           nums[2]--; 
           Arrays.sort(nums); 
       } 
       return res; 
   } 
}

No.3 构造字典序最大的合并字符串

解题思路

贪心，详见注释。

代码展示

class Solution { 
   public String largestMerge(String word1, String word2) { 
       StringBuilder sb = new StringBuilder(); 
       for (int i = 0, j = 0; i < word1.length() || j < word2.length(); ) { 
           // word1[i] != word2[j] 时, 选择大的字符 
           if (i == word1.length()) { 
               sb.append(word2.charAt(j++)); 
           } else if (j == word2.length()) { 
               sb.append(word1.charAt(i++)); 
           } else if (word1.charAt(i) > word2.charAt(j)) { 
               sb.append(word1.charAt(i++)); 
           } else if (word1.charAt(i) < word2.charAt(j)) { 
               sb.append(word2.charAt(j++)); 
           } else { 
               // word1[i] == word2[j] 时 
               // 找到第一个不相等的 word1[i + t] != word2[j + t] 
               // 选择大的字符所在的字符串 
               Character c1 = null, c2 = null; 
               for (int t = 1; i + t < word1.length() && j + t < word2.length(); t++) { 
                   if (word1.charAt(i + t) != word2.charAt(j + t)) { 
                       c1 = word1.charAt(i + t); 
                       c2 = word2.charAt(j + t); 
                       break; 
                   } 
               } 
               // 若后续全都相等，选择长的 
               if (c1 == null && word1.length() - i > word2.length() - j) { 
                   sb.append(word1.charAt(i++)); 
               } else if (c1 == null && word1.length() - i < word2.length() - j) { 
                   sb.append(word2.charAt(j++)); 
               } else if (c1 != null && c1 > c2) { 
                   sb.append(word1.charAt(i++)); 
               } else { 
                   sb.append(word2.charAt(j++)); 
               } 
           } 
       } 
       return sb.toString(); 
   } 
}

No.4 最接近目标值的子序列和

解题思路

超大背包问题。

代码展示

class Solution { 
   public int minAbsDifference(int[] nums, int goal) { 
       int n = nums.length; 
       int half = n / 2; 
       int[] a = new int[1 << half]; 
       for (int i = 0; i < (1 << half); i++) { 
           int sum = 0; 
           for (int j = 0; j < half; j++) { 
               if (((i >> j) & 1) > 0) { 
                   sum += nums[j]; 
               } 
           } 
           a[i] = sum; 
       } 
       int half2 = n - half; 
       int[] b = new int[1 << half2]; 
       for (int i = 0; i < (1 << half2); i++) { 
           int sum = 0; 
           for (int j = 0; j < half2; j++) { 
               if (((i >> j) & 1) > 0) { 
                   sum += nums[half + j]; 
               } 
           } 
           b[i] = sum; 
       } 
       Arrays.sort(b); 
       int ans = Integer.MAX_VALUE; 
       for (int v : a) { 
           int pos = binarySearch(b, goal - v); 
           for (int j = Math.max(0, pos - 2); j < Math.min(b.length, pos + 2); j++) { 
               ans = Math.min(ans, Math.abs((v + b[j]) - goal)); 
           } 
       } 
       return ans; 
   } 

   public static int binarySearch(int[] nums, int key) { 
       int start = 0, end = nums.length - 1; 
       while (start + 1 < end) { 
           int mid = (start + end) / 2; 
           if (nums[mid] < key) { 
               start = mid; 
           } else { 
               end = mid; 
           } 
       } 
       return nums[start] < key ? end : start; 
   } 
}