上岸算法

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

我们直击上岸

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

No.1 盒子中小球的最大数量

★解题思路

计算一个整数的每个数字之和：不断 % 10 取出最后一位并 / 10 抹掉最后一位。

代码展示

class Solution {
   public int countBalls(int lowLimit, int highLimit) {
       int[] count = new int[46];
       for (int i = lowLimit; i <= highLimit; i++) {
           int box = 0;
           for (int j = i; j > 0; j /= 10) {
               box += j % 10;
           }
           count[box]++;
       }
       return Arrays.stream(count).max().getAsInt();
   }
}

No.2 从相邻元素对还原数组

★解题思路

根据相邻的边建图，得到的图一定是链状的，找到相邻节点只有一个节点的点作为起点然后进行遍历即可。

代码展示

class Solution {
   public int[] restoreArray(int[][] adjacentPairs) {
       // 建图
       Map<Integer, List<Integer>> adjacent = new HashMap<>();
       for (var a : adjacentPairs) {
           adjacent.put(a[0], adjacent.getOrDefault(a[0], new ArrayList<>()));
           adjacent.put(a[1], adjacent.getOrDefault(a[1], new ArrayList<>()));
           adjacent.get(a[0]).add(a[1]);
           adjacent.get(a[1]).add(a[0]);
       }
       // 找到起点
       int start = 0;
       for (var a : adjacentPairs) {
           if (adjacent.get(a[0]).size() == 1) {
               start = a[0];
               break;
           }
           if (adjacent.get(a[1]).size() == 1) {
               start = a[1];
               break;
           }
       }
       // 遍历这个链状的图
       Set<Integer> vis = new HashSet<>();
       int[] res = new int[adjacentPairs.length + 1];
       for (int i = 0; i < res.length; i++) {
           res[i] = start;
           vis.add(start);
           for (int j : adjacent.get(start)) {
               if (!vis.contains(j)) {
                   start = j;
                   break;
               }
           }
       }
       return res;
   }
}

No.3 你能在你最喜欢的那天吃到你最喜欢的糖果吗

★解题思路

前缀和 + 二分查找。利用二分查找得出这一天能够吃到的糖果类型的最小值和最大值，判断想吃的类型是否在这个范围内即可。

代码展示

class Solution {
   public boolean[] canEat(int[] candiesCount, int[][] queries) {
       int n = candiesCount.length;
       long sum = 0;
       long[] prefixSum = new long[n];
       for (int i = 0; i < n; i++) {
           sum += candiesCount[i];
           prefixSum[i] = sum;
       }

       boolean[] res = new boolean[queries.length];
       for (int i = 0; i < queries.length; i++) {
           int left = binarySearch(queries[i][1] + 1, prefixSum);
           int right = binarySearch(((long) queries[i][2]) * (queries[i][1] + 1), prefixSum);
           res[i] = queries[i][0] >= left && queries[i][0] <= right;
       }

       return res;
   }

   private int binarySearch(long val, long[] prefixSum) {
       int left = 0, right = prefixSum.length - 1;
       while (left <= right) {
           int mid = (left + right) / 2;
           if (prefixSum[mid] >= val) {
               right = mid - 1;
           } else {
               left = mid + 1;
           }
       }
       return left;
   }
}

No.4 回文串分割 IV

★解题思路

数据范围较小，可以直接 dp + 暴力枚举。

代码展示

class Solution {
   public boolean checkPartitioning(String s) {
       int n = s.length();
       // dp[i][j] 表示 [i, j] 的子串是否回文的
       boolean[][] dp = new boolean[n][n];
       for (int i = n - 1; i >= 0; i--) {
           for (int j = i; j < n; j++) {
               dp[i][j] = i == j || (s.charAt(i) == s.charAt(j) && (i + 1 == j || dp[i + 1][j - 1]));
           }
       }

       // 枚举两个分割点
       for (int i = 0; i < n; i++) {
           if (dp[0][i]) {
               for (int j = i + 1; j < n - 1; j++) {
                   if (dp[i + 1][j] && dp[j + 1][n - 1])
                       return true;
               }
           }
       }
       return false;
   }
}

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

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