花花酱 LeetCode 937. Reorder Log Files

By zxi on November 10, 2018

Problem

https://leetcode.com/problems/reorder-log-files/description/

You have an array of logs. Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Note:

0 <= logs.length <= 100
3 <= logs[i].length <= 100
logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution: Partition + Sort

partition the array such that all digit logs are after all letter logs
sort the letter logs part based on the log content

Time complexity: O(n + aloga)

Space complexity: O(n)

C++

class Solution {

public:

vector<string> reorderLogFiles(vector<string>& logs) {

auto alpha_end = std::stable_partition(begin(logs), end(logs),

[](const string& log){ return isalpha(log.back()); });

std::sort(begin(logs), alpha_end, [](const string& a, const string& b){

return a.substr(a.find(' ')) < b.substr(b.find(' '));

});

return logs;

}

};

Knapsack Problem 背包问题

By zxi on November 10, 2018

Videos

上期节目中我们对动态规划做了一个总结，这期节目我们来聊聊背包问题。

背包问题是一个NP-complete的组合优化问题，Search的方法需要O(2^N)时间才能获得最优解。而使用动态规划，我们可以在伪多项式（pseudo-polynomial time）时间内获得最优解。

0-1 Knapsack Problem 0-1背包问题

Problem

Given N items, w[i] is the weight of the i-th item and v[i] is value of the i-th item. Given a knapsack with capacity W. Maximize the total value. Each item can be use 0 or 1 time.

0-1背包问题的通常定义是：一共有N件物品，第i件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够获得的最大价值是多少？每件物品可以使用0次或者1次。

例子：

重量 w = [1, 1, 2, 2]

价值 v = [1, 3, 4, 5]

背包承重 W = 4

最大价值为9，可以选第1,2,4件物品，也可以选第3，4件物品；总重量为4，总价值为9。

动态规划的状态转移方程为：

1	dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

Solutions

Search

def knapsack01DFS(w, v, W):

def dfs(s, cur_w, cur_v, ans):

ans[0] = max(ans[0], cur_v)

if s == N: return

for i in range(s, N):

if cur_w + w[i] <= W:

dfs(i + 1, cur_w + w[i], cur_v + v[i], ans)

ans = [0]

dfs(0, 0, 0, ans)

return ans[0]

DP2

def knapsack01(w, v, W):

dp = [[0] * (W + 1) for _ in range(N+1)]

for i in range(1, N + 1):

dp[i] = dp[i-1].clone()

for j in range(w[i], W + 1):

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])

return max(dp[N])

DP1/tmp

def knapsack01R(w, v, W):

dp = [0] * (W + 1)

for i in range(0, N):

tmp = list(dp)

for j in range(w[i], W + 1):

tmp[j] = max(tmp[j], dp[j - w[i]] + v[i])

dp = tmp

return max(dp)

DP1/push

def knapsack01R2(w, v, W):

dp = [0] * (W + 1)

for i in range(0, N):

for j in range(W, w[i] - 1, -1):

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

return max(dp)

DP1/pull

def knapsack01R1(w, v, W):

dp = [0] * (W + 1)

for i in range(0, N):

for j in range(W - w[i], -1, -1):

dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i])

return max(dp)

Unbounded Knapsack Problem 完全背包

完全背包、多重背包是常见的变形。和01背包的区别在于，完全背包每件物品可以使用无限多次，而多重背包每件物品最多可以使用n[i]次。两个问题都可以转换成01背包问题进行求解。

但是Naive的转换会大大增加时间复杂度：

完全背包：“复制”第i件物品到一共有 W/w[i] 件

多重背包：“复制”第i件物品到一共有 n[i] 件

然后直接调用01背包进行求解。

时间复杂度：

完全背包 O(Σ(W/w[i])*W)

多重背包 O(Σn[i]*W)

不难看出时间复杂度 = O(物品数量*背包承重)

背包承重是给定的，要降低运行时候，只有减少物品数量。但怎样才能减少总的物品数量呢？

这就涉及到二进制思想：任何一个正整数都可以用 (1, 2, 4, …, 2^K)的组合来表示。例如14 = 2 + 4 + 8。
原本需要放入14件相同的物品，现在只需要放入3件（重量和价值是原物品的2倍，4倍，8倍）。大幅降低了总的物品数量从而降低运行时间。

完全背包：对于第i件物品，我们只需要创建k = log(W/w[i])件虚拟物品即可。

每件虚拟物品的重量和价值为：1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^k*(w[i], v[i])。

多重背包：对于第i件物品，我们只需要创建k + 1件虚拟物品即可，其中k = log(n[i])。

每件虚拟物品的重量和价值为：1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^(k-1)*(w[i], v[i]), 以及 (n[i] – 2^k – 1) * (w[i], v[i])。

例如：n[i] = 14, k = 3, 虚拟物品的倍数为 1, 2, 4 和 7，这4个数组合可以组成1 ~ 14中的任何一个数，并且不会>14，即不超过n[i]。

二进制转换后直接调用01背包即可

时间复杂度：

完全背包 O(Σlog(W/w[i])*W)

多重背包 O(Σlog(n[i])*W)

空间复杂度 O(W)

其实完全背包和多重背包都可以在 O(NW)时间内完成，前者在视频中有讲到，后者属于超纲内容，以后有机会再和大家深入分享。

Bounded Knapsack Problem 多重背包

花花酱 LeetCode 648. Replace Words

By zxi on November 8, 2018

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

// Author: Huahua, Running time: 84 ms

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

unordered_set<string> d(begin(dict), end(dict));

sentence.push_back(' ');

string output;

string word;

bool found = false;

