LC128 Longest Consecutive Sequence

Problem

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Think

首先将所有的num存进hash set，然后找到每一个连续序列的开头元素（即num - 1不存在的情况），向后判断每一个num + i是否存在，求得此处的最大长度。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int longestConsecutive(vector<int>& nums) {
    unordered_set<int> map;
    for(int num: nums) map.insert(num);
    int res = 0;
    for(int num: nums){
        if(!map.count(num - 1)){
            int len = 1, start = num + 1;
            while(start != INT_MAX && map.count(start++)){
                len++;
            }
            res = max(res, len);
        }
    }
    return res;
}

LC399 Evaluate Division

Problem

‘[[“a”,“c”],[“b”,“a”],[“a”,“e”],[“a”,“a”],[“x”,“x”]]’

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

1
2
3
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Think

并查集，首先实现两个函数，一个是getParent，用来获取某一个节点的最根部的父节点；另一个是unionNodes，用来合并两个节点，也就是将node1以及所有和node1共parent的节点合并到node2的分支上面，用对应的结果val进行连接。

对于每一个给出的公式，我们首先判断前后两个变量是否出现过：

  • 如果都没有出现过，则均需要新建，node1作为被除数，设值为val，node2作为除数，设值为1，然后将node1连接到node2上；
  • 如果被除数没出现过，除数出现过，则新建被除数，设置被除数的值为除数对应节点的值乘val；
  • 如果被除数出现过，除数没出现过，则新建除数，设置除数的值为被除数除以val；
  • 如果两者都出现过，则使用unionNodes将两个节点连起来。

对于每一个query，首先判断除数和被除数是否为已知变量，且具有相同的最根父节点（说明可以除），如果不满足条件返回-1，否则返回被除数的值除以除数的值。

Code 
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
struct Node {
    double value = 0.0;
    Node *parent;
    Node() { parent = this; }
};
void UnionNodes(Node *node1, Node *node2, double val, unordered_map<string, Node*>& map){
    Node *parent1 = getParent(node1), *parent2 = getParent(node2);
    double ratio = node2->value * val / node1->value;
    for(auto it = map.begin(); it != map.end(); it++){
        if(getParent(it->second) == parent1){
            it->second->value *= ratio;
        }
    }
    parent1->parent = parent2;
}

Node* getParent(Node* node){
    if(node->parent == node) return node;
    node->parent = getParent(node->parent);
    return node->parent;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    unordered_map<string, Node*> map;
    vector<double> res;
    for(int i = 0; i < equations.size(); i++){
        string s1 = equations[i][0], s2 = equations[i][1];
        double val = values[i];
        if(!map.count(s1) && !map.count(s2)){
            map[s1] = new Node();
            map[s2] = new Node();
            map[s1]->value = val;
            map[s2]->value = 1;
            map[s1]->parent = map[s2];
        }
        else if(!map.count(s2)){
            map[s2] = new Node();
            map[s2]->value = map[s1]->value / val;
            map[s2]->parent = map[s1];
        }
        else if(!map.count(s1)){
            map[s1] = new Node();
            map[s1]->value = map[s2]->value * val;
            map[s1]->parent = map[s2];
        }
        else{
            UnionNodes(map[s1], map[s2], val, map);
        }
    }

    for(auto q: queries){
        if(!map.count(q[0]) || !map.count(q[1]) || getParent(map[q[0]]) != getParent(map[q[1]])) res.push_back(-1);
        else res.push_back(map[q[0]]->value / map[q[1]]->value);
    }

    return res;
}

LC547 Friend Circles

Problem

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 directfriend 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:

  1. N is in range [1,200].
  2. M[i][i] = 1 for all students.
  3. If M[i][j] = 1, then M[j][i] = 1.
Think

并查集。主要实现两个部分，一是getRoot，二是对于两个节点应当如何合并。

Code 
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
int getRoot(vector<int> &root, int i){
    while(i != root[i]){
        root[i] = root[root[i]];
        i = root[i];
    }
    return root[i];
}
int findCircleNum(vector<vector<int>>& M) {
    int n = M.size();
    vector<int> root(n);
    int res = n;
    for(int i = 0; i < n; i++) root[i] = i;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(M[i][j] == 1){
                int r1 = getRoot(root, i);
                int r2 = getRoot(root, j);
                if(r1 != r2){
                    res--;
                    root[r2] = r1;
                }
            }
        }
    }
    return res;
}

