发表于 | 分类于

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

1
2
3
4
5
6
7
8
9
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6

解法1： Recursion

观察可以发现，对于[1,2,3,4,5,6,7,8,9] 这个数组，第一遍从左到右去掉之后得到的是[2,4,6,8],这个时候需要从右往左。
那么她的结果也就是可以看成是两倍的right(1,2,3,4)。
同理，这个(1,2,3,4)又可以看成是从左到右的(1,2),不过这里要区分一下奇数和偶数的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lastRemaining(int n) {
        return left2Right(n);
    }
    private int left2Right(int n) {
        if (n <= 2) return n;
        return 2 * right2Left(n / 2);
    }
    private int right2Left(int n) {
        if (n <= 2) return 1;
        // differentiate between odd and even cases
        if (n % 2 == 1) {
            return 2 * left2Right(n / 2);
        } else {
            return 2 * left2Right(n / 2) - 1;
        }
    }
}

解法2： Iteration TLE

也可以用约瑟夫环的类似的解法取去模拟删除的过程。不过大数据的时候就TLE了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int lastRemaining(int n) {
        if (n <= 2) return n;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        ListIterator<Integer> iterator = list.listIterator();
        boolean left2Right = true;
        iterator.next();    // starting from the starting point
        while (list.size() > 1) {
            iterator.remove();
            if (left2Right) {
                if (iterator.hasNext()) {
                    iterator.next();
                    if (iterator.hasNext()) {
                        iterator.next();
                    } else {
                        left2Right = false;
                        iterator.previous();
                    }
                } else {
                    left2Right = false;
                    iterator.previous();
                }
            } else {
                if (iterator.hasPrevious()) {
                    iterator.previous();
                    if (iterator.hasPrevious()) {
                        iterator.previous();
                    } else {
                        left2Right = true;
                        iterator.next();
                    }
                } else {
                    left2Right = true;
                    iterator.next();
                }
            }
        }
        return list.get(0);
    }
}

发表于 | 分类于

Suppose we abstract our file system by a string in the following manner:

The string “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext” represents:

1
2
3
4
dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext” represents:

1
2
3
4
5
6
7
dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is “dir/subdir2/subsubdir2/file2.ext”, and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.

Note:
The name of a file contains at least a . and an extension.
The name of a directory or sub-directory will not contain a ..
Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

解法1： HashMap

基本的思路是先把string按照\n分割，然后按照题意，对于每一个子字符串，他的\t的数量就代表他的层数。
这样的话可以从左往右扫描一遍，遇到一个新的level就存下当前的路径长度，不过如果当前是文件的话则从map中读取当前的level长度然后加上文件名长度就可以了。
每次存level的时候实际可以存上真实level+1，代表的是如果下一个文件的level是x，那么直接从map中读取x就是对应的path长度。
初始化的时候要放入map.put(0,0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthLongestPath(String input) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();    // record the length at each level
        map.put(0, 0);
        for (String element : input.split("\n")) {
            int level = element.lastIndexOf("\t") + 1;
            element = element.substring(level);
            if (element.contains(".")) {
                res = Math.max(res, map.get(level) + element.length());
            } else {
                map.put(level + 1, map.get(level) + element.length() + 1);
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].
Example 1:

1
2
3
Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:

1
2
3
4
5
6
7
8
9
Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

解法1： Stack O(N)

用一个stack来存储每一个当前的nestedInteger。
用一个variable存储指针使得他指向当前要parse的数字的开始位置。
每次看到一个,或者是]的时候就表示当前的nestedInteger结束了，所以需要把当前的数字放入nestedInteger。如果是]，如果当前的stack不为空，那么就说明这个integer属于另一个integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        if (s == null || s.length() == 0) {
            return new NestedInteger();
        }
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        Stack<NestedInteger> stack = new Stack<>();
        int start = 1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) =='[') {
                // start of a new NestedInteger
                stack.push(new NestedInteger());
                start = i + 1;
            } else if (s.charAt(i) == ',' || s.charAt(i) == ']') {
                if (start < i) {
                    NestedInteger top = stack.peek();
                    top.add(new NestedInteger(Integer.parseInt(s.substring(start, i))));
                }
                start = i + 1;
                if (s.charAt(i) == ']') {
                    if (stack.size() > 1) {
                        NestedInteger child = stack.pop();    
                        NestedInteger parent = stack.peek();
                        parent.add(child);
                    }
                }
            }
        }
        return stack.pop();
    }
}

发表于 | 分类于

解法1： O(N), Fisher-Yates Algorithm

