每日一题补题记录8

本文主要是介绍每日一题补题记录8，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

2.20

717. 1 比特与 2 比特字符

有两种特殊字符：

第一种字符可以用一比特 0 表示
第二种字符可以用两比特（10 或 11）表示
给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。

简单遍历，遇见1走两步，遇见0走一步，如果能走到n-1,证明最后一个0一定是一比特字符

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int n=bits.length,i=0;
        while(i<n-1){
            if(bits[i]==0)i++;
            else i+=2;
        }
        return i==n-1;
    }
}

2.21

838. 推多米诺

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。
返回表示最终状态的字符串。

这个题目分析一下，任何两边都有变化的区间，由两端即可确定内部的变化，总共有四种：

1左L右R：不需处理

2左L右L：全部左倾

3左R右R：全部右倾

4左R右L：左半部右倾，右半部左倾，中间若有则平衡，若无更好

为了保证整个区间都是四种之一，我们给左右分别补上一个L一个R，这样可以简化判断，根据四种情况的分析，我们也知道这样处理不影响结果，然后我们用l\r两个指针指向任意区间两端，处理内部即可，注意室[l,r)的左闭右开区间，从1开始处理，避开最后一个补上的'R'即可

关键点：只有站着的牌才会受影响！

class Solution {
    public String pushDominoes(String dominoes) {
        StringBuffer sb=new StringBuffer();
        dominoes='L'+dominoes+'R';
        int n=dominoes.length();
        int l=0,r=0;
        for(r=1;r<n;r++){
            char c=dominoes.charAt(r);
            if(c=='.')continue;
            //注意0位置为我们加的虚拟字符L，不能加入
            if(l!=0)sb.append(dominoes.charAt(l));
            //cnt为.的个数,也即LR之间的长度
            int cnt=r-l-1;
            //无需处理中间部分
            if(dominoes.charAt(l)=='L'&&c=='R'){
                for (int i = 0; i < cnt; ++i) {
                    sb.append('.');
                }
                //左右相等，全部同化
            }else if(dominoes.charAt(l)==c){
                for (int i = 0; i < cnt; ++i) {
                    sb.append(c);
                }
            }else{
                for(int i=0;i<cnt/2;i++){
                    sb.append('R');
                }
                if(cnt%2!=0)sb.append('.');
                for(int i=0;i<cnt/2;i++){
                    sb.append('L');
                }
            }
            //窗口右移
            l=r;
        }
        return sb.toString();
    }
}

2.22

​​​​​​1994. 好子集的数目

给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。

比方说，如果 nums = [1, 2, 3, 4] ：
[2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。
[1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。
请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。

nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

这篇关于每日一题补题记录8的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！