上岸算法

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

我们直击上岸

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

No.1

检查二进制字符串字段

解题思路

符合要求的字符串即前缀全是 1，后缀全是 0 的字符串。

代码展示

class Solution { 
   public boolean checkOnesSegment(String s) { 
       if (!s.contains("0")) { 
           return true; 
       } 
       if (s.substring(s.indexOf("0")).contains("1")) { 
           return false; 
       } 
       return true; 
   } 
}

No.2构成特定和需要添加的最少元素

解题思路

贪心即可，每次都添加绝对值尽可能大的。注意总和可能溢出 int，所以中间运算要使用 long。

代码展示

class Solution { 
   public int minElements(int[] nums, int limit, int goal) { 
       long sum = 0; 
       for (int num : nums) { 
           sum += num; 
       } 
       sum = Math.abs(goal - sum); 
       int count = (int) (sum / limit); 
       if (sum % limit != 0) { 
           count++; 
       } 
       return count; 
   } 
}

No.3从第一个节点出发到最后一个节点的受限路径数

解题思路

Dijkstra + DP

代码展示

class Solution { 
   static class Edge { 
       int next; 
       int len; 

       Edge(int next, int len) { 
           this.next = next; 
           this.len = len; 
       } 
   } 

   public int countRestrictedPaths(int n, int[][] edges) { 
       // 建图 
       Map<Integer, List<Edge>> graph = new HashMap<>(); 
       for (int[] edge : edges) { 
           for (int i = 0; i < 2; i++) { 
               if (!graph.containsKey(edge[i])) { 
                   graph.put(edge[i], new ArrayList<>()); 
               } 
               graph.get(edge[i]).add(new Edge(edge[1 - i], edge[2])); 
           } 
       } 
               // dijkstra 求出 distanceToLastNode 
       var distanceToLastNode = dijkstra(n, graph); 
       // DP 
       int[] mem = new int[n + 1]; 
       Arrays.fill(mem, -1); 
       mem[n] = 1; 
       return dp(1, mem, distanceToLastNode, graph); 
   } 

   private int dp(int cur, int[] mem, Map<Integer, Integer> distanceToLastNode, Map<Integer, List<Edge>> graph) { 
       if (mem[cur] >= 0) { 
           return mem[cur]; 
       } 
       mem[cur] = 0; 
       for (var next : graph.get(cur)) { 
           if (distanceToLastNode.get(cur) > distanceToLastNode.get(next.next)) { 
               mem[cur] = (mem[cur] + dp(next.next, mem, distanceToLastNode, graph)) % 1000000007; 
           } 
       } 
       return mem[cur]; 
   } 

   static class Node { 
       int to; 
       int len; 

       Node(int to, int len) { 
           this.to = to; 
           this.len = len; 
       } 
   } 

   private Map<Integer, Integer> dijkstra(int start, Map<Integer, List<Edge>> graph) { 
       Set<Integer> visited = new HashSet<>(); 
       Map<Integer, Integer> res = new HashMap<>(); 
       PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (o1.len - o2.len)); 
       res.put(start, 0); 
       heap.add(new Node(start, 0)); 
       while (!heap.isEmpty()) { 
           Node node = heap.poll(); 
           if (visited.contains(node.to)) { 
               continue; 
           } 
           visited.add(node.to); 
           for (Edge e : graph.get(node.to)) { 
               if (res.getOrDefault(e.next, Integer.MAX_VALUE) > node.len + e.len) { 
                   res.put(e.next, node.len + e.len); 
                   heap.add(new Node(e.next, node.len + e.len)); 
               } 
           } 
       } 
       return res; 
   } 
} 

No.4 使所有区间的异或结果为零

解题思路

DP

代码展示

class Solution { 
   public int minChanges(int[] nums, int k) { 
       // count[i][j] 表示在每个长度为 k 的子区间的第 i 个位置上，数字 j 出现了多少次 
       int[][] count = new int[k][1 << 10]; 
       for (int i = 0; i < nums.length; i++) { 
           count[i % k][nums[i]]++; 
       } 

       // dp[i] 表示将每个子区间的前 i 个位置变成一致的至少要改变多少个数字 
       int[][] dp = new int[k + 1][1 << 10]; 
       for (int i = 0; i <= k; i++) { 
           Arrays.fill(dp[i], nums.length); 
       } 
       dp[0][0] = 0; 

       int min = nums.length, sum = 0; 
       for (int i = 1; i <= k; i++) { 
           int[] cur = count[i - 1]; 
           int tot = 0, max = 0; 
           for (int j : cur) { 
               tot += j; 
               max = Math.max(max, j); 
           } 
           sum += tot - max; 
           min = Math.min(min, max); 
           for (int j = 0; j < (1 << 10); j++) 
               if (cur[j] > 0) { 
                   int now = tot - cur[j]; 
                   for (int K = 0; K < (1 << 10); K++) 
                       dp[i][j ^ K] = Math.min(dp[i][j ^ K], dp[i - 1][K] + now); 
               } 
       } 
       return Math.min(dp[k][0], min + sum); 
   } 
}

上岸3月公益带刷活动