Leetcode 周赛No.123 笔记

第二次心血来潮参加Leetcode周赛,四道题目只做出两道,在看过排行榜的神奇题解后突然想坚持参加下去。以下做一下笔记吧。~

989. 数组形式的整数加法

对于非负整数 X 而言,X 的数组形式是每位数字按从左到右的顺序形成的数组。例如,如果 X = 1231,那么其数组形式为 [1,2,3,1]
给定非负整数 X 的数组形式 A,返回整数 X+K 的数组形式。

示例 1:

输入:A = [1,2,0,0], K = 34
输出:[1,2,3,4]
解释:1200 + 34 = 1234

解释 2:

输入:A = [2,7,4], K = 181
输出:[4,5,5]
解释:274 + 181 = 455

示例 3:

输入:A = [2,1,5], K = 806
输出:[1,0,2,1]
解释:215 + 806 = 1021

示例 4:

输入:A = [9,9,9,9,9,9,9,9,9,9], K = 1
输出:[1,0,0,0,0,0,0,0,0,0,0]
解释:9999999999 + 1 = 10000000000

提示:

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 9
  3. 0 <= K <= 10000
  4. 如果 A.length > 1,那么 A[0] != 0

思路:

第一道题就花了一个小时来完成:neutral_face:,本想将A与K都转化成long型相加后再转为List,结果发现给的测试用例中有更长的用例,遂转变为两个List相加与进位来实现。

//my code
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {        
        List<Integer> k = new ArrayList<Integer>();      
        List<Integer> kni = new ArrayList<Integer>();
        if(K==0)
            kni.add(0);
        else{
            while(K != 0){
                kni.add((int)(K % 10));
                K = (int)(K / 10);
            }
        }
        for(int i=kni.size()-1; i>=0; i--){
            k.add(kni.get(i));
        }

        List<Integer> a = new ArrayList<Integer>();
        for(int i=0; i<A.length; i++)
            a.add(A[i]);

        int maxLength = Math.max(a.size(), k.size());

        List<Integer> res = new ArrayList<Integer>();
        for(int i=0; i<maxLength+1; i++){
            res.add(0);
        }
        for(int i=1; i<=maxLength; i++){
            if(a.size()-i>=0&&k.size()-i>=0){
                res.set(res.size()-i, a.get(a.size()-i)+k.get(k.size()-i)+res.get(res.size()-i));
                res.set(res.size()-i-1, (int)(res.get(res.size()-i)/10));
                res.set(res.size()-i, res.get(res.size()-i)%10); 
            }else if(a.size()-i<0){
                res.set(res.size()-i, res.get(res.size()-i)+k.get(k.size()-i));
                res.set(res.size()-i-1, (int)(res.get(res.size()-i)/10));
                res.set(res.size()-i, res.get(res.size()-i)%10); 
            }else if(k.size()-i<0){
                res.set(res.size()-i, res.get(res.size()-i)+a.get(a.size()-i));
                res.set(res.size()-i-1, (int)(res.get(res.size()-i)/10));
                res.set(res.size()-i, res.get(res.size()-i)%10); 
            }
        }
        if(res.get(0)==0){
            res.remove(0);
        }
        return res;
    }
}

实现起来很复杂,还要判断A与K谁更长。后看过uwi的题解感觉真是巧妙呢,像加法器中CarryFlag一样,将K的值当作CarryFlag放入进位器中,从个位开始对A进位,最后如果因为K比A大而导致没进完位就手动进完。

//uwi's code
    class Solution {
        public List<Integer> addToArrayForm(int[] A, int K) {
            int n = A.length;
            int c = K;
            for(int i = A.length-1;i >= 0;i--){
                A[i] += c;
                c = A[i] / 10;
                A[i] %= 10;
            }
            List<Integer> ret = new ArrayList<>();
            while(c > 0){
                ret.add(0, c%10);
                c /= 10;
            }
            for(int v : A)ret.add(v);
            return ret;
        }
    }

