LIKE CODING: October 2020

Friday, October 30, 2020

[LeetCode] 1612 Check If Two Expression Trees are Equivalent

1612. Check If Two Expression Trees are Equivalent

Medium

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (variables), and internal nodes (nodes with two children) correspond to the operators. In this problem, we only consider the '+' operator (i.e. addition).

You are given the roots of two binary expression trees, root1 and root2. Return true if the two binary expression trees are equivalent. Otherwise, return false.

Two binary expression trees are equivalent if they evaluate to the same value regardless of what the variables are set to.

Follow up: What will you change in your solution if the tree also supports the '-' operator (i.e. subtraction)?

Example 1:

Input: root1 = [x], root2 = [x]
Output: true

Example 2:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Output: true
Explaination: a + (b + c) == (b + c) + a

Example 3:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Output: false
Explaination: a + (b + c) != (b + d) + a

Constraints:

The number of nodes in both trees are equal, odd and, in the range [1, 4999].
Node.val is '+' or a lower-case English letter.
It's guaranteed that the tree given is a valid binary expression tree.

/**
 * Definition for a binary tree node.
 * class Node {
 *     char val;
 *     Node left;
 *     Node right;
 *     Node() {this.val = ' ';}
 *     Node(char val) { this.val = val; }
 *     Node(char val, Node left, Node right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] cnt = new int[26];
    public boolean checkEquivalence(Node root1, Node root2) {
        helper(root1, true);
        helper(root2, false);
        for(int i=0; i<26; ++i){
            if(cnt[i]>0) return false;
        }
        return true;
    }
    
    void helper(Node root, boolean add){
        if(root==null) return;
        helper(root.left, add);
        helper(root.right, add);
        if(root.left==null && root.right==null){
            cnt[root.val-'a'] += add?1:-1;
        }
    }
}

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=677356&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%255B3088%255D%255Bvalue%255D%3D12%26searchoption%255B3088%255D%255Btype%255D%3Dradio%26searchoption%255B3046%255D%255Bvalue%255D%3D1%26searchoption%255B3046%255D%255Btype%255D%3Dradio%26orderby%3Ddateline&page=1

判断两个树是否表达同一个数学表达式，树叶可以为数字，字母，+-*, 类似类似preorder traverse来表示表达式。

第二题就是前序周游序列化城字符串，比较字符串即可？还是我想简单了。楼主给个例子？

Thursday, October 29, 2020

LeetCode [682] Baseball Game

682. Baseball Game

Easy

You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds' scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:

An integer x - Record a new score of x.
"+" - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
"D" - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
"C" - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.

Return the sum of all the scores on the record.

Example 1:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

Example 2:

Input: ops = ["5","-2","4","C","D","9","+","+"]
Output: 27
Explanation:
"5" - Add 5 to the record, record is now [5].
"-2" - Add -2 to the record, record is now [5, -2].
"4" - Add 4 to the record, record is now [5, -2, 4].
"C" - Invalidate and remove the previous score, record is now [5, -2].
"D" - Add 2 * -2 = -4 to the record, record is now [5, -2, -4].
"9" - Add 9 to the record, record is now [5, -2, -4, 9].
"+" - Add -4 + 9 = 5 to the record, record is now [5, -2, -4, 9, 5].
"+" - Add 9 + 5 = 14 to the record, record is now [5, -2, -4, 9, 5, 14].
The total sum is 5 + -2 + -4 + 9 + 5 + 14 = 27.

Example 3:

Input: ops = ["1"]
Output: 1

Constraints:

1 <= ops.length <= 1000
ops[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 104, 3 * 104].
For operation "+", there will always be at least two previous scores on the record.
For operations "C" and "D", there will always be at least one previous score on the record.

class Solution {
    public int calPoints(String[] ops) {
        int n = ops.length, sum = 0;
        Stack<Integer> records = new Stack<>();
        for(int i=0; i<n; ++i){
            String op = ops[i];
            if(op.equals("+")){
                int prev1 = records.pop();
                int prev2 = records.pop();
                records.add(prev2);
                records.add(prev1);
                records.add(prev1+prev2);
                sum += prev1+prev2;
            }else if(op.equals("D")){
                sum += 2*records.peek();
                records.add(2*records.peek());
            }else if(op.equals("C")){
                sum -= records.pop();
            }else{
                int v = Integer.parseInt(op);
                sum += v;
                records.add(v);
            }
        }
        return sum;
    }
}

Wednesday, October 28, 2020

LeetCode [658] Find K Closest Elements

658. Find K Closest Elements

Medium

Given a sorted array arr, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Constraints:

1 <= k <= arr.length
1 <= arr.length <= 10^4
Absolute value of elements in the array and x will not exceed 104

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        int n = arr.length, l = 0, r = n-1, m=0;
        while(l<=r){
            m = (l+r)/2;
            if(arr[m]>=x && (m==0 || arr[m-1]<x)) break;
            else if(arr[m]<x) l = m+1;
            else r = m-1;
        }
        
        r = m;
        l = m-1;
        while(list.size()<k){
            if(l>=0 && r<n){
                if(x-arr[l]-(arr[r]-x)<=0)
                    list.add(0, arr[l--]);
                else
                    list.add(arr[r++]);
            }else if(l>=0) list.add(0, arr[l--]);
            else if(r<n) list.add(arr[r++]);
        }
        return list;
    }
}

LeetCode [438] Find All Anagrams in a String

438. Find All Anagrams in a String

Medium

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int[] cp = new int[26];
        int[] cs = new int[26];
        int l = 0, r = 0, ns = s.length(), np = p.length();
        
        for(char c : p.toCharArray()){
            cp[c-'a']++;
        }
        
        while(r<ns){
            int c = s.charAt(r++)-'a';
            if(cp[c]==0){
                l = r;
                cs = new int[26];
            }else{
                cs[c]++;
                while(cs[c]>cp[c]){
                    int c0 = s.charAt(l++)-'a';
                    cs[c0]--;
                }
            
                if(r-l==p.length()) list.add(l);
            }
        }
        
        return list;
    }
}

LeetCode [1026] Maximum Difference Between Node and Ancestor

1026. Maximum Difference Between Node and Ancestor

Medium

Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Example 1:

Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: 
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Note:

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int dm = 0;
    public int maxAncestorDiff(TreeNode root) {
        if(root==null) return dm;
        helper(root, root.val, root.val);
        return dm;
    }
    
    void helper(TreeNode root, int aMax, int aMin){
        if(root==null) return;
        int d = Math.max(Math.abs(root.val-aMax), Math.abs(root.val-aMin));
        dm = Math.max(dm, d);
        aMax = Math.max(aMax, root.val);
        aMin = Math.min(aMin, root.val);
        helper(root.left, aMax, aMin);
        helper(root.right, aMax, aMin);
    }
}

LeetCode [836] Rectangle Overlap

836. Rectangle Overlap

Easy

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Example 3:

Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]
Output: false

Constraints:

rect1.length == 4
rect2.length == 4
-109 <= rec1[i], rec2[i] <= 109
rec1[0] <= rec1[2] and rec1[1] <= rec1[3]
rec2[0] <= rec2[2] and rec2[1] <= rec2[3]

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        int x1a = rec1[0], y1a = rec1[1], x2a = rec1[2], y2a = rec1[3];
        int x1b = rec2[0], y1b = rec2[1], x2b = rec2[2], y2b = rec2[3];
        
        boolean xo = Math.max(x1a, x1b)<Math.min(x2a, x2b);
        boolean yo = Math.max(y1a, y1b)<Math.min(y2a, y2b);
        
        return xo&&yo;
    }
}