题目

1. 对链表每两个元素之间插入0
2. 构造一颗满二叉树，要求每层之和相等
3. 给定个数字，各有红\白颜色标注，若为红色则该元素必选，否则可选。问有几种方案使得结果已选元素之和为偶数，对取模
4. 给定01串，可操作k次使得元素置0，问最长的连续的1串的长度最短为多少？

题解

1. 枚举即可

   public class Main {
       public ListNode insert0 (ListNode head) {
           ListNode curr = null, ans = null;
           while (head != null) {
               if (curr == null) {
                   ans = curr = new ListNode(head.val);
               } else {
                   curr = curr.next = new ListNode(head.val);
   
               }
   
               head = head.next;
               if (head != null) {
                   curr = curr.next = new ListNode(0);
               }
           }
           return ans;
       }
   }
   

2. 直接dfs遍历建树，我的赋值策略是当前这层的前面的节点值是1，最后一个是余数，和为。当然也可以每个节点固定为。（这里和是还是都随意的，反正固定即可。）

   public class Main {
       public TreeNode create (int n) {
           return dfs(0, 1, n);
       }
   
       private TreeNode dfs(int dep, int idx, int tar) {
           TreeNode curr;
           if (idx == (1 << dep)) {// last one
               curr = new TreeNode((1 << (tar - 1)) - (idx - 1));
           } else {
               curr = new TreeNode(1);
           }
   
           if (dep + 1 != tar) {
               curr.left = dfs(dep + 1, idx * 2 - 1, tar);
               curr.right = dfs(dep + 1, idx * 2, tar);
           }
           return curr;
       }
   }
   

3. dp

   dp[i][j]为前i个元素中，和为j（j为0表示偶数，j为1表示奇数）的方案数。初始化dp[0][0] = 1，表示没有选择任何元素（和为0，即偶数）的方案数为1。

   然后，我们遍历每个元素。对于第i个元素，如果它的颜色是红色，那么我们必须选择它。如果元素的颜色是白色，那么我们可以选择也可以不选择它。

   • 当元素颜色为红色时：

     

   • 当元素颜色为白色时：

     
     

   最后的答案为dp[n][0]。（我这里滚动以优化内存和方便写，可以不滚。）

   public class Main {
       public int getMethod(ListNode head, String colors) {
           int idx = 0;
           long mod = (long) 1e9 + 7;
           long[][] dp = new long[2][2];// j的0是偶数，1是奇数
           dp[idx ^ 1][0] = 1;
   
           for (int i = 0; i < colors.length(); ++i, idx ^= 1, head = head.next) {
               dp[idx][0] = dp[idx][1] = 0;
               if (colors.charAt(i) == 'R') {
                   dp[idx][(0 + head.val) % 2] += dp[idx ^ 1][0];
                   dp[idx][(1 + head.val) % 2] += dp[idx ^ 1][1];
               } else {
                   dp[idx][0] += dp[idx ^ 1][0];
                   dp[idx][1] += dp[idx ^ 1][1];
                   dp[idx][(0 + head.val) % 2] += dp[idx ^ 1][0];
                   dp[idx][(1 + head.val) % 2] += dp[idx ^ 1][1];
               }
   
               dp[idx][0] = dp[idx][0] % mod;
               dp[idx][1] = dp[idx][1] % mod;
           }
           return (int) dp[idx ^ 1][0];
       }
   }
   

4. 二分可行的长度，check就是遍历是否可行，若超了，则需要重新置0

   public class Main {
       public int maxLen(String s, int k) {
           int n = s.length();
           int l = -1, r = n + 1;
           while (l + 1 != r) {
               int mid = (l + r) / 2;
               if (check(s, mid, k)) r = mid;
               else l = mid;
           }
           return r;
       }
   
       private boolean check(String s, int len, int k) {
           for (int i = 0, j = 0; i < s.length(); ++i) {
               if (s.charAt(i) == '1') {
                   if (++j > len) {
                       if (--k < 0) return false;
                       j = 0;
                   }
               } else {
                   j = 0;
               }
   
           }
           return true;
       }
   }
   

彩蛋

恒生这场也打了，但是第一题暴力只过了80%，就没好意思贴出来，正解为dp，两维即可。因为*可以匹配多个相同字符，但是可能不匹配完，留几个给.来匹配。

比如：

下面是第二题，存每天的最小最大价钱即可，然后直接判。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        List<int[]> mn = new ArrayList<>();

        int n = in.nextInt();
        for (int i = 0; i < n; ++i) {
            int x = in.nextInt(), y = in.nextInt();
            if (mn.size() < x) mn.add(new int[]{y, y});
            else {
                mn.get(x - 1)[0] = Math.min(mn.get(x - 1)[0], y);
                mn.get(x - 1)[1] = Math.max(mn.get(x - 1)[1], y);
            }
        }

        for (int i = 0; i < mn.size(); i++) {
            System.out.print(i + 1 + " ");
            if (i < 2) System.out.println("N");
            else {
                if (Math.min(mn.get(i - 1)[0], mn.get(i - 2)[0]) + 5 <= mn.get(i)[1]) System.out.println("Y");
                else System.out.println("N");
            }
        }
    }
}