参看这个geeksforgeeks的文章

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    int[] data = null;
    int[] backup = null;
    Random random;
    public Solution(int[] nums) {
        data = nums;
        backup = Arrays.copyOf(data, data.length);
        random = new Random(System.currentTimeMillis());
    }
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        data = Arrays.copyOf(backup, backup.length);
        return data;
    }
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for (int i = data.length - 1; i > 0; i--) {
            int pick = random.nextInt(i + 1);
            swap(i, pick);
        }
        return data;
    }
    private void swap(int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

发表于 | 分类于

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

1
2
3
4
5
6
7
8
// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

解法1： Reservoir Sampling

是reservoir sampling的直接应用。从discussion上看来的比较好懂的解释：

1
2
3
4
5
6
7
8
Start...
When we read the first node head, if the stream ListNode stops here, we can just return the head.val. The possibility is 1/1.
When we read the second node, we can decide if we replace the result r or not. The possibility is 1/2. So we just generate a random number between 0 and 1, and check if it is equal to 1. If it is 1, replace r as the value of the current node, otherwise we don't touch r, so its value is still the value of head.
When we read the third node, now the result r is one of value in the head or second node. We just decide if we replace the value of r as the value of current node(third node). The possibility of replacing it is 1/3, namely the possibility of we don't touch r is 2/3. So we just generate a random number between 0 ~ 2, and if the result is 2 we replace r.
We can continue to do like this until the end of stream ListNode.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    ListNode head = null;
    Random random = null;
    public Solution(ListNode head) {
        this.head = head;
        random = new Random(System.currentTimeMillis());
    }
    /** Returns a random node's value. */
    public int getRandom() {
        // k = 1
        int res = head.val;
        ListNode ptr = head.next;
        for (int i = 1; ptr != null; i++) {
            if (random.nextInt(i + 1) == i) {
                res = ptr.val;
            }
            ptr = ptr.next;
        }
        return res;
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

发表于 | 分类于

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

1
2
3
4
a = 2
b = [3]
Result: 8

Example2:

1
2
3
4
a = 2
b = [1,0]
Result: 1024

解法1： 二分分割

参考了这篇解答1,主要的思想还是做二分分割。用到的性质是

1
(ab)%x = (a%x)*(b%x) % x

然后判断下是否是偶数或者奇数。这里需要记忆一个高精度除法的计算方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public static int DIV = 1337;
    public void divide(int[] b, int divisor) {
        int temp = 0;
        for (int i = 0; i < b.length; i++) {
            b[i] += temp * 10;
            temp = b[i] % divisor;
            b[i] /= divisor;
        }
    }
    public boolean isZero(int[] b) {
        for (int i = 0; i < b.length; i++) {
            if (b[i] != 0) {
                return false;
            }
        }
        return true;
    }
    public int superPow(int a, int[] b) {
        if (isZero(b)) {
            return 1;
        }
        a %= Solution.DIV;  // take a % first
        boolean isEven = false;
        if (b[b.length - 1] % 2 == 0) {
            isEven = true;
        }
        divide(b, 2);
        int sub = superPow(a, b);
        sub %= Solution.DIV;
        sub *= sub;
        sub %= Solution.DIV;
        if (!isEven) {
            sub *= a;
            sub %= Solution.DIV;
        }
        return sub;
    }
}

发表于 | 分类于

Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0,0) with length = 1 unit.

You are given a list of food’s positions in row-column order. When a snake eats the food, its length and the game’s score both increase by 1.

Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.

When a food does appear on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Given width = 3, height = 2, and food = [[1,2],[0,1]].
Snake snake = new Snake(width, height, food);
Initially the snake appears at position (0,0) and the food at (1,2).
|S| | |
| | |F|
snake.move("R"); -> Returns 0
| |S| |
| | |F|
snake.move("D"); -> Returns 0
| | | |
| |S|F|
snake.move("R"); -> Returns 1 (Snake eats the first food and right after that, the second food appears at (0,1) )
| |F| |
| |S|S|
snake.move("U"); -> Returns 1
| |F|S|
| | |S|
snake.move("L"); -> Returns 2 (Snake eats the second food)
| |S|S|
| | |S|
snake.move("U"); -> Returns -1 (Game over because snake collides with border)

解法1： Deque + HashMap

