花花酱 LeetCode 525. Contiguous Array

By zxi on June 30, 2018

Problem

题目大意：求最长子数组，要求其中0和1的数量相等。

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Solution: HashTable

Prefix sum + hashtable

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 143 ms

class Solution {

public:

int findMaxLength(vector<int>& nums) {

if (nums.empty()) return 0;

unordered_map<int, int> pos;

int sum = 0;

int ans = 0;

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

sum += nums[i] ? 1 : -1;

if (sum == 0) {

ans = i + 1;

} else if (pos.count(sum)) {

ans = max(ans, i - pos[sum]);

} else {

pos[sum] = i;

}

return ans;

}

};

V2: Using array instead of a hashtable

Time complexity: O(2*n + 1 + n)

Space complexity: O(2*n + 1)

// Author: Huahua

// Running time: 102 ms (<96.8 %)

class Solution {

public:

int findMaxLength(vector<int>& nums) {

if (nums.empty()) return 0;

const int n = nums.size();

vector<int> pos(2 * n + 1, INT_MIN);

int sum = 0;

int ans = 0;

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

sum += nums[i] ? 1 : -1;

if (sum == 0) {

ans = i + 1;

} else if (pos[sum + n] != INT_MIN) {

ans = max(ans, i - pos[sum + n]);

} else {

pos[sum + n] = i;

}

return ans;

}

};

花花酱 LeetCode 567. Permutation in String

By zxi on June 28, 2018

Problem

题目大意：给你s1, s2，问你s2的子串中是否存在s1的一个排列。

https://leetcode.com/problems/permutation-in-string/description/

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

Solution: Sliding Window

Time Complexity: O(l1 + l2 * 26) = O(l1 + l2)

Space Complexity: O(26 * 2) = O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool checkInclusion(string s1, string s2) {

int l1 = s1.length();

int l2 = s2.length();

vector<int> c1(26);

vector<int> c2(26);

for (const char c : s1)

++c1[c - 'a'];

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

if (i >= l1)

--c2[s2[i - l1] - 'a'];

++c2[s2[i] - 'a'];

if (c1 == c2) return true;

}

return false;

}

};

Problem

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots – they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

The input array won’t violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

bool canPlaceFlowers(vector<int>& flowerbed, int n) {

int count = 0;

for (size_t i = 0; i < flowerbed.size() && count < n; ++i) {

if (flowerbed[i]) continue;

bool left = i == 0 ? true : !flowerbed[i - 1];

bool right = i == flowerbed.size() - 1 ? true : !flowerbed[i + 1];

if (left && right) {

flowerbed[i++] = 1;

++count;

}

return count == n;

}

};

花花酱 LeetCode 228. Summary Ranges

By zxi on June 27, 2018

Problem

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

Solution

Time complexity: O(n)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

vector<string> summaryRanges(vector<int>& nums) {

int s = 0;

vector<string> ans;

for (size_t i = 1; i <= nums.size(); ++i) {

if (i == nums.size() || nums[i] != nums[i - 1] + 1) {

if (s == i - 1)

ans.push_back(to_string(nums[s]));

else

ans.push_back(to_string(nums[s]) + "->" + to_string(nums[i - 1]));

s = i;

}

return ans;

}

};

花花酱 LeetCode 289. Game of Life

By zxi on June 27, 2018

Problem

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

Input: 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
Output: 
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

Follow up:

Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Solution: Simulation

Time complexity: O(mn)

Space complexity: O(1)

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

void gameOfLife(vector<vector<int>>& board) {

int m = board.size();

int n = m ? board[0].size() : 0;

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

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

int lives = 0;

// Scan the 3x3 region including (j, i).

for (int y = max(0, i - 1); y < min(m, i + 2); ++y)

for (int x = max(0, j - 1); x < min(n, j + 2); ++x)

lives += board[y][x] & 1;

if (lives == 3 || lives - board[i][j] == 3) board[i][j] |= 0b10;

}

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

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

board[i][j] >>= 1;

}

};

花花酱 LeetCode 525. Contiguous Array

Problem

Solution: HashTable

花花酱 LeetCode 567. Permutation in String

Problem

Solution: Sliding Window

Related Problems

花花酱 LeetCode 605. Can Place Flowers

Problem

Solution: Greedy

花花酱 LeetCode 228. Summary Ranges

Problem

Solution

花花酱 LeetCode 289. Game of Life

Problem

Solution: Simulation

Huahua's Tech Road

花花酱 LeetCode 525. Contiguous Array

Problem

Solution: HashTable

花花酱 LeetCode 567. Permutation in String

Problem

Solution: Sliding Window

Related Problems

花花酱 LeetCode 605. Can Place Flowers

Problem

Solution: Greedy

花花酱 LeetCode 228. Summary Ranges

Problem

Solution

花花酱 LeetCode 289. Game of Life

Problem

Solution: Simulation