299. Bulls and Cows

看上去比较简单但是其实很厉害的题，而且第一遍也没做对
感觉是一个变相的Two Pointers的题
重点是什么时候countB 满足条件
1.当secret扫过去的时候，如果map里面char是负的count，证明有多余的guess里面的char等待被match
2.当guess扫过去的时候，如果map里面char是正count，证明secret里已经有一些这个char了，可以直接match
所以i每扫一次有两次增加的机会

18.73 %
class Solution {
    public String getHint(String secret, String guess) {
        if (secret == null || guess == null || secret.length() != guess.length()) {
            return null;
        }
        int countA = 0; // both same
        int countB = 0;
        // key->num, value->count
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s == g) {
                countA++;
            } else {
                if (map.getOrDefault(s, 0) < 0) {
                    countB++;
                }
                map.put(s, 1 + map.getOrDefault(s, 0));
               
                if (map.getOrDefault(g, 0) > 0) {
                    countB++;
                }
                map.put(g, map.getOrDefault(g, 0) - 1);
            }
        }
        return countA + "A" + countB + "B";
    }
}

924. Minimize Malware Spread

Version #2 Brute Force DFS/BFS[TODO]

Version #1 Union Find
Trick part is if two initial ids belong to the same component, then remove either of them would be meaningless
So we need to make sure that our initial point is the only initial point in its component
We make a count of root(init) to see how many initial points are under this current root
And then if the size of this root is max, we record the id
1 edge case is that if we can't find any count[root(init)] == 1 -> means all initial points belong to one component -> in this scenario we need to return minimum id among all initial ids

97.32 %
class Solution {
    private int[] id;
private int[] size;
public int minMalwareSpread(int[][] graph, int[] initial) {
int N = graph.length;
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (graph[i][j] == 1) {
union(i, j);
}
}
}
int[] count = new int[N];
for (int init : initial) {
count[root(init)]++;
}
int resultCount = -1;
Integer resultId = null;
int minId = N;
for (int init : initial) {
minId = Math.min(minId, init);
int root = root(init);
if (count[root] == 1) {
if (size[root] >= resultCount) {
resultCount = size[root];
resultId = (resultId == null) ? init : Math.min(resultId, init);
}
}
}
return resultCount == -1 ? minId : resultId;
}
private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
}

803. Bricks Falling When Hit

写了好久
自己想不到
重点是倒着加点的时候，如果这个点不是connect to top, 就不进行count
因为不connect to top, 证明了这个点是之前的点remove的时候掉下去的！

Version #2 Union Find[TODO]

Version #1 DFS
79.69 %

class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0 || hits == null) {
return new int[0];
}
int rows = grid.length;
int cols = grid[0].length;
int[] result = new int[hits.length];
for (int[] hit : hits) {
if (grid[hit[0]][hit[1]] == 1) {
grid[hit[0]][hit[1]] = -1;
}
}
         
for (int x = 0; x < cols; x++) {
if (grid[0][x] == 1) {
dfs(0, x, grid);
}
}

for (int i = hits.length - 1; i >= 0; i--) {
int[] count = new int[1];
if (grid[hits[i][0]][hits[i][1]] == -1) {
                    grid[hits[i][0]][hits[i][1]] = 1;
                    if (connectedToTop(hits[i][0], hits[i][1], grid)) {
                        search(hits[i][0], hits[i][1], grid, count);
                    }
}
result[i] = count[0] == 0 ? 0 : (count[0] - 1);
}
return result;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
// mark all nodes connect to top as 2
private void dfs(int y, int x, int[][] grid) {
grid[y][x] = 2; // visited
for (int i = 0; i < 4; i++) {
int currX = x + dx[i];
int currY = y + dy[i];
if (currX >= 0 && currY >= 0 && currX < grid[0].length && currY < grid.length && grid[currY][currX] == 1) {
dfs(currY, currX, grid);
}
}
}

    /*
    0 2
    1 -1
    2 2
    3 -1
    4 -1
    */
 
    private boolean connectedToTop(int y, int x, int[][] grid) {
        if (y == 0) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
int currX = x + dx[i];
int currY = y + dy[i];
if (currX >= 0 && currY >= 0 && currX < grid[0].length && currY < grid.length
               && grid[currY][currX] == 2) {
                return true;
}
}
        return false;
    }
 
