leetcode 刷题记录打卡

2020 年 刷题打卡记录，之后会在新回复帖中慢慢更新

补充内容 (2020-4-17 12:08):
先从leetcode的30天challenge来开始做做看，之后每天和朋友稍微研究一点难一些的题目

补充内容 (2020-4-19 01:21):
在家一直在用黑板写题，感觉轻松很多，也会捕捉到好多平时光是码code时候的细节。
以后不一定会把每道题的解法都记录下来（毕竟有点耗时间）但我会定期update一下

leetcode 528 single number:


最佳解法:
class Solution {
    // time complexity O(n), space o(1)
    // 用bit manipulation （xor概念）来做这道题，
    //  x  y |
    // ------|
    //  0  0 | 0
    //  1  0 | 1
    //  0  1 | 1
    //  1  1 | 0

    // 遇到重复数字的话，他们会抵消，最后bit上的数字会变成0
    // Example:   2  ->  0010    那0010 xor 0010 就会变成0
    // 所以根据题意，最后留下来的数字肯定是只出现一次的数字
    // 最后直接return int结果
    public int singleNumber(int[] nums) {
        int bit = 0;
        for (int i = 0; i < nums.length; i++)
        {
            bit ^= nums[i];
        }
        return bit;
    }
}

解法2：
用hashmap做，具体代码就不po了。概念就是用hashmap来存key value pair， key是每个数字，value是数字出现的次数
一开始O(n)走一遍把element全放到hashmap里，最后O(n) 走一遍找只出现一次的数字就行. 这样空间的话还是O(n)，n为每个unique的数字

解法3:
看答案看到的一个自己认为巧妙的做法:

2*(a+b+c) - (a+a+b+b+c) = c

用set去存储所有已经遍历过得数字，用两个integer来算不同的数字和:
1. set的数字和
2. 原数列的数字和

最后用 （set的数字和）* 2  - （原数列的数字和）就可以得到答案

leetcode 202 happy number

用一个hashset去记录见过的数字，然后我的方法是用recursive的方式去计算每个数字的新的sum
class Solution {
    public Set<Integer> seen = new HashSet<Integer>();
   
    // recursion may cause stack problem
    public boolean isHappy(int n) {
        return recursiveHelper(n);
    }
   
    public boolean recursiveHelper(int n)
    {   
        int sum = 0;
        while (n > 0)
        {
            int remainder = n % 10;
            //System.out.println("remainder: " + remainder);
            sum += remainder * remainder;
            n = n / 10;
            
            //System.out.println("result sum: " + sum);
        }
        
        System.out.println(sum);
        if (sum == 1)
        {
            return true;
        }
        
        if (seen.contains(sum))
        {
            return false;
        }
        
        seen.add(sum);
        return recursiveHelper(sum);
    }
}
time complexity的计算方式好像有点特别，之后会进行复习和更新




补充内容 (2020-4-18 09:59):
class Solution {

    // 可以用类似fast and slow two pointer的做法来做
    // 只要有重合，就说明我们陷入了无限循环
   
    //Set<Integer> seen = new HashSet<>();

   
    public boolean isHappy(i...

leetcode 283 move zeroes

class Solution {
    public void moveZeroes(int[] nums) {
        // j 代表第一个位置
        // i 会进行遍历
        int j = 0;
        for (int i = 0; i < nums.length; i++)
        {
            if (nums[i] != 0)
            {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j = j + 1;
            }
        }
    }
}

time complexity是o(n)，只要遍历一次就能把所有0给放到最后

leetcode 104

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }

Time O(n) 全部遍历
space O(logn) queue里面最多存的node数量
*/
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
        {
            return 0;
        }
   
        
        Queue<TreeNode> q = new LinkedList<>();
        
        q.add(root);
        
        int height = 0;
        while (!q.isEmpty())
        {
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode node = q.poll();
            
                if (node.left != null)
                {
                    q.add(node.left);
                }
                if (node.right != null)
                {
                    q.add(node.right);
                }
            
               
            }     
            height += 1;
        }
            return height;
    }
}

解法2：
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }

Time O(n) 全部遍历
space O(logn) recursive stack的数量为树的层数
*/
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
        {
            return 0;
        }

        // 每次node有东西的时候，height会增加
        return Math.max(maxDepth(root.left) +1, maxDepth(root.right) +1);
    }
}

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
        {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> ans =new ArrayList<List<Integer>>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        while (!q.isEmpty())
        {
            List<Integer> subList = new ArrayList<Integer>();
            
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode dequeued = q.poll();
               
                subList.add(dequeued.val);
                if (dequeued.left != null)
                {
                    q.add(dequeued.left);
                }
               
                if (dequeued.right != null)
                {
                    q.add(dequeued.right);
                }
            }
            ans.add(subList);
            
        }
        
        return ans;
   
    }
}

