目录

腾讯2020校园招聘第一题：压缩算法相关Leetcode 394. 字符串解码 腾讯2020校园招聘第二题：逛街腾讯2020校园招聘第四题：假期腾讯2020校园招聘第五题：视野争夺（AC50%）相关Leetcode 45. 跳跃游戏 II相关Leetcode 1024. 视频拼接

腾讯2020校园招聘第一题：压缩算法

import java.util.Stack; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String s=sc.next(); System.out.println(decodeString(s)); } public static String decodeString(String s) { if(s.length()==0) { return s; } StringBuilder ss=new StringBuilder(); //把[丢弃，没啥用 for(Character c:s.toCharArray()) { if(c!='[') { ss.append(c); } } Stack<Integer> numsStack=new Stack<>(); Stack<StringBuilder> stringStack=new Stack<>(); int mul=0; StringBuilder sb=new StringBuilder(); for (Character c : ss.toString().toCharArray()) { if(c>='0' && c<='9') { mul=mul*10+(c-'0'); } else if(c=='|') { //入栈 numsStack.push(mul); stringStack.push(sb); sb=new StringBuilder(); mul=0; } else if(c==']') { //出栈 int cnt=numsStack.pop(); StringBuilder tmp=sb; sb=stringStack.pop(); for (int i = 0; i < cnt; i++) { sb.append(tmp); } } else { sb.append(c); } } return sb.toString(); } }

---

相关Leetcode 394. 字符串解码

class Solution { public String decodeString(String s) { if(s.length()==0){ return s; } int mul=0; Stack<Integer> numsStack=new Stack<>(); Stack<StringBuilder> sbStack=new Stack<>(); StringBuilder sb=new StringBuilder(); for(char c:s.toCharArray()){ if(c=='['){ numsStack.push(mul); mul=0; sbStack.push(sb); sb=new StringBuilder(); } else if(c==']'){ int count=numsStack.pop(); StringBuilder tmp=sb; sb=sbStack.pop(); for(int i=0;i<count;i++){ sb.append(tmp); } } else if(c>='0' && c<='9'){ mul=mul*10+(c-'0'); } else{ sb.append(c); } } return sb.toString(); } }

字符串压缩题型的思路： 1.关注的是数字和字符串之间的关系，无关什么符号 2.使用栈来保存前面的数字和字符串 3.入栈时将前面的数字和字符串都存入 4.出栈时将最近的（栈顶的）数字和字符串进行append，使用临时变量存储。

---

---

腾讯2020校园招聘第二题：逛街

import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int[] nums=new int[n]; for (int i = 0; i < n; i++) { nums[i]=sc.nextInt(); } int[] result=new int[nums.length]; Stack<Integer> leftStack=new Stack<>(); for(int i=0;i<nums.length;i++) { result[i]=leftStack.size(); if(i!=0) { while((!leftStack.isEmpty())&&nums[i]>=leftStack.peek()) { leftStack.pop(); } } leftStack.push(nums[i]); } Stack<Integer> rightStack=new Stack<>(); for(int i=nums.length-1;i>=0;i--) { result[i]+=rightStack.size(); if(i!=0) { while((!rightStack.isEmpty())&&nums[i]>=rightStack.peek()) { rightStack.pop(); } } rightStack.push(nums[i]); } for (int i = 0; i < result.length; i++) { System.out.print(result[i]+1+" "); } } }

---

---

腾讯2020校园招聘第四题：假期

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] work=new int[n]; int[] exercise=new int[n]; for (int i = 0; i < n; i++) { work[i]=sc.nextInt(); } for (int i = 0; i < n; i++) { exercise[i]=sc.nextInt(); } int[][] dp=new int[3][n+1]; for(int i=0;i<3;i++) { Arrays.fill(dp[i], Integer.MAX_VALUE); } //第0天在休息 dp[0][0]=1; //第0天在工作 dp[1][0]=0; //第0天在锻炼 dp[2][0]=0; for (int i = 1; i <= n; i++) { //这一天可以work;今天work的话的最少休息时间 if(work[i-1]==1) { dp[1][i]=Math.min(dp[0][i-1],dp[2][i-1]); } //这一天可以exercise，今天exercise的最少休息时间 if(exercise[i-1]==1) { dp[2][i]=Math.min(dp[0][i-1],dp[1][i-1]); } //这一天可以relax,今天在relax的最少时间 dp[0][i]=Math.min(Math.min(dp[0][i-1],dp[1][i-1]), dp[2][i-1])+1; } int res=Math.min(Math.min(dp[0][n], dp[1][n]), dp[2][n]); System.out.println(res); } }

---

---

腾讯2020校园招聘第五题：视野争夺（AC50%）

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int L=sc.nextInt(); int[][] river=new int[n][2]; for (int i = 0; i < n; i++) { river[i][0]=sc.nextInt(); river[i][1]=sc.nextInt(); } int start=0; int end=0; int count=0; while(start<L) { for(int i=0;i<n;i++) { if(river[i][0]<=start) { end=Math.max(end, river[i][1]); } } count++; if(end>=L) { System.out.println(count); } if(end==start) { System.out.println(-1); } start=end; } } }

---

相关Leetcode 45. 跳跃游戏 II

class Solution { public int jump(int[] nums) { int maxposition=0; int end=0; int steps=0; for(int i=0;i<nums.length-1;i++){ maxposition=Math.max(maxposition,nums[i]+i); if(i==end){ end=maxposition; steps++; } } return steps; } }

贪心算法：假设每一次你都可以到达最远处 1.变量maxposition：nums[i]+i就是当前可以跳到的最远处 2.变量end：这是判断i是否已经遍历到当前圈的边界点了i==end。如果是的话，下一个i就是下一个圈了，要把end指向下一个圈的边界点，也就是maxposition。这是当前圈能跳到的最大范围了。 3.变量steps：要注意遍历到倒数第二个数！最后一个数是多少其实和题目一点关系也没有。

---

相关Leetcode 1024. 视频拼接

class Solution { public int videoStitching(int[][] clips, int T) { int start=0; int end=0; int count=0; while(start<T){ //每一个clip end=0; //求出最大的end for(int i=0;i<clips.length;i++){ if(clips[i][0]<=start){ end=Math.max(clips[i][1],end); } } count++; if(end>=T){ return count; } if(end==start){ return -1; } start=end; } return -1; } }