private void search(int y, int x, int[][] grid, int[] count) {
     
grid[y][x] = 2; // visited
count[0]++;
        for (int i = 0; i < 4; i++) {
int currX = x + dx[i];
int currY = y + dy[i];
if (currX >= 0 && currY >= 0 && currX < grid[0].length && currY < grid.length && grid[currY][currX] == 1) {
search(currY, currX, grid, count);
}
}
}
}

399. Evaluate Division

Version #2 DFS[TODO]


Version #1 Union Find
一开始写的时候感觉我靠怎么这么难，但是实际上用recursion的方法进行path compression 就非常容易
如果root() 用iteration的方法，每次指向grandpa, 路径缩短一半，没有办法保证最后的 ratio.get(a) 就是 rootA / a
这是这道题的关键
如果一开始就用 recursion的方法 取出root(father.get(a))
然后由  rootA / father = ratio.get(father) + father / id = ratio.get(id)
得到 rootA / id = ratio.get(father) * ratio.get(id)
就可以把id直接连在root上
这样保证了一切换算都是从root出发的
只要root一样，a / b 就一定是 a / b = root / b / (root / a) = ratio.get(b) / ratio.get(a)
不需要处理任何edge case，就很牛逼了

Input:[["a","b"],["e","f"],["b","e"]] [3.4,1.4,2.3] [["b","a"],["a","f"],["f","f"],["e","e"],["c","c"],["a","c"],["f","e"]]

Output:[0.29412,0.17903,1.0,1.0,-1.0,-1.0,43.68029]

Expected:[0.29412,10.948,1.0,1.0,-1.0,-1.0,0.71429]

75.23 %
class Solution {
    private Map<String, String> father;
// id, fatherValue/value
private Map<String, Double> ratio;

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
//   2.0
// a ---> b
father = new HashMap<>();
ratio = new HashMap<>();
for (int i = 0; i < equations.length; i++) {
String a = equations[i][0];
String b = equations[i][1];
union(a, b, values[i]);
}
double[] result = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
String a = queries[i][0];
String b = queries[i][1];
if (!father.containsKey(a) || !father.containsKey(b)) {
result[i] = -1.0;
continue;
}
String rootA = root(a);
String rootB = root(b);
if (!rootA.equals(rootB)) {
result[i] = -1.0;
} else {
// a / b = rootA / a
result[i] = ratio.get(b) / ratio.get(a);
}
}
return result;
}

// path compression needs to recalculate the ratio
// father
private String root(String id) {
if (!father.containsKey(id)) {
father.put(id, id);
ratio.put(id, 1.0);
}
if (father.get(id).equals(id)) {
            return id;
        }
        String parent = father.get(id);
        String root = root(parent);
        // ratio.get(parent) = root / parent, ratio.get(id) = parent / id
        // root / id = ratio.get(parent) * ratio.get(id)
        father.put(id, root);
        ratio.put(id, ratio.get(parent) * ratio.get(id));
return root;
}

// a / b = 2.0, b / c = 3.0.
// a / c = (a/b) * (b/c) = 6
private void union(String a, String b, Double weight) {
            String rootA = root(a);
            String rootB = root(b);
            double ratioA = ratio.get(a);
            double ratioB = ratio.get(b);
            if (rootA.equals(rootB)) {
                return;
            }
            // a / b = weight
            // rootA  = ratioA * a
            // rootB  = ratioB * b
            // rootA / rootB = ratioA * a / (ratioB * b) = ratioA / ratioB * (a / b) = ratioA / ratioB * weight
            father.put(rootB, rootA);
            ratio.put(rootB, ratioA / ratioB * weight);
}
}

