腾讯笔试 第五题 动态规划 成功通过

第三题我完全参考了檐之同学的思路，可以把算法复杂度从O(n2)降到O(n)。附上原作者的链接：https://www.nowcoder.com/discuss/226305?type=post&order=time&pos=&page=1 申请两个数组，lookBackward[i]表示向坐标递减的方向看时，在i位置能看到的楼的个数；lookForward[i]表示向坐标递增的方向看时，在i位置能看到的楼的个数。用栈的size记录楼的个数，若栈顶楼高小于等于当前遍历到的楼高则pop栈顶，否则直接push新楼。 很巧妙的地方是，计算lookBackward数组时从前往后遍历，计算lookForward数组时从后向前遍历，这样刚刚分析的逻辑才成立。最后记得算上当前楼，输出+1。代码如下： import java.util.Scanner; import java.util.*; 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[] lookBackward = new int[n];         int[] lookForward = new int[n];         int[] results = new int[n];         Deque<Integer> stack = new ArrayDeque<>();         stack.push(nums[0]);         for(int i = 1; i < n; i++){              lookBackward[i] = stack.size();             if(!stack.isEmpty() && nums[i] >= stack.peek()){                  stack.pop();             }             stack.push(nums[i]);         }         stack.clear();         stack.push(nums[n-1]);         for(int i = n-2; i >= 0; i--){             lookForward[i] = stack.size();             if(!stack.isEmpty() && nums[i] >= stack.peek()){                 stack.pop();             }             stack.push(nums[i]);         }         for(int i=0; i < n; i++){             results[i] = lookBackward[i] + lookForward[i] + 1;             System.out.print(results[i] + " ");         }     } }

解决第一题的方法其实和leetcode上394. Decode String很像，如果用迭代思想的话需要两个 stack 来辅助运算，一个用来保存个数，一个用来保存字符串。 我们遍历输入字符串，如果遇到数字，更新计数变量num。如果遇到'['，把当前字符串t压入字符串栈中，并将t清零。如果遇到'|'，我们把当前num压入数字栈中，并把num清零。如果遇到']'，我们取出数字栈中顶元素，存入变量n，然后给字符串栈的顶元素循环加上n个当前t字符串，然后更新t的值。如果遇到字母，我们直接加入当前字符串t中即可。一定要注意是把当前的字符串t重复数字栈顶的次数后加到字符串栈顶的字符后面（有点儿绕🤣）代码如下： import java.util.Scanner; import java.util.*; public class Main {     public static void main(String[] args) {          Scanner sc = new Scanner(System.in);          String s = sc.nextLine();          StringBuilder t = new StringBuilder("");          int num = 0;          Deque<Integer> stackNum = new ArrayDeque<>();          Deque<StringBuilder> stackStr = new ArrayDeque<>();          for(int i = 0; i < s.length(); i++){              char c = s.charAt(i);              if(c >= '0' && c <= '9'){                  num = 10 * num + c - '0';              }else if(c == '['){                  stackStr.push(t);                  t = new StringBuilder("");              }else if(c == '|'){                  stackNum.push(num);                  num = 0;              }else if(c == ']'){                  int n = stackNum.pop();                  StringBuilder sb = stackStr.pop();                  for(int j = 0; j < n; j++){                      sb.append(t);                  }                  t = sb;              }else{                  t.append(c);              }          }         System.out.println( t.toString());     } }

import java.util.Scanner; public class Main {     public static void main(String[] args) {         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();         }         helper(A, B, N);     }     public static void helper(int[] A, int[] B, int N) {         int[] dpA = new int[N];         int[] dpB = new int[N];         dpA[0] = A[0];         dpB[0] = B[0];         for (int i = 1; i < N; i++) {             if (A[i - 1] == 0) {                 dpA[i] = Math.max(dpA[i - 1], dpB[i - 1]) + A[i];             } else {                 dpA[i] = dpB[i - 1] + A[i];             }             if (B[i - 1] == 0) {                 dpB[i] = Math.max(dpA[i - 1], dpB[i - 1]) + B[i];             } else {                 dpB[i] = dpA[i - 1] + B[i];             }         }         System.out.println(N - Math.max(dpA[N - 1], dpB[N - 1]));     } }

解决第三题时的方法和leetcode上45.Jump Game II也很像，都是用到了贪心的思想。 先说leetcode上的那道题，初始化lastMax = 0, curMax = 0两个指针，每次遍历i <= lastMax的所有nums[i]的值，并计算i+nums[i]（相当于计算每个i能到达的最大位置下标）取最大的那个，进而更新curMax和lastMax指针。注意当lastMax>=length-1时就得到最终跳跃的步数，而当某一次的while循环中lastMax == curMax说明不可能跳到数组最后一个下标。代码如下： class Solution {     public int jump(int[] nums) {        if(nums == null || nums.length <= 1){            return 0;        }         int step = 0, lastMax = 0, curMax = 0, i = 0;         while(lastMax < nums.length-1){             while(i <= lastMax && i < nums.length){                 curMax = Math.max(curMax, i+nums[i]);                 i += 1;             }             if(lastMax == curMax){                 return -1;             }             step += 1;             lastMax = curMax;         }         return step;     } } 再说这道题，将每个炮塔的控制范围按照起始点排序以后，每次遍历list.get(i).start <= end(当前区间终点)的所有区间，取终点最大的那个，进而更新end。注意当某一次的while循环中出现end < list.get(i).start的情况时返回-1（这也就是为什么要按照起点排序，因为后面i+1、i+2……的start会更大），另外当遍历结束后的那个end小于l时也返回-1。代码如下： import java.util.Scanner; import java.util.*; public class Main {     public static class Pair{         int start, end;         public Pair(int s, int e){             this.start = s;             this.end = e;         }     }     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int answer = 0;         int n = sc.nextInt();         int l = sc.nextInt();         List<Pair> list = new ArrayList<Pair>();         for(int i = 0; i < n; i++){             int s = sc.nextInt();             int e = sc.nextInt();             Pair p = new Pair(s, e);             list.add(p);         }         Collections.sort(list, new Comparator<Pair>() {             @Override             public int compare(Pair o1, Pair o2) {                 if(o1.start != o2.start){                     return o1.start - o2.start;                 }else{                     return o1.end - o2.end;                 }             }         });         if(n == 1){             if(list.get(0).start>0 || list.get(0).end<l){                 System.out.println(-1);             }else{                 System.out.println(1);             }         }else{             int start = list.get(0).start;             int end = list.get(0).end;             if(start > 0){                 System.out.println(-1);             }else{                 answer += 1;                 int i =1;                 while(i < n){                     if(end >= l){                         System.out.println(answer);                         return;                     }                     if(end < list.get(i).start){                         System.out.println(-1);                         return;                     }                     int newEnd = -1;                     while(i < n && list.get(i).start <= end){                         newEnd = Math.max(list.get(i).end, newEnd);                         i += 1;                     }                     answer += 1;                     end = newEnd;                 }                 if(end < l){                     System.out.println(-1);                 }else{                     System.out.println(answer);                 }             }         }     } }

100，0，10，100，100。第二题咋搞?完全没时间想

第五题思路能麻烦说下么