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个小时嘛。
- 0个:“0”
- 1个:“1”,“2”,“4”,“8”
- 2个:“3”,“5”,“6”,“9”,“10”
- 3个:“11”,“7”
下面一排:
- 0个:0
- 1个:1, 2, 4, 8, 16, 32
- 2个:48, 40, 36, 34, 33, 24, 20, 18, 17, 12, 10, 9, 6, 5, 3
- 3个:…
可以用一个双层循环先求出来。
实在太多,想不出来了,直接看答案了。
最优解
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;
}
}