Posts tagged as “medium”

花花酱 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 848. Shifting Letters

By zxi on June 11, 2018

Problem

We have a string S of lowercase letters, and an integer array shifts.

Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').

For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.

Now for each shifts[i] = x, we want to shift the first i+1 letters of S, x times.

Return the final string after all such shifts to S are applied.

Example 1:

Input: S = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 
We start with "abc".
After shifting the first 1 letters of S by 3, we have "dbc".
After shifting the first 2 letters of S by 5, we have "igc".
After shifting the first 3 letters of S by 9, we have "rpl", the answer.

Note:

1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 54 ms

class Solution {

public:

string shiftingLetters(string S, vector<int>& shifts) {

int c = 0;

for (int i = shifts.size() - 1; i >= 0; --i) {

c += (shifts[i] % 26);

S[i] = (S[i] - 'a' + c) % 26 + 'a';

}

return S;

}

};

花花酱 LeetCode 846. Hand of Straights

By zxi on June 3, 2018

Problem

题目大意：给你一些牌，问你能否分组，要求每组w张连续的牌。

https://leetcode.com/problems/hand-of-straights/description/

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

Note:

1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

Solution: Greedy

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 65 ms

class Solution {

public:

bool isNStraightHand(vector<int>& hand, int W) {

map<int, int> counts;

for (int h : hand) ++counts[h];

while (!counts.empty()) {

auto it = counts.begin();

int start = it->first;

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

if (it == counts.end()

|| it->first != start + j) return false;

auto prev = it++;

if (--(prev->second) == 0)

counts.erase(prev);

}

return true;

}

};

花花酱 LeetCode 845. Longest Mountain in Array

By zxi on June 3, 2018

Problem

题目大意：找出最长的山形子数组。

https://leetcode.com/problems/longest-mountain-in-array/description/

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold:

B.length >= 3
There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000

Solution: DP

Three passes

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

int longestMountain(vector<int>& A) {

vector<int> inc(A.size());

vector<int> dec(A.size());

for (int i = 1; i < A.size(); ++i)

if (A[i] > A[i - 1]) inc[i] = inc[i - 1] + 1;

for (int i = A.size() - 2; i > 0; --i)

if (A[i] > A[i + 1]) dec[i] = dec[i + 1] + 1;

int ans = 0;

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

if (inc[i] && dec[i])

ans = max(ans, inc[i] + dec[i] + 1);

return ans >= 3 ? ans : 0;

}

};

One pass

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

int longestMountain(vector<int>& A) {

int inc = 0;

int dec = 0;

int ans = 0;

for (int i = 1; i < A.size(); ++i) {

if (dec && A[i] > A[i - 1] || A[i] == A[i - 1])

dec = inc = 0;

inc += A[i] > A[i - 1];

dec += A[i] < A[i - 1];

if (inc && dec)

ans = max(ans, inc + dec + 1);

}

return ans >= 3 ? ans : 0;

}

};