Jerry's Blog

Recording what I learned everyday

View on GitHub


13 September 2019

LeetCode(7) -- 392, 401, 404, 405, 412

by Jerry Zhang

P392. Is Subsequence (Easy)

两个字符串S和t, 判断s是否是t的子序列。顺序不能变,这跟子集不一样。

我的思路

用两个索引i,j,一个指向string s的字符,另一个指向t的字符。遍历t,只要发现跟当前的s一样的,就把i向右移一位,说明找到了一个。直到循环结束,如果i == s.length,说明全找到了。

我的代码

public class E_392_IsSubsequence {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        for (int j = 0; j < t.length() && i < s.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
        }
        return i == s.length();
    }
}

超过69%

最优解

public class Solution {
    public boolean isSubsequence(String s, String t) {
        int lastCharPosition = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = t.indexOf(s.charAt(i), lastCharPosition);
            if(index < i) {
                return false;
            } else {
                lastCharPosition = index + 1;
            }
        }
        return true;
    }
}

用indexOf函数去找,从lastCharPosition开始找。不太明白为什么判断index < i, 如果没找到,应该返回-1,那就判断-1嘛,为啥要小于i? 在LeetCode上试了一下,判断等于-1也是正确的。

P401. Binary Watch (Easy)

二进制手表。第一行有四位,表示小时,每二行有7位,表示分钟。

给一个非负整数n,代表当前亮着的led灯的个数,也就是二进制里1的个数。求所有可能是时间。

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

我的思路

一共就只有11位,所有其实完全可以把所有的可能性提前列出来。。。肯定是最快的。。。但是那样可能性很多,一天24小时,一个小时60分钟,就一共有1440种可能。

正常方法,如果有n个灯是亮的,那首要问题就是这n个灯在这两排如何分配。比如有3个灯,那第一行可能有0个,1个,2个,3个。对应的就是二进制数里有n个1时,可能是多少。像刚才那样把一天的所有时间枚举出来,难度比较大,但是把4位数里,所有的情况全列出来就很容易了,一共12个小时嘛。

下面一排:

可以用一个双层循环先求出来。

实在太多,想不出来了,直接看答案了。

最优解

class Solution {

    private final static int[] nums = new int[]{1, 2, 4, 8, 1, 2, 4, 8, 16, 32};

    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        getTimes(res, 0, 0, 0, num);
        return res;
    }

    private void getTimes(List<String> res, int hrs, int mins, int index, int k) {
        if (hrs >= 12 || mins >= 60) {
            return;
        }
        if (k == 0) {
            String hour = String.valueOf(hrs);
            String minute = String.valueOf(mins);
            if (minute.length() == 1) {
                minute = "0" + minute;
            }
            res.add(hour + ":" + minute);
            return;
        }
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if (i <= 3) {
                hrs += nums[i];
                getTimes(res, hrs, mins, i + 1, k - 1);
                hrs -= nums[i];
            } else {
                mins += nums[i];
                getTimes(res, hrs, mins, i + 1, k - 1);
                mins -= nums[i];
            }
        }
    }
}

这个递归中,k是剩下的“点数”。每当点数用完时,就要在list中添加一个结果。

这个答案看了好久也不明白,又在讨论区找到一个非常容易理解的:

class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> times = new ArrayList<String>();
        for(int x = 0; x < 12; x++){
            for(int y = 0; y < 60; y++){
				// x - hours, y - minutes
				if(Integer.bitCount(x) + Integer.bitCount(y) == num){
					// - they must be equal to the number of LEDS given as an argument, so if this passes,
					//     proceed with making the string for this hour:minute combination.
                    StringBuilder sb = new StringBuilder();
                    sb.append(Integer.toString(x));
                    sb.append(":");
                    sb.append( ((y < 10) ? "0" : "") + Integer.toString(y));
                    times.add(sb.toString());
                }
            }
        }
        return times;
    }
}

P404. Sum of Left Leaves (Easy)

一个二叉树。求所有左叶节点的和。

我的思路

递归,如果某个节点是null,和当然也是null。如果左子节点是null,那就返回右子节点的递归结果。如果左子节点是叶节点,就把这个叶节点的值加上右边的递归和。最后,如果以上情况全不符合,那说明左子节点还有更深,就直接返回左右两棵子树的递归和。

我的代码

public class E_404_SumOfLeftLeaves {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return sumOfLeftLeaves(root.right);
        }
        if (root.left.left == null && root.left.right == null) {
            return root.left.val + sumOfLeftLeaves(root.right);
        }
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

100%

最优解

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return sumOfLeftLeaves(root, 0);
    }

    public int sumOfLeftLeaves(TreeNode root, int direction){
        if(root==null) return 0;
        if(root.left==null && root.right==null) return direction*root.val;
        return sumOfLeftLeaves(root.left, 1) + sumOfLeftLeaves(root.right, 0);
    }
}

这个很巧妙,辅助方法加了一个方向作为参数。因为最大的问题就是,当知道一个节点是叶节点时,我们并不知道它是左子节点还是右子节点。如果是右边就传0,左边就传1。再用这个参数乘以当前节点的值,就能只保留左叶节点的值了。

P405. Convert a Number to Hexadecimal (Easy)

给一个整数,转化为16进制。不许用已有的方法,要自己写。

我的思路

二进制转16进制,就四位一组,转化成相应的数就行了。要找到某一位,跟“1”做与运算即可。

我的代码

public class E_405_ConvertANumberToHexadecimal {
    public String toHex(int num) {
        if (num == 0) return "0";
        String res = "";
        while (num != 0) {
            int temp = num & 15;
            if (temp < 10) {
                res = temp + res;
            } else {
                res = (char)('a' + temp - 10) + res;
            }
            num = num >>> 4;
        }
        return res;
    }
}

100%

踩了几个坑:一开始忘记把a转化为字符了,出来的结果成了那个字符的ASCII码。 当num是负数时,死循环了。因为无论怎么往右移,负数都会在最前面补1,而不是补0。于是改成了“»>”,无符号右移。 最后是当num等于0时,我开始返回的是空字符串。其实应该返回“0”

最优解

class Solution {
    char[] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

    public String toHex(int num) {
        if (num == 0) return "0";
        String result = "";
        while (num != 0) {
            result = map[(num & 15)] + result;
            num = (num >>> 4);
        }
        return result;
    }
}

基本跟我的答案完全一样,只是我利用了ASCII码转化字符,他是用了一个数组返回对应值。

P412. Fizz Buzz (Easy)

输出1到n的字符串数组,遇到3的倍数,输出”Fizz”; 遇到5的倍数,输出”Buzz”; 遇到又是3又是5的倍数,就输出”FizzBuzz”.

我的思路

这个题很简单,尽量不出bug就行了。

我的代码

public class E_412_FizzBuzz {
    public List<String> fizzBuzz(int n) {
        ArrayList<String> strings = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                strings.add("FizzBuzz");
            } else if (i % 3 == 0) {
                strings.add("Fizz");
            } else if (i % 5 == 0) {
                strings.add("Buzz");
            } else {
                strings.add(String.valueOf(i));
            }
        }
        return strings;
    }
}

100%

最优解

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> l= new ArrayList<>();
        for(int i=1 ;i<=n; i++)
        {
            if(i%3==0 && i%5!=0)
            {
                l.add("Fizz");
            }
            else if(i%5==0 && i%3!=0)
            {
                l.add("Buzz");
            }
            else if(i%3==0 && i%5==0)
            {
                l.add("FizzBuzz");
            }
            else
            {
                l.add(String.valueOf(i));
            }
        }
        return l;
    }
}
tags: LeetCode