LeetCode每日一题October Challenge，每天打卡！

话不多说，打卡就是了。
624_Maximum Distance in Arrays
Java with detailed explanation.
Time complexity_O(n): Scan all arrays in one time
Solution: record the min and max value in different arrays

class Solution {

    public int maxDistance(List<List<Integer>> arrays) {
        // Step_1: Check corner cases
        // if the arrays smaller than 2 (equals 0 or 1), then return zero;
        if (arrays.size() < 2) {
            return 0;
        }

        // Step_2: Set the min and max value in the first arrays.get(0)
        // initiate the result to "0", result equals (max - min)
        // beacase the arrays are sorted, so the min is the first value and the max is the last value
        int min = arrays.get(0).get(0);
        int max = Integer.MIN_VALUE;
        int result = 0;
        for (int i: arrays.get(0)) {
            if (max < i) {
                max = i;
            }
        }

       // Step 3: record the max and min in every arrays
        // from arrays.get(0) -> arrays.size()
        for (int i = 1; i < arrays.size(); i++) {
            // initiate temp list to store the arrays.get(i)
            // initiate temp max and temp min
            List<Integer> temp = arrays.get(i);
            int n = temp.size();
            int tempMIN = temp.get(0);
            int tempMAX = temp.get(n - 1);

            if (tempMAX -  min > result) {
                result = tempMAX -  min;
            }
            if (max - tempMIN > result) {
                result = max - tempMIN;
            }

            // if tempMIN smaller than min, then update min
            // if tempMAX smaller than min, then update max
            if (tempMIN < min) {
                min = tempMIN;
            }
            if (tempMAX > max) {
                max = tempMAX;
            }

        }

        return result;
    }
}

十月第二题：933. Number of Recent Callsclass Recent Calls

It tests the knowledge about the basic data structure and algorithm.
The input is a sequence of ping calls, ordered by the chronological time of the arrical time.
The easiest data structure is combine array and sliding window to design and develop it.
   
    // Use a container as array to keep track of all the incoming calls.
    // The sequence is ever-growing
    // We can remove the historical calls withour meaning which before t - 3000. They are outdated.
    // It also can avoid overflow of the container and reduce the memory consumption to the least.
    // In summary, the container with function like a sliding window over the ever-growing sequence.
    // Therefore, the list beeter than array which can appending incoming calls and popping outdated calls.
   
    LinkedList<Integer> slideWindow;

    public RecentCounter() {
        this.slideWindow = new LinkedList<Integer>();
        
    }
   
    public int ping(int t) {
        // Step_1:
        // At each ping call, we append the call to the container.
        this.slideWindow.addLast(t);
   
        // Step_2:
        // For Array: starting from the current call, iterate backwards to the (t - 3000).
        // For list: starting from the head of the sliding wondow, and remove the outdated calls
        while (this.slideWindow.size() > 0) {
            if (this.slideWindow.getFirst() < t - 3000) {
                this.slideWindow.removeFirst();
            }
            else {
                break;
            }
        }
        return this.slideWindow.size();
    }
}

耶，第三天。

class Solution {
    // One of the series of combination sum.
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        LinkedList path = new LinkedList<Integer>();
        Arrays.sort(candidates);
        if (target < candidates[0]) {
            return result;
        }
        helper(candidates, 0, 0, target, path, result);
        return result;
    }
   
    public void helper(int[] candidates, int start, int sum, int target, LinkedList<Integer> path, List<List<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(path));
        }
        else if (sum > target) {
            // If the current combination is not valid, backtrack and. try another potion
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            helper(candidates, i, sum + candidates[i], target, path, result);
            path.removeLast();
        }
    }
}

第四天，周六，吃喝玩乐的一天。
比较简单，无注释。

class Solution {
    public int findPairs(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(nums[i] - nums[j]) == k) {
                    if (!map.containsKey(nums[i])) {
                        count++;
                        map.put(nums[i], nums[j]);
                    }
                }
            }
        }
        return count;
    }
}

做了两个小时，气坏了

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
      
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int count = 1;
        int end = intervals[0][1];
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] == intervals[i - 1][0]) {
                end = Math.max(end, intervals[i][1]);
                continue;
            }
            else {
                if (intervals[i][1] <= end) {
                    continue;
                }
                else {
                    end = Math.max(end, intervals[i][1]);
                    count++;
                }  
            }
        }
        
        return count;
    }
}

差点想一个一个转换成二进制。

class Solution {
    public int bitwiseComplement(int N) {
        if (N == 0) {
            return 1;
        }
        
        int temp = N, bit = 1;
        while (temp != 0) {
            N = N ^ bit;
            bit = bit << 1;
            temp = temp >> 1;
        }
        
        return N;
    }
}

星期二，第六天，打卡LeetCode October Challenge ：701_ Insert into a Binary Search Tree
详细Java代码加注释

class Solution {
    // BST advantages is a search for arbitary element in O(logN) time
    // Solution: insert new node as a child of the leaf
   
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // Recursion: three possibility
        // 1: root is null
        // 2: root.val > val -->leftTree
        // 3: root.val < val -->rightTree
        if (root == null) {
            return new TreeNode(val);
        }
        
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        else {
            root.right = insertIntoBST(root.right, val);
        }
        
        return root;
    }
}

以后就在十月挑战这里打卡了，还可以积攒大米。
耶，刷题每天得四米。
十月刷题挑战