for (char c : sentence) {

if (c == ' ') {

if (!output.empty()) output += ' ';

output += word;

word = "";

found = false;

continue;

}

if (found) continue;

word += c;

if (d.count(word)) {

found = true;

}

return output;

}

};

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)

// Author: Huahua, running time: 48 ms

class TrieNode {

public:

TrieNode(): children(26), is_word(false) {}

~TrieNode() {

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

if (children[i]) {

delete children[i];

children[i] = nullptr;

}

vector<TrieNode*> children;

bool is_word;

};

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

TrieNode root;

for (const string& word : dict) {

TrieNode* cur = &root;

for (char c : word) {

if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();

cur = cur->children[c - 'a'];

}

cur->is_word = true;

}

string ans;

stringstream ss(sentence);

string word;

while (ss >> word) {

TrieNode* cur = &root;

bool found = false;

int len = 0;

for (char c : word) {

cur = cur->children[c - 'a'];

if (!cur) break;

++len;

if (cur->is_word) {

found = true;

break;

}

if (!ans.empty()) ans += ' ';

ans += found ? word.substr(0, len) : word;

}

return ans;

}

};

花花酱 LeetCode 935. Knight Dialer

By zxi on November 4, 2018

Problem

https://leetcode.com/problems/knight-dialer/description/

A chess knight can move as indicated in the chess diagram below:

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops. Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example 1:

Input: 1
Output: 10

Example 2:

Input: 2
Output: 20

Example 3:

Input: 3
Output: 46

Note:

1 <= N <= 5000

Solution: DP

V1

We can define dp[k][i][j] as # of ways to dial and the last key is (j, i) after k steps

Note: dp[*][3][0], dp[*][3][2] are always zero for all the steps.

Init: dp[0][i][j] = 1

Transition: dp[k][i][j] = sum(dp[k – 1][i + dy][j + dx]) 8 ways of move from last step.

ans = sum(dp[k])

Time complexity: O(kmn) or O(k * 12 * 8) = O(k)

Space complexity: O(kmn) -> O(mn) or O(12*8) = O(1)

V2

define dp[k][i] as # of ways to dial and the last key is i after k steps

init: dp[0][0:10] = 1

transition: dp[k][i] = sum(dp[k-1][j]) that j can move to i

ans: sum(dp[k])

Time complexity: O(k * 10) = O(k)

Space complexity: O(k * 10) -> O(10) = O(1)

C++ V1

// Author: Huahua, 96 ms

class Solution {

public:

int knightDialer(int N) {

constexpr int kMod = 1e9 + 7;

int dirs[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};

vector<vector<int>> dp(4, vector<int>(3, 1));

dp[3][0] = dp[3][2] = 0;

for (int k = 1; k < N; ++k) {

vector<vector<int>> tmp(4, vector<int>(3));

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

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

if (i == 3 && j != 1) continue;

for (int d = 0; d < 8; ++d) {

int tx = j + dirs[d][0];

int ty = i + dirs[d][1];

if (tx < 0 || ty < 0 || tx >= 3 || ty >= 4) continue;

tmp[i][j] = (tmp[i][j] + dp[ty][tx]) % kMod;

}

dp.swap(tmp);

}

int ans = 0;

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

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

ans = (ans + dp[i][j]) % kMod;

return ans;

}

};

C++ V2

// Author: Huahua, 24 ms

public:

int knightDialer(int N) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> moves{{4,6},{8,6},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4}};

vector<int> dp(10, 1);

for (int k = 1; k < N; ++k) {

vector<int> tmp(10);

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

for (int nxt : moves[i])

tmp[nxt] = (tmp[nxt] + dp[i]) % kMod;

dp.swap(tmp);

}

int ans = 0;

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

ans = (ans + dp[i]) % kMod;

return ans;

}

};

Problem

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:

Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]

Note:

Each test case will have at most 10000 calls to ping.
Each test case will call ping with strictly increasing values of t.
Each call to ping will have 1 <= t <= 10^9.

Solution: Queue

Use a FIFO queue to track all the previous pings that are within 3000 ms to current.

Time complexity: Avg O(1), Total O(n)

Space complexity: O(n)

C++

class RecentCounter {

public:

RecentCounter() {}

int ping(int t) {

while (!q.empty() && t - q.front() > 3000) q.pop();

q.push(t);

return q.size();

}

private:

queue<int> q;

};

花花酱 LeetCode 937. Reorder Log Files

Problem

Solution: Partition + Sort

C++

Knapsack Problem 背包问题

Videos

0-1 Knapsack Problem 0-1背包问题

Problem

Solutions

Search

DP2

DP1/tmp

DP1/push

DP1/pull

Unbounded Knapsack Problem 完全背包

Bounded Knapsack Problem 多重背包

花花酱 LeetCode 648. Replace Words

Problem

Solution 1: HashTable

Solution2: Trie

花花酱 LeetCode 935. Knight Dialer

Problem

Solution: DP

V1

V2

C++ V1

C++ V2

Related Problem

花花酱 LeetCode 933. Number of Recent Calls

Problem

Solution: Queue

C++

Huahua's Tech Road

花花酱 LeetCode 937. Reorder Log Files

Problem

Solution: Partition + Sort

C++

Knapsack Problem 背包问题

Videos

0-1 Knapsack Problem 0-1背包问题

Problem

Solutions

Search

DP2

DP1/tmp

DP1/push

DP1/pull

Unbounded Knapsack Problem 完全背包

Bounded Knapsack Problem 多重背包

花花酱 LeetCode 648. Replace Words

Problem

Solution 1: HashTable

Solution2: Trie

花花酱 LeetCode 935. Knight Dialer

Problem

Solution: DP

V1

V2

C++ V1

C++ V2

Related Problem

花花酱 LeetCode 933. Number of Recent Calls

Problem

Solution: Queue

C++