936. Stamping The Sequence

[2ND TRY]
Version #3 Greedy without any reason

class Solution {
    private int matchedCount;
public int[] movesToStamp(String stamp, String target) {
char[] chars = target.toCharArray();
matchedCount = 0;
List<Integer> result =new LinkedList<>();
while(matchedCount != target.length()) {
if (!match(stamp, target, chars, result)) break;
}
return matchedCount == target.length() ? result.stream().mapToInt(a -> a).toArray() : new int[0];
}

private boolean match(String stamp, String target, char[] chars, List<Integer> result) {
for (int i = 0; i <= target.length() - stamp.length(); i++) {
int j = 0;
boolean canMatch = false;
for (j = 0; j < stamp.length(); j++) {
if (chars[i + j] == stamp.charAt(j)) {
canMatch = true;
} else if (chars[i + j] != '?') {
break;
}
}
if (canMatch && j == stamp.length()) {
for (j = 0; j < stamp.length(); j++) {
if (chars[i + j] != '?') {
chars[i + j] = '?';
matchedCount++;
}
}
result.add(0, i);
return true;
}
}
return false;
}
}


Version #2 TLE BFS
public int[] movesToStamp(String stamp, String target) {
String mask = "";
String result = "";
int stampLen = stamp.length();
for (int i = 0; i < stampLen; i++) mask += "?";
for (int i = 0; i < target.length(); i++) result += "?";
// key-string after stamped like ababc -> ab???, value-list of indexed where we have put stamps
Map<String, List<Integer>> map = new HashMap<>();
// string[0] places we can still put stamp, string[1] target
Queue<String> que =new LinkedList<>();
que.offer(target);
int step = 0;
while (!que.isEmpty()) {
step++;
if (step > 10) return new int[0];
int size = que.size();
while (size-- > 0) {
String curr = que.poll();
List<Integer> stamped = map.getOrDefault(curr, new ArrayList<>());
// ab???, [2]
for (int i = 0; i <= target.length() - stampLen; i++) {
if (stamped.contains(i)) continue; // skip if we have already stamped on this position
int j = 0;
boolean valid = false;
for (j = 0; j < stampLen; j++) {
if (stamp.charAt(j) == target.charAt(i + j)) {
valid = true; // this stamp contributes to our result
} else if (curr.charAt(i + j) != '?') {
break;
}
}
if (valid && j == stampLen) { // we can stamp here
String next = curr.substring(0, i) + mask + curr.substring(i + stampLen);
List<Integer> nextStamped = new LinkedList<>(stamped);
nextStamped.add(0, i);
if (next.equals(result)) return nextStamped.stream().mapToInt(a -> a).toArray();
if (!map.containsKey(next)) {
map.put(next, nextStamped);
que.offer(next);
}
}
}
}
}
return new int[0];
}


[1ST TRY]
一个非常有意思的题
怎么说，中心思想感觉上非常像topological sort
用一个stamp的start index来表示 distinct stamp
一开始默认为targe从0 一直到 targetLen - stampLen 都会有潜在的stamp可以盖章
我们希望当一个stamp落下的时候，它的所有character都和target是matched
所以当我们用 O(targetLen*stampLen)搜索整个target，找到所有character完全match的stamp，就可以把它们放入我们的done queue里面，代表这些位置是可以盖章的
那么盖章以后的效果是什么呢，就是使盖章的char完全满足target, 并且覆盖之前不满足的任何char

 stamp = "abca", target = "aabcaca"

//       stamp     a b c a
//       target      a a b c a c a     
//       matched     todo
        // 0 ->  0           1 2 3
        // 1 ->  1 2 3 4
        // 2 ->              2 3 4 5
        // 3 ->  3 4         5 6
        // use index i to represent where to put stamp
