No.1 K 进制表示下的各位数字总和

解题思路

进制转换使用取余运算。

代码展示

class Solution { 
   public int sumBase(int n, int k) { 
       int sum = 0; 
       for (int i = n; i > 0; i /= k) { 
           sum += i % k; 
       } 
       return sum; 
   } 
}

No.2 最高频元素的频数

解题思路

首先统计每个数值的出现次数，然后从小到大枚举每个数值，该过程中使用队列储存要变成当前数值的元素即可。

代码展示

class Solution { 
   public int maxFrequency(int[] nums, int k) { 
       final int max = Arrays.stream(nums).max().getAsInt(); 
       int[] cnt = new int[max + 1]; 
       for (int num : nums) { 
           cnt[num]++; 
       } 
       LinkedList<Integer> queue = new LinkedList<>(); 
       int result = 0; 
       int cost = 0; 
       for (int i = 0; i <= max; i++) { 
           cost += queue.size(); 
           while (cost > k && !queue.isEmpty()) { 
               cost -= i - queue.poll(); 
           } 
           if (cost <= k) { 
               result = Math.max(queue.size() + cnt[i], result); 
           } 
           for (int j = 0; j < cnt[i]; j++) { 
               queue.add(i); 
           } 
       } 
       return result; 
   } 
}

No.3所有元音按顺序排布的最长子字符串

解题思路

可以先将相邻重复字符压缩成一个字符，然后就可以查找 "aeiou" 这个字串了。

代码展示

class Solution { 
   public int longestBeautifulSubstring(String word) { 
       StringBuilder sb = new StringBuilder(); 
       List<Integer> count = new ArrayList<>(); 
       int cnt = 1; 
       char c = word.charAt(0); 
       for (int i = 1; i < word.length(); i++) { 
           if (word.charAt(i) == c) { 
               cnt++; 
               continue; 
           } 
           sb.append(c); 
           count.add(cnt); 
           c = word.charAt(i); 
           cnt = 1; 
       } 
       sb.append(c); 
       count.add(cnt); 

       int result = 0; 
       String str = sb.toString(); 
       for (int i = 0; i + 5 <= str.length(); i++) { 
           if ("aeiou".equals(str.substring(i, i + 5))) { 
               int tmp = 0; 
               for (int j = 0; j < 5; j++) { 
                   tmp += count.get(i + j); 
               } 
               result = Math.max(result, tmp); 
           } 
       } 
       return result; 
   } 
} 

No.4 最高建筑高度

解题思路

重新计算 restrictions 然后依次计算两个相邻限高之间的最高建筑即可。

为什么要重新计算？因为输入的 restrictions 中的限高并不能都达到。比方有 [2, 1] 和 [3, 5]，因为限制建筑 2 最高为 1, 那么建筑 3 最高只能是 2, 而给定的 [3, 5] 是不可能达到的。换句话说，由于相邻建筑高度差不超过 1 的限制存在，相邻的限高条件之间也会相互影响。所以我们需要重新计算 restrictions，输入 [[2, 1], [3, 5]] 重新计算后应得到 [[2, 1], [3, 2]]。

重新计算的过程与 Dijkstra 求单源最短路堆优化版本有点类似。重新计算之后可能有一些建筑的限高会变低，但是不可能会变高。我们从最低的限高开始计算即可，每一个限高可能会降低它相邻的两个限高的高度。再举个例子：[[5, 5], [8, 1], [10, 10]] 中，建筑 5 和 10 的限高就会被建筑 8 的限高所降低，最终得到 [[5, 4], [8, 1], [10, 3]]。

代码展示

class Solution { 
   public int maxBuilding(int n, int[][] restrictions) { 
       // 复制 restrictions, 得到 R 
       // 并添加两个边界点：[1, 0] 和 [n, n - 1] 
       // 即有 R.length == restrictions.length + 2 
       int[][] R = new int[restrictions.length + 2][2]; 
       R[0] = new int[]{1, 0}; 
       R[restrictions.length + 1] = new int[]{n, n - 1}; 
       Arrays.sort(restrictions, Comparator.comparingInt(a -> a[0])); // 按照建筑编号排序 
       System.arraycopy(restrictions, 0, R, 1, restrictions.length); 

       // 重新计算 R[i][1] 
       PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); 
       for (int i = 0; i < R.length; i++) { 
           heap.add(new int[]{i, R[i][1]}); 
       } 
       boolean[] done = new boolean[R.length]; 
       while (!heap.isEmpty()) { 
           int id = heap.poll()[0]; 
           if (done[id]) { 
               continue; 
           } 
           done[id] = true; 
           for (int i = -1; i <= 1; i += 2) { 
               int nei = id + i; // neighbor 
               if (nei < 0 || nei >= R.length) { 
                   continue; 
               } 
               int maxHeight = R[id][1] + Math.abs(R[id][0] - R[nei][0]); 
               if (R[nei][1] > maxHeight) { 
                   R[nei][1] = maxHeight; 
                   heap.add(new int[]{nei, maxHeight}); 
               } 
           } 
       } 

       // 根据每两个相邻的建筑高度限制，计算这两个建筑之间（包括自身）的最高建筑 
       int result = 0; 
       for (int i = 1; i < R.length; i++) { 
           result = Math.max(result, calc(R[i], R[i - 1])); 
       } 
       return result; 
   } 

   private int calc(int[] a, int[] b) { 
       return Math.max(a[1], b[1]) + (Math.abs(b[0] - a[0]) - Math.abs(b[1] - a[1])) / 2; 
   } 
}