LC684 Redundant Connection

Problem

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

1
2
3
4
5
6
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3

Example 2:

1
2
3
4
5
6
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3

Note:

The size of the input 2D-array will be between 3 and 1000.

Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Think

并查集，主要实现的就是并查集的两个函数。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    vector<int> root(2001, -1);
    for(auto edge: edges){
        int x = getRoot(root, edge[0]), y = getRoot(root, edge[1]);
        if(x == y) return edge;
        root[x] = y;
    }
    return {};
}

int getRoot(vector<int>& root, int i){
    while(root[i] != -1){
        i = root[i];
    }
    return i;
}

LC685 Redundant Connection II

Problem

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

1
2
3
4
5
6
7
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
  1
 / \
v   v
2-->3

Example 2:

1
2
3
4
5
6
7
Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

Note:

The size of the input 2D-array will be between 3 and 1000.

Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Think

getRoot函数和上题类似。

主要分三种情况：

  • 无环，但是有入度为2的节点，返回的是后加入的那一条边
  • 有环，且没有入度为2的节点，返回的是最后组成环的那一条边
  • 有环，且有入度为2的节点，返回的是组成环，且是加入入度为2的边的后一条边

因此需要用first和second来记录前后遍历到的两条边，如果当前边对应有root，则说明之前已经有入度为1了，所以需要记录first和second，然后将edge的出节点置为-1.

Code 
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
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    vector<int> root(n + 1, -1), first, second;
    for(auto &edge: edges){
        if(root[edge[1]] == -1){
            root[edge[1]] = edge[0];
        }
        else{
            first = {root[edge[1]], edge[1]};
            second = edge;
            edge[1] = -1;
        }
    }

    for(int i = 0; i <= n; i++) root[i] = i;

    for(auto &edge: edges){
        if(edge[1] == -1) continue;
        int x = getRoot(root, edge[0]), y = getRoot(root, edge[1]);
        if(x == y) return first.empty() ? edge: first;
        root[x] = y;
    }
    return second;
    
}

int getRoot(vector<int>& root, int i){
    while(root[i] != i){
        root[i] = root[root[i]];
        i = root[i];
    }
    return i;
}

LC721 Accounts Merge

Problem

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

1
2
3
4
5
6
7
8
Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation: 
The first and third John's are the same person as they have the common email "johnsmith@mail.com".
The second John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Note:

The length of accounts will be in the range [1, 1000].

The length of accounts[i] will be in the range [1, 10].

The length of accounts[i][j] will be in the range [1, 30].

Think

并查集，首先建立hash map存放root，建立hash map存放每个email对应的name，建立hash表存放所有email对应的序列结果。

首先遍历accounts，构建root和owner数组；

然后遍历accounts，将每一个email连接到对应的root的根节点上；

然后遍历account，将相同root的email存在hash map的相同区域的set里面；

最后将结果的hash map转化成二维数组。

Code 
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
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, string> root;
    unordered_map<string, string> owner;
    unordered_map<string, set<string>> m;
    vector<vector<string>> res;
    for(auto account: accounts){
        for(int i = 1; i < account.size(); i++){
            root[account[i]] = account[i];
            owner[account[i]] = account[0];
        }
    }

    for(auto account: accounts){
        string p = getRoot(root, account[1]);
        for(int i = 2; i < account.size(); i++){
            root[getRoot(root, account[i])] = p;
        }
    }

    for(auto account: accounts){
        for(int i = 1; i < account.size(); i++){
            m[getRoot(root, account[i])].insert(account[i]);
        }
    }

    for(auto a: m){
        vector<string> v(a.second.begin(), a.second.end());
        v.insert(v.begin(), owner[a.first]);
        res.push_back(v);
    }
    
    return res;
}
string getRoot(unordered_map<string, string> &map, string email){
    return map[email] == email ? email : getRoot(map, map[email]);
}

LC794 Valid Tic-Tac-Toe State

Problem

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty square.

Here are the rules of Tic-Tac-Toe:

  • Players take turns placing characters into empty squares (" ").
  • The first player always places “X” characters, while the second player always places “O” characters.
  • “X” and “O” characters are always placed into empty squares, never filled ones.
  • The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty.
  • No more moves can be played if the game is over.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Example 1:
Input: board = ["O  ", "   ", "   "]
Output: false
Explanation: The first player always plays "X".

Example 2:
Input: board = ["XOX", " X ", "   "]
Output: false
Explanation: Players take turns making moves.

Example 3:
Input: board = ["XXX", "   ", "OOO"]
Output: false

Example 4:
Input: board = ["XOX", "O O", "XOX"]
Output: true

Note:

  • board is a length-3 array of strings, where each string board[i] has length 3.
  • Each board[i][j] is a character in the set {" ", "X", "O"}.
Think

直接检查即可。

Code 
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
bool validTicTacToe(vector<string>& board) {
    int xCnt = 0, oCnt = 0;
    for(string s: board){
        for(char c: s){
            if(c == 'X') xCnt++;
            else if(c == 'O') oCnt++;
        }
    }
    if(!( (xCnt == oCnt) || (xCnt == oCnt + 1) ) ) return false;
    bool flag1 = check(board, 'X');
    bool flag2 = check(board, 'O');
    if(!flag1 && !flag2) return true;
    if(flag1) return xCnt == oCnt + 1;
    if(flag2) return xCnt == oCnt;
    return false;
}

bool check(vector<string>& board, char c){
    bool flag1 = (board[0][0] == c) && (board[0][1] == c) && (board[0][2] == c);
    bool flag2 = (board[1][0] == c) && (board[1][1] == c) && (board[1][2] == c);
    bool flag3 = (board[2][0] == c) && (board[2][1] == c) && (board[2][2] == c);

    bool flag4 = (board[0][0] == c) && (board[1][0] == c) && (board[2][0] == c);
    bool flag5 = (board[0][1] == c) && (board[1][1] == c) && (board[2][1] == c);
    bool flag6 = (board[0][2] == c) && (board[1][2] == c) && (board[2][2] == c);

    bool flag7 = (board[0][0] == c) && (board[1][1] == c) && (board[2][2] == c);
    bool flag8 = (board[2][0] == c) && (board[1][1] == c) && (board[0][2] == c);

    return flag1 || flag2 || flag3 || flag4 || flag5 || flag6 || flag7 || flag8;
}

LC821 Shortest Distance to a Character

Problem

Given a string S and a character C, return an array of integers representing the shortest distance from the character Cin the string.

Example 1:

1
2
Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

  1. S string length is in [1, 10000].
  2. C is a single character, and guaranteed to be in string S.
  3. All letters in S and C are lowercase.
Think

遍历两次数组，分别从前往后和从后往前，记录字符C的位置，然后取i - pos 或者 pos - i即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> shortestToChar(string S, char C) {
    int n = S.size(), pos = -n;
    vector<int> res(n);
    for(int i = 0; i < n; i++){
        if(S[i] == C) pos = i;
        res[i] = i - pos;
    }

    for(int i = pos - 1; i >= 0; i--){
        if(S[i] == C) pos = i;
        res[i] = min(res[i], pos - i);
    }

    return res;
}

LC869 Reordered Power of 2

Problem

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

1
2
Input: 1
Output: true

Example 2:

1
2
Input: 10
Output: false

Example 3:

1
2
Input: 16
Output: true

Example 4:

1
2
Input: 24
Output: false

Example 5:

1
2
Input: 46
Output: true

Note:

  1. 1 <= N <= 10^9
Think

遍历所有可能的2的幂次，如果n为2的幂次的重排列，则其每个数字出现的个数应当是相同的。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool reorderedPowerOf2(int N) {
    int *cur = getCount(N);
    for(int i = 0; i < 32; i++){
        if(equalArr(cur, getCount(1 << i))) return true;
    }
    return false;
}

int* getCount(int n){
    int *res = new int[10];
    while(n > 0){
        res[n % 10]++;
        n /= 10;
    }
    return res;
}

bool equalArr(int *a1, int *a2){
    for(int i = 0; i < 10; i++){
        if(a1[i] != a2[i]) return false;
    }
    return true;
}

Review

并查集主要两个函数：getRoot，unionFind

  • getRoot的写法固定，即：

    1
    2
    3
    string getRoot(vector<int> &root, int i){
        return root[i] == i ? i : getRoot(root, root[i]);
    }

  • unionFind函数主要负责判断给定的两个节点是否有相同的root，如果没有则需要将其中一个节点的root值设为另一个节点。