譬如当我们在 index=2盖章后，就完全使整个[index, index + stampLen) 满足条件
整个区域都可以在boolean[] visited 里面设为true
我们找哪些 stamp 的todo list里面有这些点，就可以把他们移除掉，因为后面的stamp 帮助他们完成了这些点
如果这些候选的stamp 的todo list 空了，有两种情况
重点！！！
1. 虽然它的todo list空了，但是它有些点是自己的matched点，也就是说需要盖下这个章才能满足
2.其他的stamp帮它完成了它的任务，在他的范围内所有char都已经盖完了，那么这个stamp就不需要盖章了
具体是1还是2，要在我们位于stamp的时候扫一遍它的范围，看看有没有visited[p] == false
如果有的话，要push到done里面去等待该站，如果没有就完全不用管了

while停止的条件是done的list全部pop完，也就是说该盖的章全都盖上
这里有个bug就是下面这种情况
最后能盖的章都盖完了，还有很多没有解决的点，证明没有可行解，要返回new int[0]

"mda"
"mdadddaaaa"

时间复杂度大约是 O(MN) 的量级

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        Deque<Integer> result = new ArrayDeque<>();
        int stampLen = stamp.length();
        int targetLen = target.length();
        Map<Integer, Set<Integer>> todo = new HashMap<>();
        Queue<Integer> done = new LinkedList<>();
        for (int i = 0; i <= targetLen - stampLen; i++) {
            Set<Integer> todoIndex = new HashSet<>();
            for (int j = 0; j < stampLen; j++) {
                if (stamp.charAt(j) != target.charAt(i + j)) {
                    todoIndex.add(i + j);
                }
            }
            if (todoIndex.isEmpty()) {
                done.offer(i);
            } else {
                todo.put(i, todoIndex);
            }
        }
        boolean[] visited = new boolean[targetLen];
        while (!done.isEmpty()) {
            // p + stampLen = i
            // p = i - stampLen + 1
            //  i   (i+stampLen)
         
            //     abca
            //    aabcaca
            int curr = done.poll();
            result.addFirst(curr);
            // System.out.println("curr -> "  + curr);
            for (int changedPos = curr; changedPos < curr + stampLen; changedPos++) {
                visited[changedPos] = true;
             
                // check all stamp that might contain changedPos
                for (int stampIndex = Math.max(0, curr - stampLen + 1); stampIndex < Math.min(curr + stampLen, targetLen); stampIndex++) {
                    Set<Integer> todoIndex = null;
                    if ((todoIndex = todo.get(stampIndex)) != null) {
                        if (todoIndex.contains(changedPos)) {
                            todoIndex.remove(changedPos);
                            if (todoIndex.size() == 0) {
                                todo.remove(stampIndex);
                                for (int p = 0; p < stampLen; p++) {
                                 
                                    if (!visited[stampIndex + p]) {
                                        done.offer(stampIndex);
                                        break;
                                    }
                                }
                            }
                        }
                    }
                 
                }
            }
        }
        for (boolean visit : visited) {
            if (!visit) {
                return new int[0];
            }
        }
        return result.stream().mapToInt(i -> i).toArray();
    }
}

934. Shortest Bridge

DFS + BFS
Time O(mn)
Space O(mn)

昨天contest的题目，没有做出来，原因是看错了题就觉得不会做就放弃了
今天仔细看了一下特别想抽自己
题目说有2个island, 找到flip的最少的点使两个island连在一起
昨天看成了有无数个island...
如果无数个island的话，从一个island出发BFS, reach到一个新island的时候记录步数，此时有可能相同的步数也reach到了其他的island，所以需要把当前层全部走完，找到所有当前层的1，作为接下来dfs的起点。。。

这道题本身就简单很多了，首先搜整个图找到第一个'1'点，进行DFS就找到了第一个island, 一边找一遍把找到的点都放到queue里面作为后面expand的基础
expand通过BFS的level traversal记录step数，如果找到了第一个没有检查过的'1'点，就是另外island的点，直接返回走到这个点用到的步数就好了

这道题的Time和Space要求都很严，必须在进入下一层之前进行valid检查，否则就会TLE或者MLE

