上岸算法

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

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

No.1 重复至少 K 次且长度为 M 的模式

★解题思路

枚举所有可能的模式, 然后统计每种模式重复了多少次即可.

代码展示

class Solution {
   public boolean containsPattern(int[] arr, int m, int k) {
       for (int i = 0; i + m <= arr.length; i++) {
           int[] pattern = Arrays.copyOfRange(arr, i, i + m);
           if (count(arr, pattern) >= k) {
               return true;
           }
       }
       return false;
   }
   private int count(int[] arr, int[] pattern) {
       int res = 0;
       int n = pattern.length;
       int cnt = 0;
       for (int i = 0; i + n <= arr.length; ) {
           if (Arrays.equals(arr, i, i + n, pattern, 0, n)) {
               cnt++;
               i += n;
           } else {
               cnt = 0; // 不再连续, 置零
               i++;
           }
           res = Math.max(res, cnt);
       }
       return res;
   }
}

No.2 乘积为正数的最长子数组长度

★解题思路

递推, 见代码注释.

代码展示

class Solution {
   public int getMaxLen(int[] nums) {
       int n = nums.length;
       int res = 0;
       // F[i] 表示以第 i 个数字结尾, 最长连续乘积为正数的子数组长度
       // G[i] 表示以第 i 个数字结尾, 最长连续乘积为负数的子数组长度 
       int[] F = new int[n + 1];
       int[] G = new int[n + 1];
       for (int i = 1; i <= n; i++) {
           if (nums[i - 1] == 0) {
               F[i] = G[i] = 0;
           } else if (nums[i - 1] > 0) {
               // 当前数字大于 0
               // F[i] 从 F[i-1] 计算, 若 F[i-1]=0, 当前数字单独成子数组
               // G[i] 从 G[i-1] 计算, 若 G[i-1]=0, 无乘积为负数的子数组
               F[i] = F[i - 1] > 0 ? F[i - 1] + 1 : 1;
               G[i] = G[i - 1] > 0 ? G[i - 1] + 1 : 0;
           } else {
               // 当前数字小于 0, F[i] 从 G[i-1] 计算, G[i] 从 F[i-1] 计算
               G[i] = F[i - 1] > 0 ? F[i - 1] + 1 : 1;
               F[i] = G[i - 1] > 0 ? G[i - 1] + 1 : 0;
           }
           res = Math.max(res, F[i]);
       }
       return res;
   }
}

No.3 使陆地分离的最少天数

★解题思路

该题目看似一个网络流问题, 但是其实很简单.

由于是网格图, 所以我们最多操作两次就可以将陆地分割.

代码展示

class Solution {
   public static int[] dx = {0, 0, 1, -1};
   public static int[] dy = {1, -1, 0, 0};
   private int n, m;

   public int minDays(int[][] grid) {
       n = grid.length;
       m = grid[0].length;
       if (check(grid)) return 0;
       // 判断是否有操作 1 次的方案
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++) {
               if (grid[i][j] == 1) {
                   grid[i][j] = 0;
                   if (check(grid)) return 1;
                   grid[i][j] = 1;
               }
           }
       }
       return 2;
   }

   // check 检查 grid 是否已经被分割
   public boolean check(int[][] grid) {
       int nums1 = 0; // 统计 grid 中 1 的数量
       int landSize = -1; // 碰到的第一块陆地的大小
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++) {
               nums1 += grid[i][j];
               if (grid[i][j] == 1 && landSize < 0) {
                   landSize = dfs(grid, i, j, new boolean[n][m]);
               }
           }
       }
       return landSize < nums1;
   }

   // 统计陆地大小
   private int dfs(int[][] grid, int x, int y, boolean[][] vis) {
       int res = 1;
       vis[x][y] = true;
       for (int i = 0; i < 4; i++) {
           int nx = x + dx[i];
           int ny = y + dy[i];
           if (nx < 0 || ny < 0 || nx >= n || ny >= m || vis[nx][ny] || grid[nx][ny] == 0) continue;
           res += dfs(grid, nx, ny, vis);
       }
       return res;
   }
}

No.4

将子数组重新排序得到同一个二叉查找树的方案数

★

解题思路

一个数后面第一个大于它的和第一个小于它的数值不能改变, 并且一个数后面所有大于它的数和所有小于它的数互不影响.

我们建立 BST, 通过树的结构分析出一共有多少种可能的序列, 然后 -1 返回.

假设 node 有左子节点 left 和右子节点 right, 那么这棵树的方案数就是左子树的方案数  右子树的方案数  合并二者的方案数.

合并二者的方案数对应前面提到的一个数后面所有大于它的数和所有小于它的数互不影响. 代码中使用 helper 数组统计这一点.

代码展示

class Node {
   int val, count;
   Node left, right;
   Node(int x) {
       val = x;
       count = 1;
   }
}

class Solution {
   private static long MOD = 1000000007;
   private long[][] helper;

   public int numOfWays(int[] nums) {
       // 建树, 并统计每个节点下的子树大小
       Node root = new Node(nums[0]);
       for (int i = 1; i < nums.length; i++) {
           Node node = root;
           Node newNode = new Node(nums[i]);
           while (true) {
               node.count++;
               if (node.val < nums[i]) {
                   if (node.right == null) {
                       node.right = newNode;
                       break;
                   }
                   node = node.right;
               } else {
                   if (node.left == null) {
                       node.left = newNode;
                       break;
                   }
                   node = node.left;
               }
           }
       }

       // 推导 helper 数组
       helper = new long[nums.length + 1][nums.length + 1];
       helper[0][0] = 1;
       for (int i = 1; i <= nums.length; i++) {
           helper[i][0] = 1;
           for (int j = 1; j <= nums.length; j++) {
               helper[i][j] = (helper[i - 1][j - 1] + helper[i - 1][j]) % MOD;
           }
       }

       return (int) ((dfs(root) + MOD - 1) % MOD);
   }

   private long dfs(Node node) {
       Node l = node.left, r = node.right;
       if (l == null && r == null) return 1;
       if (l == null) return dfs(r);
       if (r == null) return dfs(l);
       long lRes = dfs(l), rRes = dfs(r);
       // 两子树的方案数相乘, 再乘以 helper
       return (helper[node.count - 1][l.count] * lRes % MOD) * rRes % MOD;
   }
}

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

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