上岸算法

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

我们直击上岸

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

No.1判断字符串的两半是否相似

★解题思路

统计元音字母数量即可。

代码展示

class Solution {
   public boolean halvesAreAlike(String s) {
       int n = s.length();
       int a = 0, b = 0;
       for (int i = 0, j = n - 1; i < j; i++, j--) {
           a += "AEIOUaeiou".indexOf(s.charAt(i)) >= 0 ? 1 : 0;
           b += "AEIOUaeiou".indexOf(s.charAt(j)) >= 0 ? 1 : 0;
       }
       return a == b;
   }
}

No.2 吃苹果的最大数目

★解题思路

贪心的思路，我们总是吃掉剩下的苹果中最先烂掉的。使用优先队列可以维护剩下的苹果哪些先烂掉。

代码展示

class Solution {
   static class Apple {
       int num;
       int day;

       public Apple(int num, int day) {
           this.num = num;
           this.day = day;
       }
   }

   public int eatenApples(int[] apples, int[] days) {
       PriorityQueue<Apple> bucket = new PriorityQueue<>(Comparator.comparingInt(a -> a.day));
       int res = 0;
       for (int i = 0; i < apples.length; i++) {
           if (apples[i] > 0) {
               bucket.add(new Apple(apples[i], i + days[i]));
           }
           res += eat(bucket, i);
       }
       // 不再增加苹果，将剩下的吃完
       for (int i = apples.length; !bucket.isEmpty(); i++) {
           res += eat(bucket, i);
       }
       return res;
   }

   // 在第 day 天吃苹果，返回能吃到的数量 (0 或 1)
   private int eat(PriorityQueue<Apple> bucket, int day) {
       while (!bucket.isEmpty()) {
           Apple a = bucket.poll();
           if (a.day <= day) {
               continue;
           }
           if ((--a.num) > 0) {
               bucket.add(a);
           }
           return 1;
       }
       return 0;
   }
}

No.3 球会落何处

★解题思路

模拟球的下落即可。

代码展示

class Solution {
   public int[] findBall(int[][] grid) {
       int m = grid[0].length;
       int[] res = new int[m];
       for (int i = 0; i < m; i++) {
           res[i] = drop(0, i, grid);
       }
       return res;
   }

   private int drop(int x, int y, int[][] grid) {
       if (x == grid.length) {
           return y;
       }
       if (grid[x][y] == 1 && (y == grid[0].length - 1 || grid[x][y + 1] == -1)) {
           return -1;
       }
       if (grid[x][y] == -1 && (y == 0 || grid[x][y - 1] == 1)) {
           return -1;
       }
       return drop(x + 1, y + grid[x][y], grid);
   }
}

No.4 与数组中元素的最大异或值

★解题思路

字典树。

我们知道，二进制数的异或运算的含义就是两者是否不同 —— 所以我们在 Trie 树上尽可能走与当前位不同的那一条路径即可。

代码展示

class Solution {
   class TrieNode {
       int min; // 当前节点下最小的数
       TrieNode[] child;

       public TrieNode() {
           min = Integer.MAX_VALUE;
           child = new TrieNode[2];
       }
   }

   public int[] maximizeXor(int[] nums, int[][] queries) {
       int min = Arrays.stream(nums).min().getAsInt();

       // 初始化，建立一棵 32 层的 Trie 树
       TrieNode root = new TrieNode();
       for (int num : nums) {
           TrieNode cur = root;
           for (int m = 30; m >= 0; m--) {
               cur.min = Math.min(cur.min, num);
               int d = (num >> m) & 1;
               if (cur.child[d] == null) {
                   cur.child[d] = new TrieNode();
               }
               cur = cur.child[d];
               cur.min = Math.min(cur.min, num);
           }
       }

       // 求解
       int[] res = new int[queries.length];
       for (int i = 0; i < queries.length; i++) {
           if (queries[i][1] < min) {
               res[i] = -1;
               continue;
           }
           TrieNode cur = root;
           for (int m = 30; m >= 0 && cur != null; m--) {
               int xd = (queries[i][0] >> m) & 1; // 希望往 xd ^ 1 的方向走
               TrieNode except = cur.child[xd ^ 1];
               if (except == null || except.min > queries[i][1]) {
                   cur = cur.child[xd];
               } else {
                   cur = except;
               }
           }
           res[i] = cur == null || cur.min > queries[i][1] ? -1 : cur.min ^ queries[i][0];
       }
       return res;
   }
}

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

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