上岸算法

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

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

No.1 重新排列单词间的空格

★解题思路

详解可以看下方代码注释。

代码展示

class Solution { 
   public String reorderSpaces(String text) { 
       // 提取单词列表 
       String[] words = text.trim().split(" +"); 
       // 计数空格数量 
       int count = 0; 
       for (int i = 0; i < text.length(); i++) { 
           count += text.charAt(i) == ' ' ? 1 : 0; 
       } 
       // 特殊情况判断 
       if (words.length == 1) { 
           StringBuilder tail = new StringBuilder(); 
           for (int i = 0; i < count; i++) 
               tail.append(" "); 
           return words[0] + tail.toString(); 
       } 
       // 计算平均空格数量 
       int avg = count / (words.length - 1); 
       int mod = count % (words.length - 1); 
       StringBuilder sep = new StringBuilder(); 
       for (int i = 0; i < avg; i++) 
           sep.append(" "); 
       // 组装结果 
       StringBuilder res = new StringBuilder(words[0]); 
       for (int i = 1; i < words.length; i++) { 
           res.append(sep); 
           res.append(words[i]); 
       } 
       if (mod > 0) { 
           for (int i = 0; i < mod; i++) 
               res.append(" "); 

       } 
       return res.toString(); 
   } 
}

No.2 拆分字符串使唯一子字符串的数目最大

★解题思路

回溯法, 枚举所有的拆分情况即可, 使用 set 判断是否有重复字符串出现.

代码展示

class Solution { 
   public int maxUniqueSplit(String s) { 
       return maxUniqueSplit(s, 0, new HashSet<String>()); 
   } 
   private int maxUniqueSplit(String s, int start, HashSet<String> set) { 
       if (start == s.length()) { 
           return set.size(); 
       } 
       int res = 1; 
       for (int end = start + 1; end <= s.length(); end++) { 
           String sub = s.substring(start, end); 
           if (!set.contains(sub)) { 
               set.add(sub); 
               res = Math.max(res, maxUniqueSplit(s, end, set)); 
               set.remove(sub); 
           } 
       } 
       return res; 
   } 
}

No.3 矩阵的最大非负积

★解题思路

详细思路建代码

代码展示

class Solution { 
   public int maxProductPath(int[][] grid) { 
       int n = grid.length; 
       int m = grid[0].length; 
       // max[i][j] 表示走到 [i, j] 的最大非负乘积 
       // min[i][j] 表示走到 [i, j] 的最小非正乘积 
       long[][] max = new long[n][m]; 
       long[][] min = new long[n][m]; 
       for (int i = 0; i < n; i++) { 
           // MIN_VAULE, MAX_VALUE 表示非法状态 
           Arrays.fill(max[i], Long.MIN_VALUE); 
           Arrays.fill(min[i], Long.MAX_VALUE); 
       } 
       if (grid[0][0] > 0) 
           max[0][0] = grid[0][0]; 
       if (grid[0][0] < 0) 
           min[0][0] = grid[0][0]; 
       if (grid[0][0] == 0) 
           max[0][0] = min[0][0] = 0; 
       // 根据 grid[i][j] 的正负进行状态转移 
       for (int i = 0; i < n; i++) { 
           for (int j = 0; j < m; j++) { 
               if (i == 0 && j == 0) 
                   continue; 
               if (grid[i][j] > 0) { 
                   long uMax = (i == 0 || max[i - 1][j] == Long.MIN_VALUE) ?  
                           Long.MIN_VALUE : (grid[i][j] * max[i - 1][j]); 
                   long lMax = (j == 0 || max[i][j - 1] == Long.MIN_VALUE) ?  
                           Long.MIN_VALUE : (grid[i][j] * max[i][j - 1]); 
                   max[i][j] = Math.max(uMax, lMax); 
                   long uMin = (i == 0 || min[i - 1][j] == Long.MAX_VALUE) ?  
                           Long.MAX_VALUE : (grid[i][j] * min[i - 1][j]); 
                   long lMin = (j == 0 || min[i][j - 1] == Long.MAX_VALUE) ?  
                           Long.MAX_VALUE : (grid[i][j] * min[i][j - 1]); 
                   min[i][j] = Math.min(uMin, lMin); 
               } 
               if (grid[i][j] < 0) { 
                   long uMax = (i == 0 || min[i - 1][j] == Long.MAX_VALUE) ?  
                           Long.MIN_VALUE : (grid[i][j] * min[i - 1][j]); 
                   long lMax = (j == 0 || min[i][j - 1] == Long.MAX_VALUE) ?  
                           Long.MIN_VALUE : (grid[i][j] * min[i][j - 1]); 
                   max[i][j] = Math.max(uMax, lMax); 
                   long uMin = (i == 0 || max[i - 1][j] == Long.MIN_VALUE) ?  
                           Long.MAX_VALUE : (grid[i][j] * max[i - 1][j]); 
                   long lMin = (j == 0 || max[i][j - 1] == Long.MIN_VALUE) ?  
                           Long.MAX_VALUE : (grid[i][j] * max[i][j - 1]); 
                   min[i][j] = Math.min(uMin, lMin); 
               } 
               if (grid[i][j] == 0) 
                   max[i][j] = min[i][j] = 0; 
           } 
       } 
       if (max[n - 1][m - 1] < 0) 
           return -1; 
       return (int) (max[n - 1][m - 1] % 1000000007L); 
   } 
}

No.4

连通两组点的最小成本

★

解题思路

状态压缩动态规划.详情见注释

代码展示

class Solution { 
   public int connectTwoGroups(List<List<Integer>> cost) { 
       int n = cost.size(), m = cost.get(0).size(); 
       // f[i][j] 表示第一组中的前 i 个点与第二组中的 j 点连接的最小花费 
       // 其中 j 表示一个点集 
       int maxJ = (1 << m) - 1; 
       int[][] f = new int[n + 1][maxJ + 1]; 
       for (int i = 0; i <= n; i++) { 
           Arrays.fill(f[i], 0x3f3f3f3f); 
       } 
       f[0][0] = 0; 
       for (int i = 1; i <= n; ++i) { 
           // 预处理信息 
           int[] sum = new int[maxJ + 1]; 
           for (int j = 0; j <= maxJ; ++j) { 
               sum[j] = 0; 
               for (int u = 1, v = 1; u <= m; u++, v <<= 1) { 
                   if ((v & j) > 0) 
                       sum[j] += cost.get(i - 1).get(u - 1); 
               } 
           } 
           // 状态转移, u 表示集合 2 的点编号, v 表示它在集合 j 中的位置 
           // 即枚举集合 2 中的点, 与 i 配对, 选出最优解 
           for (int j = 0; j <= maxJ; ++j) { 
               for (int u = 1, v = 1; u <= m; u++, v <<= 1) { 
                   if ((v & j) > 0) 
                       f[i][j] = Math.min(f[i][j], f[i - 1][j] + cost.get(i - 1).get(u - 1)); 
               } 
               int j2 = (maxJ ^ j); 
               for (int u = j2; u > 0; u = (u - 1) & j2) { 
                   f[i][j | u] = Math.min(f[i][j | u], f[i - 1][j] + sum[u]); 
               } 
           } 
       } 
       return f[n][maxJ]; 
   } 
}

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

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