Posts published in “Search”

花花酱 LeetCode 301. Remove Invalid Parentheses

By zxi on December 21, 2017

Problem:

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]

"(a)())()" -> ["(a)()()", "(a())()"]

")(" -> [""]

题目大意：给你一个字符串，由”(” “)”和其他字符构成。让你删除数量最少的括号使得表达式合法（括号都匹配）。输出所有的合法表达式。

Idea:

Solution: DFS

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<string> removeInvalidParentheses(const string& s) {

int l = 0;

int r = 0;

for (const char ch : s) {

l += (ch == '(');

if (l == 0)

r += (ch == ')');

else

l -= (ch == ')');

}

vector<string> ans;

dfs(s, 0, l, r, ans);

return ans;

}

private:

bool isValid(const string& s) {

int count = 0;

for (const char ch : s) {

if (ch == '(') ++count;

if (ch == ')') --count;

if (count < 0) return false;

}

return count == 0;

}

// l/r: number of left/right parentheses to remove.

void dfs(const string& s, int start, int l, int r, vector<string>& ans) {

// Nothing to remove.

if (l == 0 && r == 0) {

if (isValid(s)) ans.push_back(s);

return;

}

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

// We only remove the first parenthes if there are consecutive ones to avoid duplications.

if (i != start && s[i] == s[i - 1]) continue;

if (s[i] == '(' || s[i] == ')') {

string curr = s;

curr.erase(i, 1);

if (r > 0 && s[i] == ')')

dfs(curr, i, l, r - 1, ans);

else if (l > 0 && s[i] == '(')

dfs(curr, i, l - 1, r, ans);

}

};

花花酱 LeetCode 749. Contain Virus

By zxi on December 18, 2017

题目大意：给你一个格子地图上面有一些病毒用1表示，未受感染的格子用0表示。带有病毒的格子每天会向四周的格子传播病毒。在每一天，你必须在最大的病毒（连通区域）的周围建造墙阻挡病毒传播。问你一共需要多少个墙才能阻挡所有病毒传播。

Problems:

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region — the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:

Input: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: grid = 
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

Example 3:

Input: grid = 
[[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls.

Note:

The number of rows and columns of grid will each be in the range [1, 50].
Each grid[i][j] will be either 0 or 1.
Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

Idea:

Use DFS to find virus regions, next affected regions and # of walls needed to block each virus region.

Simulate the virus expansion process.

Solution:

C++ / DFS

Time complexity: O(n^3)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

int containVirus(vector<vector<int>>& grid) {

int m = grid.size();

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

int total_walls = 0;

while (true) {

vector<int> visited(m * n, 0);

vector<int> virus_area;

vector<unordered_set<int>> nexts;

int block_index = -1;

int block_walls = -1;

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

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

int key = i * n + j;

if (grid[i][j] != 1 || visited[key]) continue;

vector<int> curr;

unordered_set<int> next;

int walls = 0;

getArea(j, i, m, n, grid, visited, curr, next, walls);

if (next.empty()) continue;

if (nexts.empty() || next.size() > nexts[block_index].size()) {

virus_area.swap(curr);

block_index = nexts.size();

block_walls = walls;

}

nexts.push_back(std::move(next));

}

if (nexts.empty()) break;

total_walls += block_walls;

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

if (i == block_index) {

for (const int key : virus_area) {

int y = key / n;

int x = key % n;

grid[y][x] = 2; // blocked.

}

} else {

for (const int key : nexts[i]) {

int y = key / n;

int x = key % n;

grid[y][x] = 1; // newly affected

}

return total_walls;

}

private:

void getArea(

int x, int y, int m, int n,

vector<vector<int>>& grid,

vector<int>& visited,

vector<int>& curr,

unordered_set<int>& next,

int& walls) {

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

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == 2) return;

int key = y * n + x;

// need one wall

if (grid[y][x] == 0) {

++walls;

next.insert(key);

return;

}

if (visited[key]) return;

visited[key] = 1;

curr.push_back(key);

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

getArea(x + dirs[i][0], y + dirs[i][1], m, n, grid, visited, curr, next, walls);

}

};

Related Problems:

[解题报告] LeetCode 200. Number of Islands

花花酱 LeetCode 733. Flood Fill

By zxi on November 28, 2017

Problem:

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:

Input:

image = [[1,1,1],[1,1,0],[1,0,1]]

sr = 1, sc = 1, newColor = 2

Output: [[2,2,2],[2,2,0],[2,0,1]]

Explanation:

From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected

by a path of the same color as the starting pixel are colored with the new color.

Note the bottom corner is not colored 2, because it is not 4-directionally connected

to the starting pixel.

Note:

The length of image and image[0] will be in the range [1, 50].
The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

Idea

DFS

Solution:

C++ / DFS

Time complexity: O(mn)

Space complexity: O(1)

// Author: Huahua

// Runtime: 33 ms

class Solution {

public:

vector<vector<int>> floodFill(vector<vector<int>>& image,

int sr, int sc, int newColor) {

if (image[sr][sc] == newColor) return image;

int m = image.size();

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

floodFill(image, sc, sr, n, m, image[sr][sc], newColor);

return image;

}

private:

void floodFill(vector<vector<int>>& image,

int x, int y, int n, int m, int orgColor, int newColor) {

if (x < 0 || x >= n || y < 0 || y >= m) return;

if (image[y][x] != orgColor) return;

image[y][x] = newColor;

floodFill(image, x + 1, y, n, m, orgColor, newColor);

floodFill(image, x - 1, y, n, m, orgColor, newColor);

floodFill(image, x, y + 1, n, m, orgColor, newColor);

floodFill(image, x, y - 1, n, m, orgColor, newColor);

}

};

Related Problems:

花花酱 LeetCode 216. Combination Sum III

By zxi on November 3, 2017

题目大意：输出所有用k个数的和为n的组合。可以使用的元素是1到9。

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

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

Idea:

DFS + backtracking

bit

Solution:

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

vector<int> cur;

dfs(k, n, 1, cur, ans);

return ans;

}