设计题在于选用合适的数据结构来完成要求的feature。
用一个hashmap存每一个snake的位置是便于查询是否头咬到了身体
用deque来表示一个snake，方便从头从尾巴更新。
每次移动的时候先要把tail移除，然后判断是否溢出，是否咬到了身体。
然后再判断是否吃到了果实，如果是那么再把tail给放回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class SnakeGame {
    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    Deque<Integer> snake;
    Set<Integer> snakeBody;
    int width;
    int height;
    int[][] food;
    int score;
    int foodIndex;
    public SnakeGame(int width, int height, int[][] food) {
        this.snake = new LinkedList<Integer>();
        this.snakeBody = new HashSet<>();
        this.width = width;
        this.height = height;
        this.food = food;
        this.score = 0;
        this.foodIndex = 0;
        snake.offerFirst(0);
        snakeBody.add(0);
    }
    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
        @return The game's score after the move. Return -1 if game over.
        Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        if (score == -1) {
            return score;
        }
        int head = snake.peekFirst();
        int row = head / width;
        int col = head % width;
        switch (direction) {
            case "U":
                row--;
                break;
            case "D":
                row++;
                break;
            case "L":
                col--;
                break;
            case "R":
                col++;
                break;
        }
        // remove tail from snake
        int tail = snake.peekLast();
        snake.removeLast();
        snakeBody.remove(tail);
        // check if snake is out of boundary
        if (row < 0 || row >= height || col < 0 || col >= width) {
            score = -1;
            return score;
        }
        int newHead = row * width + col;
        if (snakeBody.contains(newHead)) {
            score = -1;
            return score;
        }
        // check if the tail needs to be added back
        if (foodIndex < food.length) {
            int[] currentFood = food[foodIndex];
            if (row == currentFood[0] && col == currentFood[1]) {
                snake.offerLast(tail);
                snakeBody.add(tail);
                foodIndex++;
                score++;
            }            
        }
        // add new head into snake
        snake.offerFirst(newHead);
        snakeBody.add(newHead);
        return score;
    }
}
/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

发表于 | 分类于

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

1
2
3
4
5
6
7
8
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

1
2
3
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

解法1： Two DP process

这一系列题的推广解法非常的简洁也非常的好懂。这是一种互为影响的dp系列。一般用两个dp array解决。
一个array代表在时间i不持有股票的最大值，另一个代表在时间i持有股票的最大值。
那么可以得到这样的关系
withStock[i] = Math.max(withStock[i - 1], withoutStock[i - 1] - price)
这里表示在时间i如果买了股票的话资金池就需要减掉price
withoutStock[i] = Math.max(withoutStock[i - 1], withStock[i - 1] + price)
这里只是加入了fee，那么我们可以把它放在sell的时候或者是buy的时候就可以了。
最后最大的值一定是withoutStock[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        long tik0 = 0, tik1 = Integer.MIN_VALUE;
        for (int price : prices) {
            long tik0_old = tik0;
            tik0 = Math.max(tik0, tik1 + price - fee);
            tik1 = Math.max(tik1, tik0_old - price);
        }
        return (int)tik0;
    }
}

发表于 | 分类于

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
    1
   / \
  0   2
  L = 1
  R = 2
Output:
    1
      \
       2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input:
    3
   / \
  0   4
   \
    2
   /
  1
  L = 1
  R = 3
Output:
      3
     /
   2   
  /

解法1： Recursion

应用BST的性质，如果当前是一个leaf并且不在[L,R]范围内，那么就返回null。
如果不是leaf并且leaf的value在范围内，那么就对左右子树各trim
如果不是leaf而不在范围内，那么就either对左子数或者右子数trim就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.left == null && root.right == null) {
            if (root.val >= L && root.val <= R) {
                return root;
            } else {
                return null;
            }
        }
        int val = root.val;
        if (val >= L && val <= R) {
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
            return root;
        } else if (val < L) {
            return trimBST(root.right, L, R);
        } else {
            // val > R
            return trimBST(root.left, L, R);            
        }
    }
}

发表于 | 分类于

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

1
2
3
4
5
6
7
Input:
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

Example 2:

1
2
3
4
5
6
7
Input:
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.

解法1： DFS

这里因为已经有一个矩阵代表了graph连接的情况，所以我们不需要另外建图了。
对于每一个node，dfs一下把所有连通的地方都设为visited。
在外面循环的时候，每次看到一个没有被visited过得就是一个新的group

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0] == null || M[0].length == 0) {
            return 0;
        }
        int n = M.length;
        boolean[] visited = new boolean[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                res++;
                dfs(M, visited, i);
            }
        }
        return res;
    }
    private void dfs(int[][] M, boolean[] visited, int id) {
        visited[id] = true;
        for (int i = 0; i < M.length; i++) {
            if (visited[i] || M[i][id] == 0) continue;
            dfs(M, visited, i);
        }
    }
}

解法2: Union Find

比较典型的Union Find解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0] == null || M[0].length == 0) {
            return 0;
        }
        int n = M.length;
        int[] roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        // loop through M to union
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1 ; j < n; j++) {
                if (M[i][j] == 1) {
                    int root_left = find(roots, i);
                    int root_right = find(roots, j);
                    roots[root_right] = root_left;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (roots[i] == i) {
                res++;
            }
        }
        return res;
    }
    private int find(int[] nums, int i) {
        while (i != nums[i]) {
            i = nums[nums[i]];
        }
        return i;
    }
}