上岸算法

任何只教知识的课程都是耍流氓

我们直击上岸

关注我们，第一时间获得大厂面试真题讲解

No.1 替换隐藏数字得到的最晚时间

★解题思路

从左到右依次处理每个位置的 ? 即可 —— 替换为可能的最大值。

代码展示

class Solution {
   public String maximumTime(String time) {
       char[] chars = time.toCharArray();
       if (chars[0] == '?') {
           chars[0] = chars[1] != '?' && chars[1] > '3' ? '1' : '2';
       }
       if (chars[1] == '?') {
           chars[1] = chars[0] == '2' ? '3' : '9';
       }
       if (chars[3] == '?') {
           chars[3] = '5';
       }
       if (chars[4] == '?') {
           chars[4] = '9';
       }
       return new String(chars);
   }
}

No.2 满足三条件之一需改变的最少字符数

★解题思路

3 种条件、26 个分界点，枚举这 3 x 26 种情况即可。

代码展示

class Solution {
   public int minCharacters(String a, String b) {
       int[] cntA = count(a); // cntA[c - 'a'] 表示 a 中 c 出现的次数
       int[] cntB = count(b);
       int res = Integer.MAX_VALUE;

       for (char c = 'a'; c <= 'z'; c++) {
           // a, b 都为字符 c
           res = Math.min(res, a.length() + b.length() - cntA[c - 'a'] - cntB[c - 'a']);
           if (cntB[25] == 0) {
               // a > b 且 b 中所有字符不大于 c
               res = Math.min(res, calc(cntA, cntB, c));
           }
           if (cntA[25] == 0) { 
               // a < b 且 a 中所有字符不大于 c
               res = Math.min(res, calc(cntB, cntA, c));
           }
       }

       return res;
   }

   private int calc(int[] cntA, int[] cntB, char c) {
       int res = 0;
       for (char c2 = 'a'; c2 <= c; c2++) {
           res += cntA[c2 - 'a'];
       }
       for (char c2 = (char) (c + 1); c2 <= 'z'; c2++) {
           res += cntB[c2 - 'a'];
       }
       return res;
   }

   private int[] count(String s) {
       int[] cnt = new int[26];
       for (char c : s.toCharArray()) {
           cnt[c - 'a']++;
       }
       return cnt;
   }
}

No.3 找出第K大的异或坐标值

★解题思路

前缀和。计算出每个坐标的异或值，然后取第 K 大即可。

代码展示

class Solution {
   public int kthLargestValue(int[][] matrix, int k) {
       int n = matrix.length;
       int m = matrix[0].length;
       int[][] rowPrefix = new int[n][m]; // 每一行的前缀异或和
       for (int i = 0; i < n; i++) {
           rowPrefix[i][0] = matrix[i][0];
           for (int j = 1; j < m; j++) {
               rowPrefix[i][j] = rowPrefix[i][j - 1] ^ matrix[i][j];
           }
       }

       List<Integer> list = new ArrayList<>();
       // 利用 rowPrefix 计算出每个坐标的值
       for (int j = 0; j < m; j++) {
           int xor = rowPrefix[0][j];
           list.add(xor);
           for (int i = 1; i < n; i++) {
               xor ^= rowPrefix[i][j];
               list.add(xor);
           }
       }
       Collections.sort(list);
       return list.get(list.size() - k);
   }
}

No.4放置盒子

★解题思路

最优策略就是尽可能利用墙角，然后堆得尽可能高。按照如下顺序放置方块即可：

放 1 个 (0, 0, 0) 高 1，底 1，总 1 (样例一)

放 1 个 (1, 0, 0) 底 2，总 2

放 2 个 (0, 1, 0) (0, 0, 1) 高 2，底 3，总 4 (样例二)

放 1 个 (2, 0, 0) 底 4，总 5

放 2 个 (2, 1, 0) (2, 0, 1) 底 5，总 7

放 3 个 (2, 2, 0) (2, 1, 1) (2, 0, 0) 底 6，总 10 (样例三)

...

从 0 开始，底部每增加一个，放置的方块总数就会增加 1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5 ... 个。

代码展示

class Solution {
   public int minimumBoxes(int n) {
       int sum = 1;
       int level = 1;
       int bottom = 1;
       while (sum < n) {
           for (int i = 0; i <= level && sum < n; i++) {
               bottom++;
               sum += i + 1;
           }
           level += 1;
       }
       return bottom;
   }
}

    杭州上岸算法网络科技有限公司

上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。