腾讯音乐笔试 09.26 AC

第一题

// 字符串中只包含0和1，一次操作可以将相邻的两个字符变成'00'或'11'
// 问，需要最少多少次操作将字符串全变成0或者全变成1.

    public int minOperations (String str) {
        char cs[] = str.toCharArray();
        return Math.min(fun(cs, '1'), fun(cs, '0'));
    }

    public int fun(char cs[], char target){
        int ret = 0;
        for(int i = 0; i < cs.length; i++){
            if(cs[i] == target){
                ret ++;
                i++;
            }
        }
        return ret;
    }

第二题

// 一个数组，问有多少个连续的子数组，使得其所有元素乘积后面0的个数大于等于x
// 数组长度 10**5
// [5, 2, 3, 50, 4] , 2
// [5, 2, 3, 50] [5, 2, 3, 50, 4] [2, 3, 50, 4] [2, 3, 50] [3, 50, 4] [50, 4] 共 6 种

// 暴力
// 找每个位置2、5个数，这个肯定都能想到
// 然后查看 [i-j] 区间中 2、5 的个数

// 优化
// 前缀和 + 二分查找 （下面的代码）

// 再优化
// 评论区大佬提出使用滑窗的思路，直接 O(n) ，代码略

    static  int arr[][];
    static  int n;
    public static int getSubarrayNum (ArrayList<Integer> a, int x) {
        n = a.size();
        arr = new int[n+1][2];
        // 先存储每个位置 2、5 个数
        for(int i = 0; i < n; i++){
            int tmp = a.get(i);
            while(tmp % 2 == 0){
                arr[i+1][0]++;
                tmp = tmp/2;
            }
            tmp = a.get(i);
            while(tmp%5 == 0){
                arr[i+1][1]++;
                tmp = tmp / 5;
            }
        }
        // 计算前缀和
        for(int i = 1; i <= n; i++){
            arr[i][0] += arr[i-1][0];
            arr[i][1] += arr[i-1][1];
        }
        // 二分查找
        long ret = 0;
        for(int i = 0; i <= n; i++){
            int a2 = findIdx(0, x + arr[i][0]);
            int b2 = findIdx(1, x + arr[i][1]);
            // if(a2 > n || b2 > n) continue;
            ret += (n+1) - Math.max(a2, b2);
            ret = ret % 1000000007;
        }
        return (int)ret;
    }

    // 找满足 arr[][idx] >= val 的最左侧索引
    public static  int findIdx(int idx, int val){
        int left = 1;
        int right = n;
        int ret = n+1;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(arr[mid][idx] < val){
                left = mid + 1;
            }else{
                right = mid-1;
                ret = mid;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int arr[] = new int[]{5, 2, 3, 50, 4};
        ArrayList<Integer> l = new ArrayList<>();
        for(int item : arr) l.add(item);
        System.out.println(getSubarrayNum(l, 2));
    }

第三题

// 数学 or 找规律题目
// 定义一个规则A：2*2区域内4个数据的和为偶数。
// 此时，有一个 N * M 的矩阵(2 <= n, m <= 10 ** 9)，可以选择[1,x] (x为偶数) 中的可重复的数据进行填充
// 问，有多少种填写方式，使得这个矩阵每个 2*2 区域都符合规则 A。
// n = 2, m = 2, x = 2 result = 8，如下所示（二维转一维了，凑合看吧）
// [1, 1, 1, 1] [1, 1, 2, 2] [1, 2, 1, 2] [1, 2, 2, 1] [2, 1, 2, 1] [2, 2, 1, 1] [2, 1, 1, 2] [2, 2, 2, 2]

    public int numsOfGoodMatrix (int n, int m, int x) {
        long ret = 2;
        long a = func(2, m-1); // 上册
        a = a % 1000000007;
        long b = func(2, n-1); // 左侧
        b = b % 1000000007;
        ret = ret * a;
        ret = ret % 1000000007;
        ret = ret * b;
        ret = ret % 1000000007;
        // n*m 数值
        long c = func(x>>1, m);
        c = func((int)c, n);
        ret = ret * c;
        return (int)(ret % 1000000007);
    }

    public long func(int val, int cnt){
        if(cnt == 1) return val;
        long t = func(val, cnt>>1);
        t = t % 1000000007;
        t = t * t;
        t = t % 1000000007;
        if((cnt & 1) == 0){
            return t;
        }else{
            t = t * val;
            t = t % 1000000007;
            return t;
        }
    }