990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b""a!=b"。在这里,ab 是小写字母(不一定不同),表示单字母变量名。
只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false

示例 1:

输入:["a==b","b!=a"]
输出:false
解释:如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2:

输入:["b==a","a==b"]
输出:true
解释:我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3:

输入:["a==b","b==c","a==c"]
输出:true

示例 4:

输入:["a==b","b!=c","c==a"]
输出:false

示例 5:

输入:["c==c","b==d","x!=z"]
输出:true

提示:

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3] 是小写字母
  4. equations[i][1] 要么是 '=',要么是 '!'
  5. equations[i][2] 是 '='

思路:

可以看出能够用连通图的方法解。先将相等的节点在图中连接,然后将每个连通分支标上不同的号码,此时同一连通分支的节点号码是相同的。最后判断每一个!=号断言的两个节点是否相等即可。

//my code
class Solution {
    public boolean equationsPossible(String[] equations) {
        Graph g = new Graph();
        for(int i=0; i<equations.length; i++){
            if(equations[i].charAt(1)=='='){
                g.link(equations[i].charAt(0), equations[i].charAt(3));
            }
        }
        g.draw();
        //检验
        for(int i=0; i<equations.length; i++){
            if(equations[i].charAt(1)=='!'){
                if(g.getPoint(equations[i].charAt(0))==g.getPoint(equations[i].charAt(3)))
                    return false;
            }
        }
        return true;
    }
}

class Graph{  //邻接矩阵实现的图
    int matrix[][] = new int[256][256];
    int points[] = new int[256];  //记录每个点的颜色编号
    public Graph(){
        for(int i=0; i<256; i++){
            for(int j=0;j<256;j++){
                matrix[i][j] = 0;
            }
            points[i] = -1;
        }
    }

    public void link(char a, char b){
        int num1 = (int)a, num2 = (int)b;
        this.matrix[num1][num2]=1;
        this.matrix[num2][num1]=1;
    }

    public void draw(){  //为每个连通分支深度优先标号
        int count=0;
        for(int i=0; i<256; i++){
            drawDeep(i, count);
            count++;
        }
    }
    public void drawDeep(int point, int count){
        if(points[point]==-1){
            points[point] = count;
            for(int i=0; i<256; i++){
                if(this.matrix[point][i]==1){
                    drawDeep(i, count);
                }
            }
        }
    }
    public int getPoint(int n){
        return this.points[n];
    }
}

排行榜上的题解直接用类似树的方法,为每个连通分支定义了一个根节点,比较时直接用根节点就可以比较。

# lg52931's code
class Solution(object):
    def equationsPossible(self, equations):
        """
        :type equations: List[str]
        :rtype: bool
        """
        par = [i for i in xrange(26)]
        def root(x):
            if x == par[x]:
                return x
            par[x] = root(par[x])
            return par[x]

        def join(a,b):
            x = root(a)
            y = root(b)

            par[y] = x

        for s in equations:
            if s[1] == '=':
                join(ord(s[0])-ord('a'), ord(s[3])-ord('a'))
        for s in equations:
            if s[1] == '!':
                if root(ord(s[0])-ord('a')) == root(ord(s[3])-ord('a')):
                    return False
        return True

991. 坏了的计算器

在显示着数字的坏计算器上,我们可以执行以下两种操作:

  • 双倍(Double):将显示屏上的数字乘 2;
  • 递减(Decrement):将显示屏上的数字减 1 。

最初,计算器显示数字 X
返回显示数字 Y 所需的最小操作数。

示例 1:

输入:X = 2, Y = 3
输出:2
解释:先进行双倍运算,然后再进行递减运算 {2 -> 4 -> 3}.

示例 2:

输入:X = 5, Y = 8
输出:2
解释:先递减,再双倍 {5 -> 4 -> 8}.

示例 3:

输入:X = 3, Y = 10
输出:3
解释:先双倍,然后递减,再双倍 {3 -> 6 -> 5 -> 10}.

示例 4:

