花花酱 LeetCode 438. Find All Anagrams in a String

By zxi on May 28, 2018

Problem

题目大意：在s中找出所有p的Anagrams。

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution: HashTable + Sliding Window

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

vector<int> findAnagrams(string s, string p) {

int n = s.length();

int l = p.length();

vector<int> ans;

vector<int> vp(26, 0);

vector<int> vs(26, 0);

for (char c : p) ++vp[c - 'a'];

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

if (i >= l) --vs[s[i - l] - 'a'];

++vs[s[i] - 'a'];

if (vs == vp) ans.push_back(i + 1 - l);

}

return ans;

}

};

花花酱 LeetCode 841. Keys and Rooms

By zxi on May 27, 2018

Problem

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

Solution: DFS

Time complexity: O(V + E)

Space complexity: O(V)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool canVisitAllRooms(vector<vector<int>>& rooms) {

unordered_set<int> visited;

dfs(rooms, 0, visited);

return visited.size() == rooms.size();

}

private:

void dfs(const vector<vector<int>>& rooms,

int cur, unordered_set<int>& visited) {

if (visited.count(cur)) return;

visited.insert(cur);

for (int nxt : rooms[cur])

dfs(rooms, nxt, visited);

}

};

花花酱 LeetCode 329. Longest Increasing Path in a Matrix

By zxi on May 24, 2018

Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution1: DFS + Memorization

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int longestIncreasingPath(vector<vector<int>>& matrix) {

if (matrix.empty()) return 0;

m_ = matrix.size();

n_ = matrix[0].size();

dp_ = vector<vector<int>>(m_, vector<int>(n_, -1));

int ans = 0;

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

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

ans = max(ans, dfs(matrix, x, y));

return ans;

}

private:

int dfs(const vector<vector<int>>& mat, int x, int y) {

if (dp_[y][x] != -1) return dp_[y][x];

static int dirs[] = {0, -1, 0, 1, 0};

dp_[y][x] = 1;

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

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx >= n_ || ty >= m_ || mat[ty][tx] <= mat[y][x])

continue;

dp_[y][x] = max(dp_[y][x], 1 + dfs(mat, tx, ty));

}

return dp_[y][x];

}

int m_;

int n_;

// dp[i][j]: max length start from (j, i)

vector<vector<int>> dp_;

};

Solution2: DP

Time complexity: O(mn*log(mn))

Space complexity: O(mn)

// Author: Huahua

// Running time: 63 ms

class Solution {

public:

int longestIncreasingPath(vector<vector<int>>& matrix) {

if (matrix.empty()) return 0;

int m = matrix.size();

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

vector<vector<int>> dp(m, vector<int>(n, 1));

int ans = 0;

vector<pair<int, pair<int, int>>> cells;

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

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

cells.push_back({matrix[y][x], {x, y}});

sort(cells.rbegin(), cells.rend());

vector<int> dirs {0, 1, 0, -1, 0};

for (const auto& cell : cells) {

int x = cell.second.first;

int y = cell.second.second;

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

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

if (matrix[ty][tx] <= matrix[y][x]) continue;

dp[y][x] = max(dp[y][x], 1 + dp[ty][tx]);

}

ans = max(ans, dp[y][x]);

}

return ans;

}

};

花花酱 LeetCode 830. Positions of Large Groups

By zxi on May 13, 2018

Problem

In a string S of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like S = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z" and "yy".

Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

Example 1:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting 3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

Note: 1 <= S.length <= 1000

Solution: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

vector<vector<int>> largeGroupPositions(string S) {

constexpr int kLargeGroupSize = 3;

const int n = S.size();

vector<vector<int>> ans;

int c = 0;

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

if (i == n || S[i] != S[i - 1]) {

if (c >= kLargeGroupSize) ans.push_back({i - c, i - 1});

c = 0;

}

return ans;

}

};

花花酱 LeetCode 832. Flipping an Image

By zxi on May 13, 2018

Problem

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1

Solution 1: Brute Force

Time complexity: O(m*n)

Space complexity: O(m*n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {

auto B = A;

int m = A.size();

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

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

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

B[i][j] = 1 - A[i][n - j - 1];

return B;

}

};

Huahua's Tech Road

花花酱 LeetCode 438. Find All Anagrams in a String

Problem

Solution: HashTable + Sliding Window

花花酱 LeetCode 841. Keys and Rooms

Problem

Solution: DFS

花花酱 LeetCode 329. Longest Increasing Path in a Matrix

Problem

Solution1: DFS + Memorization

Solution2: DP

花花酱 LeetCode 830. Positions of Large Groups

Problem

Solution: Brute Force

花花酱 LeetCode 832. Flipping an Image

Problem

Solution 1: Brute Force