腾讯后端校招笔试(小菜鸡分享3道题，如有错误还望指正)
腾讯后端校招笔试(0/0/0/50/100) 菜鸡水平：
1. 压缩算法：
第1道没做出来，应该使用栈，后来看了其他大佬的分享，整理了1份Java版
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main( String[] args ) {
helper();
}
public static void helper(){
Scanner sc = new Scanner(System.in);
Stack<Character> stack = new Stack<>();
String s = sc.next();
int len = s.length();
for(int i=0;i<len;i++) {
char c = s.charAt(i);
if(c != ']') {
stack.push(c);
}else {
String tmp = "";
while(stack.peek() != '|') {
tmp += stack.pop();
}
stack.pop(); // 弹出 '|'
int n = 0, k = 1;
while(stack.peek() != '[') {
n += (stack.pop() - '0') * k;
k *= 10;
}
stack.pop(); // 弹出 '['
for(k=0;k<n;k++) {
for(int z=tmp.length()-1;z>=0;z--) {
stack.push(tmp.charAt(z));
}
}
}
}
int size = stack.size();
char[] res = new char[size];
for(int i=size-1;i>=0;i--) {
res[i] = stack.pop();
}
for(int i=0;i<size;i++) {
System.out.print(res[i]);
}
}
} 2. 逆序对：题目看完没理解，直接跳过 3.真视守卫：同上，跳过(寻思打LOL应该理解的透彻点，没卵用)
4.逛街：
笔试时只想到这个：站在某栋楼，分别朝左看、朝右看遍历计数，复杂度O(N^2)，超时(通过50%)
import java.util.Scanner;
public class Main {
public static void main( String[] args ) {
helper();
}
private static void helper() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] h = new int[n];
for(int i=0;i<n;i++) {
h[i] = sc.nextInt();
}
int[] res = new int[n];
int maxIndex;
for(int i=0;i<n;i++) {
res[i] = 1;
maxIndex = -1;
for(int j=i-1;j>=0;j--) {
if(maxIndex == -1 || h[maxIndex] < h[j]) {
maxIndex = j;
}
if(i - j == 1) {
res[i] ++;
}else if(h[j] > h[j + 1] && (j == maxIndex || h[j] > h[maxIndex])){
res[i] ++;
}
}
maxIndex = -1;
for(int j=i+1;j<n;j++) {
if(maxIndex == -1 || h[maxIndex] < h[j]) {
maxIndex = j;
}
if(j - i == 1) {
res[i] ++;
}else if(h[j] > h[j - 1] && (j == maxIndex || h[j] > h[maxIndex])){
res[i] ++;
}
}
}
for(int i=0;i<n;i++) {
System.out.print(res[i]+" ");
}
}
} 后来想到了，使用动态规划，能适当减少复杂度，但是不满足条件时仍然退化为O(N^2) import java.util.Scanner;
public class Main {
public static void main( String[] args ) {
helper();
}
private static void helper() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] h = new int[n];
for(int i=0;i<n;i++) {
h[i] = sc.nextInt();
}
if(n == 2) {
System.out.print("2 2");
}
int[] res = new int[n];
int[] left = new int[n+1]; // left[i]代表站在第i栋楼，可以看到i左侧的最多楼数(包含第i栋)
int[] right = new int[n+1]; // right[i]代表站在第i栋楼，可以看到i右侧的最多楼数(包含第i栋)
// 先左到右遍历一次，记录left数组
for(int i=2;i<=n;i++) {
if(i==2) {
left[i] = 1; // 第2栋楼肯定看得到第1栋楼
}else if(h[i-2] < h[i-3]) {
left[i] = left[i-1] + 1;
}else {
left[i] = 1; // 先看到左侧最近的一栋楼
int max = h[i-2];
for(int j=i-4;j>=0;j--) { // 退化为遍历
if(h[j] > max) {
left[i] ++;
}
}
}
}
for(int i=n-2;i>=0;i--) {
if(i == n - 2) { // 第n-1栋楼肯定看得到第n栋楼
right[i] = 1;
}else if(h[i+1] < h[i+2]) {
right[i] = right[i+1] + 1;
}else {
right[i] = 1; // 先看到右侧最近的一栋楼
int max = h[i+1];
for(int j=i+3;j<n;j++) {
if(h[j] > max) {
right[i] ++;
}
}
}
}
for(int i=0;i<n;i++) {
res[i] = left[i+1] + right[i] +1;
System.out.print(res[i] + " ");
}
}
} 5. 假期： 唯一AC的题，使用动态规划，定义dp[n+1][2]和a[n]、b[n]，其中dp[i][0]代表第i天工作或休息那么做事情(做事情=工作或健身)最多的天数，dp[i][1]代表第i天健身或休息那么做事情最多的天数，a数组工作，b数组代表健身，很容易得到状态转移：
dp[i][0] = Math.max(dp[i-1][1] + b[i-1], dp[i-1][0]);
dp[i][1] = Math.max(dp[i-1][0] + a[i-1], dp[i-1][1]);
dp[i][1] = Math.max(dp[i-1][0] + a[i-1], dp[i-1][1]);
import java.util.Scanner;
public class Main {
public static void main( String[] args ) {
helper();
}
private static void helper() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n]; // 工作
int[] b = new int[n]; // 健身
for(int i=0;i<n;i++) {
a[i] = sc.nextInt();
}
for(int i=0;i<n;i++) {
b[i] = sc.nextInt();
}
int[][] dp = new int[n+1][2];
for(int i=1;i<=n;i++) {
dp[i][0] = Math.max(dp[i-1][1] + b[i-1], dp[i-1][0]);
dp[i][1] = Math.max(dp[i-1][0] + a[i-1], dp[i-1][1]);
}
int max = Math.max(dp[n][0], dp[n][1]);
System.out.println(n - max);
}
} 体会就是： 1）思考的不够多
2）敲代码的熟练度有待提高
总结一个字——菜
不过没关系，心态最重要，心态不崩，啥都好说😝
查看5道真题和解析