level order traversal, 很基础，具体的就不多说了，如果有更好的解法欢迎大家喷我这个小白

Symmetric Tree:

Recursive:

相当于一个方法里有两个preorder traversal。 我的理解方式是，我们有两个pointer，一个朝着左边subtree，一个朝着右边subtree来进行traverse

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // two pointer, 两个treenode traverse
        
        return helper(root, root);
    }
   
    public boolean helper(TreeNode n1, TreeNode n2)
    {
        if (n1 == null && n2 == null)
        {
            return true;
        }
        if (n1 == null || n2 == null)
        {
            return false;
        }
        
        return (n1.val == n2.val) && helper(n1.left, n2.right) && helper(n1.right, n2.left);
    }
}

解法2： iterative， 自己的做法，和官方答案有点不一样
我认为官方答案有一点点偏烦，因为他是相当于在看一个tree的copy，然后进行preorder traversal进行左右比较

我的答案是直接检查第一个root，如果左subtree和右subtree不是null的话，在将它们放到queue里面在进行比较

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // level order traversal
        Queue<TreeNode> q = new LinkedList<>();
   
        
        if (root == null)
        {
            return true;
        }
        
        if (root.left == null && root.right == null)
        {
            return true;
        }
        
        if (root.left == null || root.right == null)
        {
            return false;
        }
        
        TreeNode p1 = root.left;
        TreeNode p2 = root.right;
        
        q.add(p1);
        q.add(p2);
        
        while (!q.isEmpty())
        {
            int size = q.size();
            
            for (int i = 0; i < size / 2; i++)
            {
                TreeNode n1 = q.poll();
                TreeNode n2 = q.poll();
               
                if (n1.val != n2.val)
                {
                    return false;
                }
               
                if (n1.left == null && n2.right == null)
                {

                } else if (n1.left == null || n2.right == null){
                    return false;
                } else{
                                       
                    q.add(n1.left);
                    q.add(n2.right);
                }

                if (n1.right == null && n2.left == null)
                {
                } else if (n1.right == null || n2.left == null){
                    return false;
                }else
                {
                    q.add(n1.right);
                    q.add(n2.left);  
                }
            }
            
        }
        
        return true;
    }
}

Path Sum recursive 做法，秒了

做法很简单，每次traverse的时候都把sum变掉，换成sum - 当前node.val的值，这样在看leaf node时候我们只要关心是否最后sum变成了0

或者换个思路，每次traverse的时候把当前的currSum给作为参数放到helper method里，这样在看leaf node的时候我们只关系是否sum == currSum + node的当前值
/** * Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
    /*public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
        {
            return false;
        }

        if (root.left == null && root.right == null && sum == root.val)
        {
            return true;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

    }*/
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
        {
            return false;
        }

        return helper(root, 0, sum);

    }

    public boolean helper(TreeNode root, int currSum, int sum)
    {
        if (root == null)
        {
            return false;
        }
        if (root.left == null && root.right == null && (currSum + root.val == sum))
        {
            return true;
        }

        return helper(root.left, root.val +currSum, sum) || helper(root.right,  root.val +currSum, sum);

    }
}

Path sum 自己的iterative 做法

用postorder traversal，用两个stack，一个stack记录当前的node，另一个记录当前的sum， 这样我们每次最后检查的node都会是leaf node，然后只要检查当前的sum等于我们要找的sum就行

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
        {
            return false;
        }
        
        Stack<TreeNode> nodeS = new Stack<>();
        Stack<Integer> sumS = new Stack<>();
        
        TreeNode curr = root;
        TreeNode prev = null;
        while (!nodeS.isEmpty() || curr != null)
        {
            while (curr != null)
            {
                nodeS.push(curr);
                int currSum = sumS.isEmpty() ? 0 : sumS.peek();
                sumS.push(currSum + curr.val);
                curr = curr.left;
            }
            
            TreeNode node = nodeS.peek();
            if (node.right == null || node.right == prev)
            {
                node = nodeS.pop();
                int currSum = sumS.pop();
                System.out.println("node is: " + node.val);
                System.out.println(currSum);
                if (node.left == null && node.right == null && currSum == sum)
                {
                    return true;
                }
                prev = node;
                curr = null;
            } else{
                curr = node.right;
            }
        }
        return false;
            
    }
   

}