Posts published in “Search”

Problem

题目大意：初始位置0速度+1，每次你可以加速（速度*2）或者倒车（速度变成-1*dir）。问最少需要执行多少步操作能够到达T。

https://leetcode.com/problems/race-car/description/

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction “A”, your car does the following: position += speed, speed *= 2.

When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.

Note:

1 <= target <= 10000.

Visualization of the Solution

Solution 1: BFS

C++/Str

// Author: Huahua

// Running time: 221 ms

class Solution {

public:

int racecar(int target) {

queue<pair<int, int>> q;

q.push({0, 1});

unordered_set<string> v;

v.insert("0_1");

v.insert("0_-1");

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int pos = p.first;

int speed = p.second;

{

int pos1 = pos + speed;

int speed1 = speed * 2;

pair<int, int> p1{pos1, speed1};

if (pos1 == target) return steps + 1;

if (p1.first > 0 && p1.first < 2 * target)

q.push(p1);

}

{

int speed2 = speed > 0 ? -1 : 1;

pair<int, int> p2{pos, speed2};

string key2 = to_string(pos) + "_" + to_string(speed2);

if (!v.count(key2)) {

q.push(p2);

v.insert(key2);

}

++steps;

}

return -1;

}

};

C++/Int

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int racecar(int target) {

queue<pair<int, int>> q;

q.push({0, 1});

unordered_set<int> v;

v.insert({0, 2});

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int pos = p.first;

int speed = p.second;

pair<int, int> p1 = {pos + speed, speed * 2};

if (p1.first == target) return steps + 1;

if (p1.first > 0 && p1.first + speed < 2 * target)

q.push(p1);

int speed2 = speed > 0 ? -1 : 1;

pair<int, int> p2 = {pos, speed2};

int key = (pos << 2) | (speed2 + 1);

if (!v.count(key) && p2.first >= target / 2) {

q.push(p2);

v.insert(key);

}

++steps;

}

return -1;

}

};

Solution 2: DP O(TlogT)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int racecar(int target) {

m_ = vector<int>(target + 1, 0);

return dp(target);

}

private:

vector<int> m_;

int dp(int t) {

if (m_[t] > 0) return m_[t];

int n = ceil(log2(t + 1));

// AA...A (nA) best case

if (1 << n == t + 1) return m_[t] = n;

// AA...AR (nA + 1R) + dp(left)

m_[t] = n + 1 + dp((1 << n) - 1 - t);

for (int m = 0; m < n - 1; ++m) {

int cur = (1 << (n - 1)) - (1 << m);

//AA...ARA...AR (n-1A + 1R + mA + 1R) + dp(left)

m_[t] = min(m_[t], n + m + 1 + dp(t - cur));

}

return m_[t];

}

};

Solution 3: DP O(T^2)

m[t][d] : min steps to reach t and facing d (0 = right, 1 = left)

Time Complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 469 ms

constexpr int kMaxT = 10000;

int m[kMaxT + 1][2]={0};

