腾讯音乐笔试——04.18

题目

  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个元素中,和为jj为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");
            }
        }
    }
}
#题解##腾讯音乐##笔试##恒生#
全部评论
牛啊牛啊,我就做出1、2,第四题对了百分之30的用例,估计进不了面了
点赞 回复 分享
发布于 04-18 22:37 浙江

相关推荐

10-09 22:05
666 C++
找到工作就狠狠玩CSGO:报联合国演讲,报电子烟设计与制造
点赞 评论 收藏
分享
评论
4
13
分享
牛客网
牛客企业服务