LIKE CODING

Monday, March 15, 2021

LeetCode [780] Reaching Points

780. Reaching Points

Hard

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True

Note:

sx, sy, tx, ty will all be integers in the range [1, 10^9].

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (sx < tx && sy < ty)
            if (tx < ty) ty %= tx;
            else tx %= ty;
        return sx == tx && sy <= ty && (ty - sy) % sx == 0 ||
               sy == ty && sx <= tx && (tx - sx) % sy == 0;
    }
}

LeetCode [1348] Tweet Counts Per Frequency

1348. Tweet Counts Per Frequency

Medium

Implement the class TweetCounts that supports two methods:

1. recordTweet(string tweetName, int time)

Stores the tweetName at the recorded time (in seconds).

2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

Returns the total number of occurrences for the given tweetName per minute, hour, or day (depending on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
The first time interval always starts from the startTime, so the time intervals are [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)> for some non-negative number i and delta (which depends on freq).

Example:

Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

Output
[null,null,null,null,[2],[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet.
tweetCounts.recordTweet("tweet3", 120);                            // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120.
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.

Constraints:

There will be at most 10000 operations considering both recordTweet and getTweetCountsPerFrequency.
0 <= time, startTime, endTime <= 10^9
0 <= endTime - startTime <= 10^4

class TweetCounts {
    Map<String, Integer> fMap = new HashMap<>();
    Map<String, TreeMap<Integer, Integer>> map = new HashMap<>();
    public TweetCounts() {
        fMap.put("minute", 60);
        fMap.put("hour", 60*60);
        fMap.put("day", 60*60*24);
    }
    
    public void recordTweet(String tweetName, int time) {
        if(!map.containsKey(tweetName)) map.put(tweetName, new TreeMap<>());
        TreeMap<Integer, Integer> tMap = map.get(tweetName);
        tMap.put(time, tMap.getOrDefault(time, 0)+1);
    }
    
    void printMap(String name){
        for(Map.Entry<Integer, Integer> en : map.get(name).entrySet()){
            System.out.print(en.getKey()+"->"+en.getValue()+"   ");
        }
        System.out.println();
    }
    
    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
   //     printMap(tweetName);
        List<Integer> list = new ArrayList<>();
        int d = fMap.get(freq);
        if(map.containsKey(tweetName)){
            TreeMap<Integer, Integer> tMap = map.get(tweetName);
            int a = startTime;
            while(a<=endTime){
                int b = a + d - 1;
                int r = 0;
                for(Map.Entry<Integer, Integer> en : map.get(tweetName).subMap(a, true, b, true).entrySet()){
                    r += en.getValue();
                }
                list.add(r);
                a = b+1;
            }
        }
        return list;
    }
}

LeetCode [1302]

1302. Deepest Leaves Sum

Medium

Given the root of a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Example 2:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19

Constraints:

The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 100

/**
 * 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 maxSum = Integer.MIN_VALUE;
    int maxLevel = -1;
    public int deepestLeavesSum(TreeNode root) {
        if(root==null) return 0;
        helper(root, 0);
        return maxSum;
    }
    
    void helper(TreeNode node, int level){
        
        if(node==null) return;
       // System.out.println(node.val+" "+level);
        if(node.left==null && node.right==null){
            if(level==maxLevel) maxSum += node.val;
            else if(level>maxLevel){
                maxSum = node.val;
                maxLevel = level;
            } 
        }else{
            helper(node.left, level+1);
            helper(node.right, level+1);
        }
    }
}

LeetCode [760] Find Anagram Mappings

760. Find Anagram Mappings

Easy

Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]

We should return

[1, 4, 3, 2, 0]

as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of A appears at B[4], and so on.

Note:

A, B have equal lengths in range [1, 100].
A[i], B[i] are integers in range [0, 10^5].

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        int n = A.length;
        Map<Integer, Set<Integer>> mapB = new HashMap<>();
        for(int i=0; i<n; ++i){
            mapB.computeIfAbsent(B[i], k->new HashSet<>()).add(i);
        }

        int[] ret = new int[n];
        for(int i=0; i<n; ++i){
            int v = A[i];
            int index = mapB.get(v).iterator().next();
            mapB.get(v).remove(index);
            ret[i] = index;
        }

        return ret;
    }
}

Tuesday, March 9, 2021

KMeans

package KMeans;

import java.util.*;
public class Main {
    public static void main(String[] args) {
        KMeans km = new KMeans();
        List<List<Integer>> lists = km.kmeans(new int[]{1,2,3,4,5,6,7,7,8,9,9,9,4,4,3});
        for(List<Integer> group:lists){
            System.out.println(group.toString());
        }
    }
}

class KMeans{
    final double D = 0.001;
    double getMean(List<Integer> group){
        double s = 0;
        for(int i : group) s+=i;
        return s/(double)group.size();
    }

    List<List<Integer>> kmeans(int[] nums){
        List<List<Integer>> list = new ArrayList<>();
        double m1 = nums[0], m2 = nums[1];
        while(true){
            System.out.println(m1 + " " + m2);
            List<Integer> g1 = new ArrayList<>();
            List<Integer> g2 = new ArrayList<>();
            for(int i : nums){
                if(Math.abs(i-m1)<=Math.abs(i-m2)){
                    g1.add(i);
                }else{
                    g2.add(i);
                }
            }

            double t1 = getMean(g1), t2 = getMean(g2);
            if(Math.abs(m1-t1)<=D && Math.abs(m2-t2)<=D){
                list.add(g1);
                list.add(g2);
                return list;
            }else{
                m1 = t1;
                m2 = t2;
            }
        }
    }
}

Thursday, January 21, 2021

LeetCode [740] Delete and Earn

740. Delete and Earn

Medium

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

class Solution {
    /*
    p2 p1 p0
       p2 p1
    */
    public int deleteAndEarn(int[] nums) {
        int n = 10001;
        int[] sum = new int[n];
        int max = 0;
        for(int i : nums) sum[i] += i;
        
        int p1 = 0, p2 = 0;
        for(int i=0; i<n; ++i){
            //max earned point until current position
            int p0 = Math.max(sum[i]+p2, p1);
            p2 = Math.max(p1, p2);
            p1 = p0;
            max = Math.max(max, p0);
        }
        
        return max;
    }
}