LIKE CODING

Wednesday, August 26, 2020

LeetCode [932] Beautiful Array

932. Beautiful Array

Medium

For some fixed N, an array A is beautiful if it is a permutation of the integers 1, 2, ..., N, such that:

For every i < j, there is no k with i < k < j such that A[k] * 2 = A[i] + A[j].

Given N, return any beautiful array A. (It is guaranteed that one exists.)

Example 1:

Input: 4
Output: [2,1,4,3]

Example 2:

Input: 5
Output: [3,1,2,5,4]

Note:

1 <= N <= 1000

class Solution {
    public int[] beautifulArray(int N) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        while(list.size()<N){
            List<Integer> tmp = new ArrayList<>();
            for(int i : list){
                if(i*2-1<=N) tmp.add(i*2-1);
            }
            for(int i : list){
                if(i*2<=N) tmp.add(i*2);
            }
            list = tmp;
        }
        return list.stream().mapToInt(i->i).toArray();
    }
}

LeetCode [708] Insert into a Sorted Circular Linked List

708. Insert into a Sorted Circular Linked List

Medium

Given a node from a Circular Linked List which is sorted in ascending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the circular list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.

If the list is empty (i.e., given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the original given node.

Example 1:

Input: head = [3,4,1], insertVal = 2
Output: [3,4,1,2]
Explanation: In the figure above, there is a sorted circular list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list. The new node should be inserted between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.

Example 2:

Input: head = [], insertVal = 1
Output: [1]
Explanation: The list is empty (given head is null). We create a new single circular list and return the reference to that single node.

Example 3:

Input: head = [1], insertVal = 0
Output: [1,0]

Constraints:

0 <= Number of Nodes <= 5 * 10^4
-10^6 <= Node.val <= 10^6
-10^6 <= insertVal <= 10^6

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        if(head==null){
            node.next = node;
            head = node;
        }else{
            Node p = head;
            Node nxt = p.next;
            int cnt = 0;
            while(!((insertVal>=p.val && insertVal<=nxt.val) || (nxt.val<p.val && (insertVal<=nxt.val || insertVal>=p.val)) || cnt>1)){
                if(p==head) cnt++;
                p = nxt;
                nxt = p.next;
            }
            node.next = nxt;
            p.next = node;
        }
        return head;
    }
}

LeetCode [743] Network Delay Time

743. Network Delay Time

Medium

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        int w = Integer.MIN_VALUE;
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        for(int i=0; i<N; ++i){
            for(int[] e : times){
                int u = e[0], v = e[1], t = e[2];
                if(dist[u]!=Integer.MAX_VALUE && dist[u]+t<dist[v]){
                    dist[v] = dist[u]+t;
                }
            }
        }
        for(int i=1; i<=N; ++i){
            w = Math.max(w, dist[i]);
        }

        return w==Integer.MAX_VALUE?-1:w;
    }
}

LeetCode [1087] Brace Expansion

1087. Brace Expansion

Medium

A string S represents a list of words.

Each letter in the word has 1 or more options. If there is one option, the letter is represented as is. If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Return all words that can be formed in this manner, in lexicographical order.

Example 1:

Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: "abcd"
Output: ["abcd"]

Note:

1 <= S.length <= 50
There are no nested curly brackets.
All characters inside a pair of consecutive opening and ending curly brackets are different.

class Solution {
    List<String> ret = new ArrayList<>();
    List<List<Character>> list = new ArrayList<>();

    public String[] expand(String S) {
        int n = S.length(), i = 0;
        while(i<n){
            list.add(new ArrayList<>());
            if(Character.isAlphabetic(S.charAt(i))){
                list.get(list.size()-1).add(S.charAt(i));
                i++;
            }else{//{
                i++;//skip '{'
                while(i<n && S.charAt(i)!='}'){
                    if(Character.isAlphabetic(S.charAt(i)))
                        list.get(list.size()-1).add(S.charAt(i));
                    i++;
                }
                i++;//skip '{'
            }
        }

        helper(0, "");
        return ret.toArray(new String[0]);
    }

    void helper(int i, String cur) {
        if (i == list.size() && cur.length() > 0) {
            ret.add(cur);
        } else if (list.get(i).size() == 0) {
            helper(i + 1, cur);
        } else {
            Collections.sort(list.get(i));
            for (char c : list.get(i)) {
                helper(i + 1, cur + c);
            }
        }
    }
}

LeetCode [1219] Path with Maximum Gold

1219. Path with Maximum Gold

Medium

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

Every time you are located in a cell you will collect all the gold in that cell.
From your position you can walk one step to the left, right, up or down.
You can't visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Constraints:

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

class Solution {
    int maxSum = 0;
    int[][] grid;
    int m, n;
    int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int getMaximumGold(int[][] grid) {
        m = grid.length;
        if(m==0) return 0;
        n = grid[0].length;
        if(n==0) return 0;
        this.grid = grid;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]>0){
                    helper(i, j, 0);
                }
            }
        }
        return maxSum;
    }

    void helper(int i, int j, int sum){
        sum += grid[i][j];
        maxSum = Math.max(sum, maxSum);
        int t = grid[i][j];
        grid[i][j] = 0;
        for(int[] d: dir){
            int ii = i+d[0], jj = j+d[1];
            if(ii>=0 && ii<m && jj>=0 && jj<n && grid[ii][jj]>0){
                helper(ii, jj, sum);
            }
        }
        grid[i][j] = t;
    }
}

Tuesday, August 25, 2020

LeetCode [734] Sentence Similarity

734. Sentence Similarity

Easy

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, "great acting skills" and "fine drama talent" are similar, if the similar word pairs are pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are not necessarily similar.

However, similarity is symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Note:

The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].

class Solution {
    Map<String, Set<String>> map = new HashMap<>();
    public boolean areSentencesSimilar(String[] words1, String[] words2, List<List<String>> pairs) {
        int n1 = words1.length, n2 = words2.length;
        if(n1!=n2) return false;
        for(List<String> p : pairs){
            String w1 = p.get(0), w2 = p.get(1);
            if(!w1.equals(w2)){
                map.computeIfAbsent(w1, k->new HashSet<>()).add(w2);
                map.computeIfAbsent(w2, k->new HashSet<>()).add(w1);
            }
        }
        
        for(int i=0; i<n1; ++i){
            String w1 = words1[i], w2 = words2[i];
            if(w1.equals(w2)) continue;
            if(!map.containsKey(w1) || !map.get(w1).contains(w2)){
                return false;
            } 
        }
        return true;
    }
}

LeetCode [662] Maximum Width of Binary Tree

662. Maximum Width of Binary Tree

Medium

Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

It is guaranteed that the answer will in the range of 32-bit signed integer.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Constraints:

The given binary tree will have between 1 and 3000 nodes.

/**
 * 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 {
    Map<Integer, Integer> map = new HashMap<>();//level, left most
    int ret = 0;
    public int widthOfBinaryTree(TreeNode root) {
        helper(root, 0, 0);
        return ret;
    }
    
    void helper(TreeNode node, int level, int i){
        if(node==null) return;
        if(!map.containsKey(level)) map.put(level, i);
        int leftMost = map.get(level);
        ret = Math.max(ret, i-leftMost+1);
        helper(node.left, level+1, i*2);
        helper(node.right, level+1, i*2+1);
    }
}