花花酱 LeetCode 547. Friend Circles

By zxi on September 21, 2017

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 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 i_thand j_th 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:

Input:

[[1,1,0],

[1,1,0],

[0,0,1]]

Output: 2

Example 2:

Input:

[[1,1,0],

[1,1,1],

[0,1,1]]

Output: 1

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

Idea:

Find all connected components using DFS

Solution: DFS

C++

// Author: Huahua

// Time complexity: O(n^2)

// Space complexity: O(n)

// Running Time: 25 ms

class Solution {

public:

int findCircleNum(vector<vector<int>>& M) {

if (M.empty()) return 0;

int n = M.size();

int ans = 0;

for (int i = 0; i < n; ++i) {

if (!M[i][i]) continue;

++ans;

dfs(M, i, n);

}

return ans;

}

private:

void dfs(vector<vector<int>>& M, int curr, int n) {

// Visit all friends (neighbors)

for (int i = 0; i < n; ++i) {

if (!M[curr][i]) continue;

M[curr][i] = M[i][curr] = 0;

dfs(M, i, n);

}

};

Java

// Author: Huahua

// Time complexity: O(n^2)

// Space complexity: O(n)

// Running Time: 20 ms

class Solution {

public int findCircleNum(int[][] M) {

int n = M.length;

if (n == 0) return 0;

int ans = 0;

for (int i = 0; i < n; ++i) {

if (M[i][i] == 0) continue;

++ans;

dfs(M, i, n);

}

return ans;

}

private void dfs(int[][] M, int curr, int n) {

for (int i = 0; i < n; ++i) {

if (M[curr][i] == 0) continue;

M[curr][i] = M[i][curr] = 0;

dfs(M, i, n);

}

Python

"""

Author: Huahua

Time complexity: O(n^2)

Space complexity: O(n)

Running Time: 162 ms

"""

class Solution(object):

def findCircleNum(self, M):

"""

:type M: List[List[int]]

:rtype: int

"""

def dfs(M, curr, n):

for i in xrange(n):

if M[curr][i] == 1:

M[curr][i] = M[i][curr] = 0

dfs(M, i, n)

n = len(M)

ans = 0

for i in xrange(n):

if M[i][i] == 1:

ans += 1

dfs(M, i, n)

return ans

Solution 2: Union Find

C++

// Author: Huahua

// Runtime: 19 ms

class UnionFindSet {

public:

UnionFindSet(int n) {

parents_ = vector<int>(n + 1, 0);

ranks_ = vector<int>(n + 1, 0);

for (int i = 0; i < parents_.size(); ++i)

parents_[i] = i;

}

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pu] > ranks_[pv]) {

parents_[pv] = pu;

} else if (ranks_[pv] > ranks_[pu]) {

parents_[pu] = pv;

} else {

parents_[pu] = pv;

++ranks_[pv];

}

return true;

}

int Find(int id) {

if (id != parents_[id])

parents_[id] = Find(parents_[id]);

return parents_[id];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

class Solution {

public:

int findCircleNum(vector<vector<int>>& M) {

int n = M.size();

UnionFindSet s(n);

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

if (M[i][j] == 1) s.Union(i, j);

unordered_set<int> circles;

for (int i = 0; i < n; ++i)

circles.insert(s.Find(i));

return circles.size();

}

};

Idea: DFS

Use DFS to find a connected component (an island) and mark all the nodes to 0.

Time complexity: O(mn)

Space complexity: O(mn)

Solution

C++

// Author: Huahua

// Time complexity: O(mn)

// Running time: 6 ms

class Solution {

public:

int numIslands(vector<vector<char>>& grid) {

if (grid.empty()) return 0;

int m = grid.size();

int n = grid[0].size();

int ans = 0;

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x) {

ans += grid[y][x] - '0';

dfs(grid, x, y, m, n);

}

return ans;

}

private:

void dfs(vector<vector<char>>& grid, int x, int y, int m, int n) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, m, n);

dfs(grid, x - 1, y, m, n);

dfs(grid, x, y + 1, m, n);

dfs(grid, x, y - 1, m, n);

}

};

Java

// Author: Huahua

// Time Complexity: O(mn)

// Running time: 13 ms

class Solution {

public int numIslands(char[][] grid) {

int m = grid.length;

if (m == 0) return 0;

int n = grid[0].length;

int ans = 0;

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

if (grid[y][x] == '1') {

++ans;

dfs(grid, x, y, n, m);

}

return ans;

}

private void dfs(char[][] grid, int x, int y, int n, int m) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, n, m);

dfs(grid, x - 1, y, n, m);

dfs(grid, x, y + 1, n, m);

dfs(grid, x, y - 1, n, m);

}

Python

"""

Author: Huahua

Time Complexity: O(mn)

Running Time: 102 ms

"""

class Solution(object):

def numIslands(self, grid):

"""

:type grid: List[List[str]]

:rtype: int

"""

m = len(grid)