class Solution {

public:

int racecar(int target) {

if (m[1][0] == 0) {

for (int t = 1; t <= kMaxT; ++t) {

const int n = ceil(log2(t + 1));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

const int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + min(m[l][1], m[l][0] + 1);

m[t][1] = n + 1 + min(m[l][0], m[l][1] + 1);

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

const int mi = min(m[i][0] + 2, m[i][1] + 1);

m[t][0] = min(m[t][0], m[t - i][0] + mi);

m[t][1] = min(m[t][1], m[t - i][1] + mi);

}

return min(m[target][0], m[target][1]);

}

};

C++/opt

// Author: Huahua

// Running time: 361 ms

typedef unsigned char uint8;

constexpr int kMaxT = 10000;

uint8 m[kMaxT + 1][2]={0};

inline uint8 MIN(uint8 a, uint8 b) {

return a < b ? a : b;

}

class Solution {

public:

int racecar(int target) {

if (m[1][0] == 0) {

for (int t = 1; t <= kMaxT; ++t) {

const int n = ceil(log2(t + 1));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

const int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + MIN(m[l][1], (uint8)(m[l][0] + 1));

m[t][1] = n + 1 + MIN(m[l][0], (uint8)(m[l][1] + 1));

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

const int mi = MIN(m[i][0] + 2, m[i][1] + 1);

m[t][0] = MIN(m[t][0], (uint8)(m[t - i][0] + mi));

m[t][1] = MIN(m[t][1], (uint8)(m[t - i][1] + mi));

}

return min(m[target][0], m[target][1]);

}

};

Java

// Author: Huahua

// Running time: 562 ms

class Solution {

private static int[][] m;

public int racecar(int target) {

if (m == null) {

final int kMaxT = 10000;

m = new int[kMaxT + 1][2];

for (int t = 1; t <= kMaxT; ++t) {

int n = (int)Math.ceil(Math.log(t + 1) / Math.log(2));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + Math.min(m[l][1], m[l][0] + 1);

m[t][1] = n + 1 + Math.min(m[l][0], m[l][1] + 1);

for (int i = 1; i < t; ++i)

for (int d = 0; d <= 1; d++)

m[t][d] = Math.min(m[t][d], Math.min(

m[i][0] + 2 + m[t - i][d],

m[i][1] + 1 + m[t - i][d]));

}

return Math.min(m[target][0], m[target][1]);

}

Problem

题目大意：给你每辆公交车的环形路线，问最少需要坐多少辆公交车才能送S到达T。

https://leetcode.com/problems/bus-routes/description/

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

Solution: BFS

Time Complexity: O(m*n) m: # of buses, n: # of routes

Space complexity: O(m*n + m)

C++

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {

if (S == T) return 0;

unordered_map<int, vector<int>> m;

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

for (const int stop : routes[i])

m[stop].push_back(i);

vector<int> visited(routes.size(), 0);

queue<int> q;

q.push(S);

int buses = 0;

while (!q.empty()) {

int size = q.size();

++buses;

while (size--) {

int curr = q.front(); q.pop();

for (const int bus : m[curr]) {

if (visited[bus]) continue;

visited[bus] = 1;

for (int stop : routes[bus]) {

if (stop == T) return buses;

q.push(stop);

}

return -1;

}

};

花花酱 LeetCode 805. Split Array With Same Average

By zxi on March 24, 2018

Problem

题目大意：问能否将一个数组分成两部分，每部分的平均值相同。

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].

Solution: Search

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 771 ms

class Solution {

public:

bool splitArraySameAverage(vector<int>& A) {

std::sort(A.begin(), A.end());

sum = std::accumulate(A.begin(), A.end(), 0);

n = A.size();

return dfs(A, 1, 0, 0);

}

private:

int sum;

int n;

bool dfs(const vector<int>& A, int c, int s, int cur) {

if (c > A.size() / 2) return false;

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

cur += A[i];

if (cur * (n - c) == (sum - cur) * c) return true;

if (cur * (n - c) > (sum - cur) * c) break;

if (dfs(A, c + 1, i + 1, cur)) return true;

cur -= A[i];

}

return false;

}

};

花花酱 LeetCode 803. Bricks Falling When Hit

By zxi on March 18, 2018

Problem

题目大意：给你一堵砖墙，求每次击碎一块后掉落的砖头数量。

We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

Example 1:
Input: 
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation: 
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.

Example 2:
Input: 
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: 
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping.  Note that the erased brick (1, 0) will not be counted as a dropped brick.

Idea

For each day, hit and clear the specified brick.
Find all connected components (CCs) using DFS.
For each CC, if there is no brick that is on the first row that the entire cc will drop. Clear those CCs.

Solution: DFS

C++

// Author: Huahua

// Running time: 1261 ms

class Solution {

public:

vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {

dirs_ = {0, -1, 0, 1, 0};

m_ = grid.size();

n_ = grid[0].size();

g_.swap(grid);

seq_ = 1;

vector<int> ans;

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

ans.push_back(hit(hits[i][1], hits[i][0]));

return ans;

}

private:

vector<vector<int>> g_;

vector<int> dirs_;

int seq_;

int m_;

int n_;

// hit x, y and return the number of bricks fallen.

int hit(int x, int y) {

if (x < 0 || x >= n_ || y < 0 || y >= m_) return 0;

g_[y][x] = 0;

int ans = 0;

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

++seq_;

int count = 0;

if (!fall(x + dirs_[i], y + dirs_[i + 1], false, count)) continue;

++seq_;

ans += count;

fall(x + dirs_[i], y + dirs_[i + 1], true, count);

}

return ans;

}

// Check whether the CC contains (x, y) will fall or not.

// Set all nodes in this CC as seq_ or 0 if clear.

// count: the # of nodes in this CC.

bool fall(int x, int y, bool clear, int& count) {

if (x < 0 || x >= n_ || y < 0 || y >= m_) return true;

if (g_[y][x] == seq_ || g_[y][x] == 0) return true;

if (y == 0) return false;

g_[y][x] = clear ? 0 : seq_;

++count;

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

if (!fall(x + dirs_[i], y + dirs_[i + 1], clear, count)) return false;

return true;

}

};

Java

// Author: Huahua

// Stack Overflow (1024 recursive calls)

class Solution {

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

int m;

int n;

int[][] g;

int seq;

int count;

public int[] hitBricks(int[][] grid, int[][] hits) {

this.g = grid;

this.m = grid.length;

this.n = grid[0].length;

int[] ans = new int[hits.length];

for (int i = 0; i < hits.length; ++i)

ans[i] = hit(hits[i][1], hits[i][0]);

return ans;

}

private int hit(int x, int y) {

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

g[y][x] = 0;

int ans = 0;

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

++seq;

count = 0;

if (!fall(x + dirs[i], y + dirs[i + 1], false)) continue;

ans += count;

++seq;

fall(x + dirs[i], y + dirs[i + 1], true);

}

return ans;

}

private boolean fall(int x, int y, boolean clear) {

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

if (g[y][x] == seq || g[y][x] == 0) return true;

if (y == 0) return false;

g[y][x] = clear ? 0 : seq;

++count;

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

if (!fall(x + dirs[i], y + dirs[i + 1], clear)) return false;

return true;

}

Solution 1: DFS

Time complexity: O(n*2^l), l = # of letters in the string

Space complexity: O(n) + O(n*2^l)

C++

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<string> letterCasePermutation(string S) {

vector<string> ans;

dfs(S, 0, ans);

return ans;

}

private:

void dfs(string& S, int s, vector<string>& ans) {

if (s == S.length()) {

ans.push_back(S);

return;

}

dfs(S, s + 1, ans);

if (!isalpha(S[s])) return;

S[s] ^= (1 << 5);

dfs(S, s + 1, ans);

S[s] ^= (1 << 5);

}

};

Java

// Author: Huahua

// Running time: 8 ms

class Solution {

public List<String> letterCasePermutation(String S) {

List<String> ans = new ArrayList<>();

dfs(S.toCharArray(), 0, ans);

return ans;

}

private void dfs(char[] S, int i, List<String> ans) {

if (i == S.length) {

ans.add(new String(S));

return;

}

dfs(S, i + 1, ans);

if (!Character.isLetter(S[i])) return;

S[i] ^= 1 << 5;

dfs(S, i + 1, ans);

S[i] ^= 1 << 5;

}

Python 3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def letterCasePermutation(self, S):

ans = []

def dfs(S, i, n):

if i == n:

ans.append(''.join(S))

return

dfs(S, i + 1, n)

if not S[i].isalpha(): return

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(S, i + 1, n)

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(list(S), 0, len(S))

return ans

Posts published in “Search”

花花酱 LeetCode 818. Race Car

Problem

Visualization of the Solution

Solution 1: BFS

C++/Str

C++/Int

Solution 2: DP O(TlogT)

C++

Solution 3: DP O(T^2)

C++

C++/opt

Java

花花酱 LeetCode 815. Bus Routes

Problem

Solution: BFS

花花酱 LeetCode 805. Split Array With Same Average

Problem

Solution: Search

花花酱 LeetCode 803. Bricks Falling When Hit

Problem

Idea

Solution: DFS

C++

Java

Related Problems

花花酱 LeetCode 784. Letter Case Permutation

Solution 1: DFS

C++

Java

Python 3