腾讯后端笔试 除第二题全A思路
求第二题思路
1. 基本leetcode 394原题，没什么好说的
2. 求思路！！！
3. 贪心，按照起始点排序以后，每次遍历起点小于等于当前区间终点，取终点最大的那个。边界条件一个是中间发生不能覆盖的情况，一个是遍历完最后小于所求区间
package tencent.c0817.c;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int L = scanner.nextInt();
int[][] guard = new int[n][2];
for (int i = 0; i < n; i++) {
guard[i][0] = scanner.nextInt();
guard[i][1] = scanner.nextInt();
}
System.out.println(minGuards(guard, L));
}
private static int minGuards(int[][] guard, int len) {
Arrays.sort(guard, (a, b) -> a[0] - b[0]);
int end = 0;
int count = 0;
int i = 0;
while (i < guard.length) {
if (end >= len) {
break;
}
int max = end;
if (guard[i][0] > end) {
return -1;
}
while (i < guard.length && guard[i][0] <= end) {
if (guard[i][1] > max) {
max = guard[i][1];
}
i++;
}
end = max;
count++;
}
if (end < len) {
return -1;
}
return count;
}
}
4. 开向前看向后看两个数组，用栈，每次pop出比当前楼小的，用stack的size作为值，最后输出记得+1（当前楼）
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = scanner.nextInt();
}
int[] front = new int[n];
int[] back = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(heights[0]);
for (int i = 1; i < n; i++) {
front[i] = stack.size();
while (!stack.isEmpty() && stack.peek() <= heights[i]) {
stack.pop();
}
stack.push(heights[i]);
}
stack.clear();
stack.push(heights[n - 1]);
for (int i = n - 2; i >= 0; i--) {
back[i] = stack.size();
while (!stack.isEmpty() && stack.peek() <= heights[i]) {
stack.pop();
}
stack.push(heights[i]);
}
for (int i = 0; i < n; i++) {
System.out.print(front[i] + back[i] + 1);
System.out.print(" ");
}
}
}
5. dp，直接看代码吧……
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] company = new int[n];
int[] gym = new int[n];
for (int i = 0; i < n; i++) {
company[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
gym[i] = scanner.nextInt();
}
System.out.println(helper(company, gym));
}
private static int helper(int[] company, int[] gym) {
int n = company.length;
int[][] dp = new int[n][3];
if (company[0] == 0) {
dp[0][0] = 1;
}
if (gym[0] == 0) {
dp[0][1] = 1;
}
dp[0][2] = 1;
for (int i = 1; i < n; i++) {
int j = i - 1;
dp[i][0] = Math.min(dp[j][1], dp[j][2]) + (company[i] == 0 ? 1 : 0);
dp[i][1] = Math.min(dp[j][0], dp[j][2]) + (gym[i] == 0 ? 1 : 0);
dp[i][2] = Math.min(Math.min(dp[j][0], dp[j][1]), dp[j][2]) + 1;
}
return Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
}
}