if m == 0: return 0

n = len(grid[0])

ans = 0

for y in xrange(m):

for x in xrange(n):

if grid[y][x] == '1':

ans += 1

self.__dfs(grid, x, y, n, m)

return ans

def __dfs(self, grid, x, y, n, m):

if x < 0 or y < 0 or x >=n or y >= m or grid[y][x] == '0':

return

grid[y][x] = '0'

self.__dfs(grid, x + 1, y, n, m)

self.__dfs(grid, x - 1, y, n, m)

self.__dfs(grid, x, y + 1, n, m)

self.__dfs(grid, x, y - 1, n, m)

Related Problems

花花酱 LeetCode 409. Longest Palindrome

By zxi on September 19, 2017

https://leetcode.com/problems/longest-palindrome/description/

Problem:

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:

"abccccdd"

Output:

Explanation:

One longest palindrome that can be built is "dccaccd", whose length is 7.

Idea:

Greedy + Counting

Solution:

C++

// Author: Huahua

// Time complexity: O(n)

// Space complexity: O(128) = O(1)

// Running time: 3 ms 9/2017

class Solution {

public:

int longestPalindrome(const string& s) {

vector<int> freqs(128, 0);

for (const char c : s)

++freqs[c];

int ans = 0;

int odd = 0;

for (const int freq : freqs) {

// same as: ans += freq % 2 == 0 ? freq : freq - 1;

// same as: ans += freq / 2 * 2;

// same as: ans += ((freq >> 1) << 1);

// same as: ans += freq & (INT_MAX - 1);

ans += freq & (~1); // clear the last bit

odd |= freq & 1;

}

ans += odd;

return ans;

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int longestPalindrome(String s) {

int[] freqs = new int[128];

for (int i = 0; i < s.length(); ++i)

++freqs[s.charAt(i)];

int ans = 0;

int odd = 0;

for (int freq: freqs) {

ans += freq & (~1);

odd |= freq & 1;

}

return ans + odd;

}

Python

"""

Author: Huahua

Running time: 39 ms

"""

class Solution(object):

def longestPalindrome(self, s):

"""

:type s: str

:rtype: int

"""

freqs = [0] * 128

for c in s:

freqs[ord(c)] += 1

ans, odd = 0, 0

for freq in freqs:

ans += freq & (~1)

odd |= freq & 1

return ans + odd

花花酱 LeetCode 304. Range Sum Query 2D – Immutable

By zxi on September 18, 2017

https://leetcode.com/problems/range-sum-query-2d-immutable/description/

Problem:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [

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

[5, 6, 3, 2, 1],

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

[4, 1, 0, 1, 7],

[1, 0, 3, 0, 5]

]

sumRegion(2, 1, 4, 3) : 8

sumRegion(1, 1, 2, 2) : 11

sumRegion(1, 2, 2, 4) : 12

Note:

You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Idea:

Dynamic programming

Time complexity:

O(n^2)

sumRegion: O(1)

Solution:

// Author: Huahua

// Time complexity:

// constructor: O(n^2)

// sumRegion: O(1)

// Running time: 22 ms 9/2017

class NumMatrix {

public:

NumMatrix(const vector<vector<int>>& matrix) {

sums_.clear();

if (matrix.empty()) return;

int m = matrix.size();

int n = matrix[0].size();

// sums_[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])

sums_ = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

sums_[i][j] = matrix[i - 1][j - 1]

+ sums_[i - 1][j]

+ sums_[i][j - 1]

- sums_[i - 1][j - 1];

}

int sumRegion(int row1, int col1, int row2, int col2) {

return sums_[row2 + 1][col2 + 1]

- sums_[row2 + 1][col1]

- sums_[row1][col2 + 1]

+ sums_[row1][col1];

}

private:

vector<vector<int>> sums_;

};

/**

* Your NumMatrix object will be instantiated and called as such:

* NumMatrix obj = new NumMatrix(matrix);

* int param_1 = obj.sumRegion(row1,col1,row2,col2);

花花酱 LeetCode 547. Friend Circles

Solution: DFS

C++

Java

Python

Solution 2: Union Find

C++

Related Problems

花花酱 LeetCode 664. Strange Printer

C++

Java

Python3

花花酱 LeetCode 200. Number of Islands

Idea: DFS

Solution

C++

Java

Python

Related Problems

花花酱 LeetCode 409. Longest Palindrome

花花酱 LeetCode 304. Range Sum Query 2D – Immutable

Huahua's Tech Road

花花酱 LeetCode 547. Friend Circles

Solution: DFS

C++

Java

Python

Solution 2: Union Find

C++

Related Problems

花花酱 LeetCode 664. Strange Printer

C++

Java

Python3

花花酱 LeetCode 200. Number of Islands

Idea: DFS

Solution

C++

Java

Python

Related Problems

花花酱 LeetCode 409. Longest Palindrome

花花酱 LeetCode 304. Range Sum Query 2D – Immutable