Search

Zhiwen's study blog

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
 public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (!map.containsKey(num)) { map.put(num, 1); } else { map.put(num, map.get(num) + 1); } } List<Integer>[] bucket = new List[nums.length + 1]; for (int key : map.keySet()) { if (bucket[map.get(key)] == null) { bucket[map.get(key)] = new ArrayList<>(); } bucket[map.get(key)].add(key); } List<Integer> result = new ArrayList<>(); for (int i = bucket.length - 1; i >= 0; i--) { if (result.size() >= k) { return result; } if (bucket[i] != null) { result.addAll(bucket[i]); } } return result; } } 

208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

public class Trie {

    public class TrieNode {
        public char val;
        public boolean isWord;
        public TrieNode[] children = new TrieNode[26];
        public TrieNode () {};
        public TrieNode (char c) {
            TrieNode node = new TrieNode();
            node.val = c;
        }
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode(' ');
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode(c);
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) return false;
            node = node.children[c - 'a'];
        }
        return node.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i ++) {
            char c = prefix.charAt(i);
            if (node.children[c - 'a'] == null) return false;
            node = node.children[c - 'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

582. Kill Process

Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

Example 1:

Input: 
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation: 
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

Note:

  1. The given kill id is guaranteed to be one of the given PIDs.
  2. n >= 1.
Show Company Tags
Show Tags
public class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> result = new ArrayList<>();
        if (pid == null || ppid == null) return result;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < pid.size(); i++) {
            if (!map.containsKey(ppid.get(i))) {
                map.put(ppid.get(i), new LinkedList<>());
            }
            map.get(ppid.get(i)).add(pid.get(i));
        }
        Queue<Integer> q = new LinkedList<>();
        q.offer(kill);
        while (!q.isEmpty()) {
            int id = q.poll();
            result.add(id);
            if (map.containsKey(id)) q.addAll(map.get(id));
        }
        return result;
    }
}

463. Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:
public class Solution {
    
    private int result = 0;
    private final int[] dx = new int[]{-1,0,1,0};
    private final int[] dy = new int[]{0,1,0,-1};
    private boolean[][] visited;
    
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j, grid);
                }
                
            }
        }
        return result;
    }
    
    private void bfs(int x, int y, int[][] grid) {
        visited[x][y] = true;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] pos = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = pos[0] + dx[i];
                int ny = pos[1] + dy[i];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length) {
                    if (grid[nx][ny] == 1 && !visited[nx][ny]) {
                        q.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                    else if (grid[nx][ny] == 0) result++;
                } else {
                    result++;
                }
            }
        }
    }
}

// DFS
public class Solution {
    
    private int result = 0;
    private final int[] dx = new int[]{-1,0,1,0};
    private final int[] dy = new int[]{0,1,0,-1};
    private boolean[][] visited;
    
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    dfs(i, j, grid);
                    return result;
                }
                
            }
        }
        return result;
    }
    
    private void dfs(int x, int y, int[][] grid) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length) {
                if (grid[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    dfs(nx, ny, grid);
                } else if (grid[nx][ny] == 0) result++;
            } else result++;
        }
    }
}

210. Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

  1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.
public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // set to store courses, map to store in/outDegree
        Map<Integer, Set<Integer>> inDegree = new HashMap<>();
        Map<Integer, Set<Integer>> outDegree = new HashMap<>();
        // Init course
        for (int i = 0; i < numCourses; i++) {
            inDegree.put(i, new HashSet<>());
            outDegree.put(i, new HashSet<>());
        }
        // set in/outDegree
        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            inDegree.get(cur).add(pre);
            outDegree.get(pre).add(cur);
        }
        // queue to store nodes without indegree
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree.get(i).size() == 0) q.offer(i);
        }
        // add q.poll to result
        int[] result = new int[numCourses];
        int index = 0;
        while (!q.isEmpty()) {
            Integer course = q.poll();
            result[index++] = course;
            for (Integer next : outDegree.get(course)) {
                inDegree.get(next).remove(course);
                if (inDegree.get(next).size() == 0) q.offer(next);
            }
        }
        // return result
        if (index == numCourses) return result;
        else return new int[]{};
    }
}

207. Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> inDegree = new HashMap<>();
        Map<Integer, Set<Integer>> outDegree = new HashMap<>();
        Set<Integer> set = new HashSet<>();

        // Init courses
        for (int i = 0; i < numCourses; i++) {
            inDegree.put(i, new HashSet<>());
            outDegree.put(i, new HashSet<>());
            set.add(i);
        }

        // Parse course prerequisites
        for (int i = 0; i < prerequisites.length; i++) {
            int current = prerequisites[i][0];
            int pre = prerequisites[i][1];

            inDegree.get(current).add(pre);
            outDegree.get(pre).add(current);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (Integer course : set) {
            if (inDegree.get(course).size() == 0) {
                queue.add(course);
            }
        }

        int index = 0;
        int[] result = new int[set.size()];
        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            result[index++] = course;
            for (Integer next : outDegree.get(course)) {
                inDegree.get(next).remove(course);
                if (inDegree.get(next).size() == 0) {
                    queue.offer(next);
                }
            }
        }

        if (index != set.size()) {
            return false;
        } else {
            return true;
        }
    }
}

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private boolean result = false;
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        dfs(root, sum, 0);
        return result;
    }
    
    private void dfs(TreeNode root, int sum, int pathSum) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (pathSum + root.val == sum) {
                result = true;
                return;
            }
        }
        if (root.left != null) dfs(root.left, sum, pathSum + root.val);
        if (root.right != null) dfs(root.right, sum, pathSum + root.val);
    }
}

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int result = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 0);
        return result;
    }
    
    private void dfs(TreeNode root, int pathSum) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            result += pathSum * 10 + root.val;
            return;
        }
        if (root.left != null) {
            dfs(root.left, pathSum * 10 + root.val);
        }
        if (root.right != null) dfs(root.right, pathSum * 10 + root.val);
    } 
}

17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

public class Solution {
    private int[] num = new int[]{2,3,4,5,6,7,8,9};
    private String[] letter = new String[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    private HashMap<Integer, String> map = new HashMap<>();
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return result;
        for (int i = 0; i < num.length; i++) {
            map.put(num[i], letter[i]);
        }
        helper(digits, 0);
        return result;
    }
    
    private void helper(String s, int start) {
        if (start == s.length()) {
            result.add(sb.toString());
            return;
        }
        int digit = Integer.valueOf(s.charAt(start) - '0');
        String search = map.get(digit);
        for (int i = 0; i < search.length(); i++) {
            int len1 = sb.length();
            sb.append(search.charAt(i));
            int len2 = sb.length();
            helper(s, start + 1);
            sb.delete(len1, len2);
        }
    }
}

Create a free website or blog at WordPress.com.

Up ↑