fresh grad 刷题+补习知识打卡贴

5/17 Thur
google tag
686. Repeated String Match
StringBuilder
int         indexOf(String str)
Returns the index within this string of the first occurrence of the specified substring
459. Repeated Substring Pattern, use StringBuilder
406. Queue Reconstruction by Height, greedy
Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value.
For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth.

769. Max Chunks To Make Sorted 代码很简单，思路咋就想不到呢。。
keep track of the max value until the current position, and compare it to the sorted array, i.e. current index. If the max equals index i, then the final count++.
768. Max Chunks To Make Sorted II
Iterate through the array, each time all elements to the left are smaller (or equal) to all elements to the right, there is a new chuck
when you are at index i, compare max(0,..., i) with min (i + 1, ..., n-1)
这道题居然是我两个月前做的一个oa。。
763. Partition Labels, similar to 769
1)  traverse the string record the last index of each char.
2) traverse the string again. if last index of all previous chars and current char is current index i, then it is a new partition

246. Strobogrammatic Number, HashMap
247. Strobogrammatic Number II, recursion
base case n = 0, 1; recursion: start and end + char. last recursion do not add "0"
248. Strobogrammatic Number III, II改改???

5/19 Sat
498. Diagonal Traverse, find pattern
836. Rectangle Overlap, similar idea to interval overlap
(729: Math.max(interval[0], start) < Math.min(interval[1], end) means this is an overlap!!!!!!)
838. Push Dominoes
traverse through the char array. seeing a '.', do not change
think about R/L ... R/L. seeing a R/L, change previous dots
839. Similar String Groups, DFS
starting from a string, change it to null and do dfs on it

5/21 Mon
玩了好几天。。。该学习了
127. Word Ladder
1) BFS
convert List of wordList into HashSet. search would be O(1)
Do regular BFS with a Queue
each time we found transformed word in the wordList, we delete the word from the set to avoid search again
2) bidirection BFS
use two HashSet to maintain the words generated from start and end
use a temp HashSet to store the words generated for current level

楼主之前一个帖子不还在亚马逊干了一年吗，难道是共用一个号？

5/22 Tue
433. Minimum Genetic Mutation, Similar to 127
36. Valid Sudoku, HashSet
int rowIdx = 3 (i / 3), colIdx = 3 (i % 3); indices for each grid start point
board[rowIdx + j / 3][colIdx + j % 3] to traverse the 3*3 grid
37. Sudoku Solver, Backtracking
for every empty cell, try from 1 to 9 and check if it would be valid and do DFS from this point
board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] to traverse the 3*3 grid
这两题3*3的traverse自己想不到...
286. Walls and Gates, BFS
每次只需要改infi的cell，因为BFS保证第一次改infi都是最近的
417. Pacific Atlantic Water Flow, BFS
Two Queue and add all the Pacific border to one queue; Atlantic border to another queue. Keep a visited matrix for each queue. In the end, add the cell visited by two queue to the result.
BFS: Water flood from ocean to the cell. Since water can only flow from high/equal cell to low cell, add the neighboor cell with height larger or equal to current cell to the queue and mark as visited.
139. Word Break, DP

5/23 Wed
130. Surrounded Regions, BFS
First, check the four borders of the matrix. If there is an element 'O', change it and all its neighbor 'O' elements to ''. Then change all 'O' to 'X' and all '' to 'O'.
317. Shortest Distance from All Buildings, BFS
BFS from every building, calculate the distances and find the minimum distance in the end.
We do not go into a cell if it is not accessible by at least one of previous buildings.
529. Minesweeper, BFS, DFS
1.        If click on a mine ('M'), mark it as 'X', stop further search.
2.        If click on an empty cell ('E'), depends on how many surrounding mine:
2.1 Has surrounding mine(s), mark it with number of surrounding mine(s), stop further search.
2.2 No surrounding mine, mark it as 'B', continue search its 8 neighbors.
490. The Maze, BFS
different that usual search, move forward until hit wall or boundary

5/24 Thur
815. Bus Routes, BFS
HashMap, where bus stop number is the key and all the buses (bus routes) that go through it are added to an ArrayList. To avoid loops, we also maintain a HashSet that stores the bus stops that we have already visited. Also mark the bus route as null after visited to avoid searching again.
733. Flood Fill, BFS, DFS
463. Island Perimeter, Not using BFS or DFS here
There is exactly one island, so all 1's are connected
1) loop over the matrix and count the number of islands;
2) if the current dot is an island, count if it has any right neighbor or down neighbor;
3) the result is islands 4 - neighbors* 2
695. Max Area of Island, DFS
734. Sentence Similarity, HashMap

5/26 Sat
737. Sentence Similarity II, HashMap, Union Find
840. Magic Squares In Grid
841. Keys and Rooms, BFS

5/28 Mon
843. Guess the Word, Minimax
making the guess that minimizes the maximum possible size of the resulting word list. If we started with all the words in our word list, we can iterate through all possibilities for what the secret could be.

5/29 Tue
505. The Maze II, Dijkstra Algorithm, PriorityQueue

5/30 Wed
743. Network Delay Time, Dijkstra Algorithm
int[][] edges = new int[N + 1][N + 1]; // store the time between the directred edges
int[] res = new int[N + 1]; // store the time from node K to each node
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> res[a] - res[b]);
752. Open the Lock, BFS and Bidirection BFS (similar to 127. Word Ladder)
https://www.geeksforgeeks.org/bidirectional-search/

785. Is Graph Bipartite?, DFS, two coloring
802. Find Eventual Safe States, DFS, use coloring

491. Increasing Subsequences, backtracking
similar to 90. Subsets II
can use set to avoid adding duplicate results

5/31 Thur
531. Lonely Pixel I
traverse the matrix twice. first time, count # of B for each row and col
694. Number of Distinct Islands, DFS and HashSet to record the String of directions
721. Accounts Merge, Union Find and TreeSet to get sorted
Map<String, String> owners = new HashMap<>();// key: email, val: owner
Map<String, String> parents = new HashMap<>();// key: email, val: parent of the email(same owner)
Map<String, TreeSet<String>> unions = new HashMap<>();//key: parent email, val: all associated emails and itself

6/1 Fri
200. Number of Islands (VERY CLASSIC)
recursive/iterative DFS, BFS, Union Find
305. Number of Islands II, Union find
323. Number of Connected Components in an Undirected Graph, Union Find

6/3 Sun
547. Friend Circles, Union Find, DFS (similar to 323)
684. Redundant Connection, Union Find
union the two vertices of an edge if they are not in the same group. otherwise return the edge
685. Redundant Connection II, Union Find
737. Sentence Similarity II, Union Find
use HashMap to do union and find; val: key's parent
261. Graph Valid Tree, Union Find
tree must be connected and acyclic

Union Find TEMPLATE
public boolean validTree(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int x = find(parent, e[0]);
            int y = find(parent, e[1]);
            if (x != y) {
                parent[x] = y;
                n--;
            } else return false; // cycle
        }
        return n == 1; // connected
    }
   
    public int find(int[] parent, int i) {
        while (parent[i] != i) {
            parent[i] = parent[parent[i]];
            i = parent[i];
        }
        return i;
    }
一般可以用array来做，偶尔用到HashMap

844. Backspace String Compare, Stack
845. Longest Mountain in Array
846. Hand of Straights, TreeMap