输入:X = 1024, Y = 1
输出:1023
解释:执行递减运算 1023 次

提示:

  1. 1 <= X <= 10^9
  2. 1 <= Y <= 10^9

思路:

做到此题时已经没时间了,本来想是否能用动归来解,实践后发现会堆栈溢出,陷入循环递归。后来在想能否反过来,从Y到X就只需要+1➗2操作了,但是没有实现成功。uwi用到了二进制的思路,但是没有看懂。第二名lg52931的代码比较简单:

# lg52931's code
class Solution(object):
    def brokenCalc(self, X, Y):
        """
        :type X: int
        :type Y: int
        :rtype: int
        """
        ops = 0
        while Y > X:
            if Y % 2 == 1:
                ops += 1
                Y += 1
            else:
                Y /= 2
                ops += 1
        return ops + X - Y

用到了反过来从Y到X求解的思路,能除以2则除以2,不能则加1。因为除了再加总是比加了再除所执行的步数少的(举例才想通),因此可以这样解。

992. K 个不同整数的子数组

给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组。
(例如,[1,2,3,1,2] 中有 3 个不同的整数:12,以及 3。)
返回 A 中好子数组的数目。

示例 1:

输出:A = [1,2,1,2,3], K = 2
输入:7
解释:恰好由 2 个不同整数组成的子数组:[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2:

输入:A = [1,2,1,3,4], K = 3
输出:3
解释:恰好由 3 个不同整数组成的子数组:[1,2,1,3], [2,1,3], [1,3,4].

提示:

  1. 1 <= A.length <= 20000
  2. 1 <= A[i] <= A.length
  3. 1 <= K <= A.length

思路:

虽然这道题标记为Hard难度,但做起来似乎没那么难,像刷子一样从左往右刷就完事了。从A的第i位开始往右一位一位刷,总有这样的趋势:被刷到的部分拥有的整数个数从小于K,到等于K,再到大于K。每次等于K时计数器加一,每次大于K时break循环,开始从i+1位重新刷。

//my code
class Solution {
    public int subarraysWithKDistinct(int[] A, int K) {
        int res = 0;
        for(int i=0; i<A.length; i++){
            Bucket b = new Bucket(A.length);
            for(int j=0; j<A.length-i; j++){
                b.push(A[i+j]);
                if(b.getFillAmount()==K)
                    res++;
                else if(b.getFillAmount()>K)
                    break;
            }
        }
        return res;
    }
}
class Bucket{
    int a[];
    int fillAmount;
    public Bucket(int n){
        this.a = new int[n+1];
        Arrays.fill(a, 0);
        this.fillAmount = 0;
    }
    public void push(int d){
        if(a[d]==0)
            this.fillAmount++;
        this.a[d]++;
    }
    public int getFillAmount(){
        return fillAmount;
    }
}

写了一个“桶”类,存放每一个数字出现情况,以及被“刷”过的部分有几种数字(fillAmount,不空桶的数量)。不过,排行榜上的代码似乎都不大能看懂……

//uwi's code
    class Solution {
        public int subarraysWithKDistinct(int[] A, int K) {
            return count(A, K) - count(A, K-1);
        }

        int count(int[] a, int K)
        {
            int n = a.length;
            int[] f = new int[n+1];
            int dis = 0;
            int p = 0;
            int ret = 0;
            for(int i = 0;i < n;i++){
                if(++f[a[i]] == 1){
                    dis++;
                }
                while(dis > K){
                    if(--f[a[p++]] == 0){
                        dis--;
                    }
                }
                ret += i-p+1;
            }
            return ret;
        }
    }

附 新学到的知识点

java.util.Arrays

java.util.Arrays类能方便的操作数组,它所有的方法都是静态的。

  1. fill方法 :给数组中的某段元素附上相同值。
  2. sort方法:对数组中某段元素排序。
  3. equals方法:比较两个数组,判断的是数组中元素值是否相等。
  4. binarySearch方法:对排过序的数组进行二分法查找。
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注