class Solution {
    public int shortestBridge(int[][] A) {
        int rows = A.length;
        int cols = A[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> que = new LinkedList<>();
        boolean flag = false;
        for (int y = 0; y < rows; y++) {
            if (flag) {
                break;
            }
            for (int x = 0; x < cols && !flag; x++) {
                if (!visited[y][x] && A[y][x] == 1) {
                    dfs(A, y, x, visited, que);
                    flag = true;
                }
            }
        }
        // que contains all nodes that belong to current area
        int level = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] curr = que.poll();
                for (int i = 0; i < 4; i++) {
                    int currX = curr[1] + dx[i];
                    int currY = curr[0] + dy[i];
                    if (currX >= 0 && currX < A[0].length && currY >= 0 && currY < A.length && !visited[currY][currX]) {
                        if (A[currY][currX] == 1) {
                            return level;
                        } else {
                            visited[currY][currX] = true;
                            que.offer(new int[]{currY, currX});
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
    private int[] dx = new int[]{1, 0, -1, 0};
    private int[] dy = new int[]{0, -1, 0, 1};
    private void dfs(int[][] A, int y, int x, boolean[][] visited, Queue<int[]> que) {
        visited[y][x] = true;
        que.offer(new int[]{y, x});
        for (int i = 0; i < 4; i++) {
            int currX = x + dx[i];
            int currY = y + dy[i];
            if (currX >= 0 && currX < A[0].length && currY >= 0 && currY < A.length
               && A[currY][currX] == 1 && !visited[currY][currX]) {
                dfs(A, currY, currX, visited, que);
            }
        }
    }
}

336. Palindrome Pairs

Version #2 Trie[TODO]


Version #1 HashMap of reversed word

1. abcd v.s. dcba
if we cut abcd by either ("", "abcd") or ("abce", "") we'll find a mapped "abcd(reversed dcba)" in hash map -> we add 2 result (0, 1) & (1, 0)
And when dcba comes, we also add (1, 0) and (0, 1)
In case of this kind of duplicate, I wanted to stop cutting when left | right -> right.length() at least 1
So we'll only have ""|"abcd" for (1, 0) and ""|"dcba" for (0, 1)
However we have edge case 2 ->
2. "a" ,""
When "a" came, we have ""|"a" and have matched "" in map
When "" came, we only allow k < word.length() so "" will never be cutted
That's a bug

This answer handles this in a very smart way-> we still try to cut from 0 to left.lengh()
if right.length() == 0, we don't add
So it satisfies the 1st edge case
For the 2nd edge case -> we still have "a"|"" which is (0, 1) for "a", ""|"a" (1, 0) for "a"
Now when "" came, we have ""|"" it will never be added
Time O(N k^2) k is the average length of words

17.46 %
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> result = new ArrayList<>();
if (words == null) {
return result;
}
// key -> reversed word, value -> index of the original word
Map<String, Integer> reversedWords = new HashMap<>();
for (int i = 0; i < words.length; i++) {
reversedWords.put(new StringBuilder(words[i]).reverse().toString(), i);
}

for (int i = 0; i < words.length; i++) {
String word = words[i];
// partition word into left | right
// left | right | candidate or  candidate | left | right
for (int k = 0; k <= word.length(); k++) {
String left = word.substring(0, k);
String right = word.substring(k, word.length());
int j;
if (reversedWords.containsKey(left) && (j = reversedWords.get(left)) != i && isPalindrome(right)) {
result.add(Arrays.asList(i, j));
}
if (reversedWords.containsKey(right) && left.length() != 0 && (j = reversedWords.get(right)) != i && isPalindrome(left)) {
result.add(Arrays.asList(reversedWords.get(right), i));
}
}
}
return result;
}
private boolean isPalindrome(String word) {
int len = word.length();
int i = 0;
while (i < len / 2) {
if (word.charAt(i) != word.charAt(len - i - 1)) {
return false;
}
i++;
}
return true;
}
}