private:

// Use k numbers (>= s) to sum up to n

void dfs(int k, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (k == 0) {

if (n == 0) ans.push_back(cur);

return;

}

for (int i = s; i <= 9; ++i) {

if (i > n) return;

cur.push_back(i);

dfs(k - 1, n - i, i + 1, cur, ans);

cur.pop_back();

}

};

C++ / binary

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

// 2^9, generate all combinations of [1 .. 9]

for (int i = 0; i < (1 << 9); ++i) {

vector<int> cur;

int sum = 0;

// Use j if (j - 1)-th bit is 1

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

if (i & (1 << (j - 1))) {

sum += j;

cur.push_back(j);

}

if (sum == n && cur.size() == k)

ans.push_back(cur);

}

return ans;

}

};

Python

class Solution:

def combinationSum3(self, k, n):

def dfs(k, n, s, cur, ans):

if k == 0 and n == 0:

ans.append(list(cur))

for i in range(s, min(n + 1, 10)):

dfs(k - 1, n - i, i + 1, cur + [i], ans)

ans = []

dfs(k, n, 1, [], ans)

return ans

Related problems:

花花酱 LeetCode 37. Sudoku Solver

By zxi on October 16, 2017

Problem:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

Idea:

DFS + backtracking

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

void solveSudoku(vector<vector<char>>& board) {

rows_ = vector<vector<int>>(9, vector<int>(10));

cols_ = vector<vector<int>>(9, vector<int>(10));

boxes_ = vector<vector<int>>(9, vector<int>(10));

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

for(int j = 0; j < 9; j++) {

const char c = board[i][j];

if ( c != '.') {

int n = c - '0';

int bx = j / 3;

int by = i / 3;

rows_[i][n] = 1;

cols_[j][n] = 1;

boxes_[by * 3 + bx][n] = 1;

}

fill(board, 0, 0);

}

private:

vector<vector<int>> rows_, cols_, boxes_;

bool fill(vector<vector<char>>& board, int x, int y) {

if (y == 9)

return true;

int nx = (x + 1) % 9;

int ny = (nx == 0) ? y + 1 : y;

if (board[y][x] != '.') return fill(board, nx, ny);

for (int i = 1; i <= 9; i++) {

int bx = x / 3;

int by = y / 3;

int box_key = by * 3 + bx;

if (!rows_[y][i] && !cols_[x][i] && !boxes_[box_key][i]) {

rows_[y][i] = 1;

cols_[x][i] = 1;

boxes_[box_key][i] = 1;

board[y][x] = i + '0';

if (fill(board, nx, ny)) return true;

board[y][x] = '.';

boxes_[box_key][i] = 0;

cols_[x][i] = 0;

rows_[y][i] = 0;

}

return false;

}

};

Related Problems:

[解题报告] LeetCode 51. N-Queens