上岸算法
任何只教知识的课程都是耍流氓
我们直击上岸
关注我们，第一时间获得大厂面试真题讲解
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);
}
}
创作新主题