上岸算法

死磕100%上岸率的精品小班课

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

No.1 设计有序流

★

解题思路

按照题意编码即可.

代码展示

class OrderedStream {

   private final String[] strings;
   private int ptr;

   public OrderedStream(int n) {
       strings = new String[n];
       ptr = 0;
   }

   public List<String> insert(int id, String value) {
       id--;  // 数组下标从 0 开始
       strings[id] = value;
       List<String> res = new ArrayList<>();
       for (; ptr < strings.length && strings[ptr] != null; ptr++) {
           res.add(strings[ptr]);
       }
       return res;
   }
}

No.2 确定两个字符串是否接近

★解题思路

解读、分析得到两个字符串接近的条件:

字符集相同

每种字符出现的次数构成的序列相同

代码展示

class Solution {
   public boolean closeStrings(String word1, String word2) {
       int[] cnt1 = new int[26];
       for (int i = 0; i < word1.length(); i++) {
           cnt1[word1.charAt(i) - 'a']++;
       }
       int[] cnt2 = new int[26];
       for (int i = 0; i < word2.length(); i++) {
           cnt2[word2.charAt(i) - 'a']++;
       }
       // 字符集相同
       for (int i = 0; i < 26; i++) {
           // 字符 i 若在 word1 中出现, 那么在 word2 中也必须出现
           if (cnt1[i] + cnt2[i] != 0 && cnt1[i] * cnt2[i] == 0) {
               return false;
           }
       }
       // 次数序列相同
       Arrays.sort(cnt1);
       Arrays.sort(cnt2);
       for (int i = 0; i < 26; i++) {
           if (cnt1[i] != cnt2[i]) {
               return false;
           }
       }
       return true;
   }
}

No.3 将x减到0的最小操作数

★解题思路

两根指针, 详见注释.

代码展示

class Solution {
   public int minOperations(int[] nums, int x) {
       // 预处理出前缀和与后缀和, 方便后续计算
       int[] prefixSum = new int[nums.length];
       int[] suffixSum = new int[nums.length];
       prefixSum[0] = nums[0];
       for (int i = 1; i < nums.length; i++) {
           prefixSum[i] = prefixSum[i - 1] + nums[i];
       }
       suffixSum[nums.length - 1] = nums[nums.length - 1];
       for (int i = nums.length - 2; i >= 0; i--) {
           suffixSum[i] = suffixSum[i + 1] + nums[i];
       }

       // 两根指针 left 和 right
       int res = nums.length + 1;
       int left = 0, right = 0;
       // [0, left) + [right, nums.length)
       for (; left < nums.length; left++) {
           while (right < nums.length && calcSum(left, right, prefixSum, suffixSum) > x) {
               right++;
           }
           if (calcSum(left, right, prefixSum, suffixSum) == x) {
               int len = left + nums.length - right;
               res = Math.min(res, len);
           }
       }
       return res > nums.length ? -1 : res;
   }

   private int calcSum(int left, int right, int[] prefixSum, int[] suffixSum) {
       // [0, left) + [right, nums.length)
       return (left > 0 ? prefixSum[left - 1] : 0) +
               (right < suffixSum.length ? suffixSum[right] : 0);
   }
}

No.4 最大化网格幸福感

★ 解题思路

深度优先搜索 (回溯).

本质上就是枚举每一个格子是分配外向的人, 还是内向的人, 还是不分配.

下述代码展示思路, 可以计算出正确答案, 但是会超出时间限制.

进一步优化可以将 grid 进行压缩并且记忆化, 方可通过.

代码展示

class Solution {
   private int res;

   public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
       res = 0;
       dfs(0, 0, m, n, new byte[m][n], introvertsCount, extrovertsCount);
       return res;
   }

   private void dfs(int x, int y, int m, int n, byte[][] grid, int introvertsCount, int extrovertsCount) {
       if (y == n) {
           x++;
           y = 0;
       }
       if (x == m || introvertsCount + extrovertsCount == 0) {
           res = Math.max(calc(grid), res);
           return;
       }
       // 优化点: 就算剩下的人都取最大幸福值也不如当前答案优秀, 停止搜索.
       if (introvertsCount * 120 + extrovertsCount * 120 + calc(grid) <= res) {
           return;
       }
       if (extrovertsCount > 0) {
           grid[x][y] = 2;
           dfs(x, y + 1, m, n, grid, introvertsCount, extrovertsCount - 1);
           grid[x][y] = 0;
       }
       if (introvertsCount > 0) {
           grid[x][y] = 1;
           dfs(x, y + 1, m, n, grid, introvertsCount - 1, extrovertsCount);
           grid[x][y] = 0;
       }
       dfs(x, y + 1, m, n, grid, introvertsCount, extrovertsCount);
   }

   private int calc(byte[][] grid) {
       int[] dx = {1, -1, 0, 0};
       int[] dy = {0, 0, 1, -1};
       int res = 0;
       for (int i = 0; i < grid.length; i++) {
           for (int j = 0; j < grid[0].length; j++) {
               if (grid[i][j] == 0) {
                   continue;
               }
               res += grid[i][j] == 1 ? 120 : 40;
               int inc = grid[i][j] == 1 ? -30 : 20;
               for (int k = 0; k < 4; k++) {
                   int x = i + dx[k];
                   int y = j + dy[k];
                   if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {
                       continue;
                   }
                   if (grid[x][y] > 0) {
                       res += inc;
                   }
               }
           }
       }
       return res;
   }
}

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

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