Posts published in June 2018

花花酱 LeetCode 852. Peak Index in a Mountain Array

By zxi on June 17, 2018

Problem

Let’s call an array A a mountain if the following properties hold:

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

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

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

Example 2:

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

Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.

Solution1: Liner Scan

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

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

if (A[i] < A[i - 1]) return i - 1;

}

};

C++/STL

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

return max_element(begin(A), end(A)) - begin(A);

}

};

Solution 2: Binary Search

Find the smallest l such that A[l] > A[l + 1].

Time complexity: O(logn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

int l = 0;

int r = A.size();

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

};

Java

// Author: Huahua, 3 ms

class Solution {

public int peakIndexInMountainArray(int[] A) {

int l = 0;

int r = A.length;

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

Python3

# Author: Huahua, 40 ms

class Solution:

def peakIndexInMountainArray(self, A):

l, r = 0, len(A)

while l < r:

m = l + (r - l) // 2

if A[m] > A[m + 1]:

r = m

else:

l = m + 1

return l

花花酱 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 849. Maximize Distance to Closest Person

By zxi on June 11, 2018

Problem

In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty.

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.

Return that maximum distance to closest person.

Example 1:

Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

Input: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:

1 <= seats.length <= 20000
seats contains only 0s or 1s, at least one 0, and at least one 1.

Solution

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int maxDistToClosest(vector<int>& seats) {

int n = seats.size();

int prev = -1;

int ans = 0;

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

if (i == n) ans = max(ans, n - prev - 1);

else if (seats[i]) {

if (prev == -1) ans = i;

else ans = max(ans, (i - prev) / 2);

prev = i;

}

return ans;

}

};

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

By zxi on June 3, 2018

Problem

题目大意：求顶点覆盖的最短路径。

https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Solution: BFS

Time complexity: O(n*2^n)

Space complexity: O(n*2^n)

C++

// Author: Huahua

// Running time: 34 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int kAns = (1 << (graph.size())) - 1;

queue<pair<int, int>> q;

unordered_set<int> visited; // (cur_node << 16) | state

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

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int n = p.first;

int state = p.second;

if (state == kAns) return steps;

int key = (n << 16) | state;

if (visited.count(key)) continue;

visited.insert(key);

for (int next : graph[n])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

C++ / vector

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int n = graph.size();

const int kAns = (1 << n) - 1;

queue<pair<int, int>> q;

vector<vector<int>> visited(n, vector<int>(1 << n));

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

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int node = p.first;

int state = p.second;

if (state == kAns) return steps;

if (visited[node][state]) continue;

visited[node][state] = 1;

for (int next : graph[node])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

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;

}

};

Posts published in June 2018

花花酱 LeetCode 852. Peak Index in a Mountain Array

Problem

Solution1: Liner Scan

C++

C++/STL

Solution 2: Binary Search

C++

Java

Python3

花花酱 LeetCode 848. Shifting Letters

Problem

Solution

花花酱 LeetCode 849. Maximize Distance to Closest Person

Problem

Solution

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

Problem

Solution: BFS

Related Problems

花花酱 LeetCode 846. Hand of Straights

Problem

Solution: Greedy