0%

By Long Luo

This article is the solution Pattern of Data Pairs Problem: Sorting First then Greedy of Problem 406. Queue Reconstruction by Height.

Intuition

The Data Pair people[h,k]\textit{people}[h, k], hih_i represents the i-th person of height hih_i, kik_i represents the other people in front who have a height greater than or equal to hih_i.

Pattern:

When face such kind of problem with Data Pair, sorting first will simplify the problem.

Usually, we will sort the first element in ascending order, while the second element in descending order, or sort the first element in descending order with the second element in ascending order.

Greedy

We sort the people\textit{people} pairs first by heightheight in descending order, and kk in ascending order.

According to the descending order of heightheight, for each person, the number of people before him is the number of people whose height is greater than or equal to him.

According to the ascending order of kk, because the kk is increase later, which can reduce the number of insert operations.

Take the example:

After sorting:

1
[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]

Insert one by one:

1
2
3
4
5
6
[7,0]
[7,0], [7,1]
[7,0], [6,1], [7,1]
[5,0], [7,0], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
阅读全文 »

By Long Luo

This article is the solution 3 Approaches: Sorting, Priority Queue, Divide and Conquer of Problem 215. Kth Largest Element in an Array.

Here shows 3 Approaches to slove this problem: Sorting, Priority Queue, Divide and Conquer.

Sort

Sort the array first, then the k-th element.

1
2
3
4
5
6
7
8
9
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}

int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn).
  • Space Complexity: O(logn)O(logn).
阅读全文 »

By Long Luo

This article is the solution Priority Queue + Greedy: Consider Ladder as a One-time Unlimited Bricks of Problem 1642. Furthest Building You Can Reach.

Intuition

While we are moving, we will need to use bricks or ladders several times. Suppose we have to move to the next building, which means we must use one ladder or Δh\Delta h bricks, so there is a question, whether to use ladders or bricks?

If the gap of buildings is large, we may use the ladder, otherwise we use the bricks.

We can consider ladder as a one-time unlimited number of bricks, That is, if we have l ladders, we will use the ladder on the ll times where Δh\Delta h is the largest, and use the bricks in the rest.

Therefore, we got the answer. We maintain no more than ll largest Δh\Delta h using priority queues, and these are where the ladders are used. For the remaining Δh\Delta h, we need to use bricks, so we need to accumulate them, if the sumsum exceeds the number of bricks bb, then we have move to the furthest building.

The code is as follows:

阅读全文 »

By Long Luo

This article is the solution 3 Approaches: DFS, BFS, DP of Problem 322. Coin Change.

Here shows 3 Approaches to slove this problem: DFS, BFS and Dynamic Programming.

DFS

TLE!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
int minCount = Integer.MAX_VALUE;

public int coinChange(int[] coins, int amount) {
if (amount <= 0) {
return 0;
}

minCount = Integer.MAX_VALUE;
dfs(coins, amount, 0);
return minCount == Integer.MAX_VALUE ? -1 : minCount;
}

private int dfs(int[] coins, int remain, int count) {
if (remain < 0) {
return -1;
}

if (remain == 0) {
minCount = Math.min(minCount, count);
return count;
}

for (int x : coins) {
dfs(coins, remain - x, count + 1);
}

return -1;
}
}

Sorting the array first, then use DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
int minAns = Integer.MAX_VALUE;

public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
minAns = Integer.MAX_VALUE;
coinChange(coins, amount, coins.length - 1, 0);
return minAns == Integer.MAX_VALUE ? -1 : minAns;
}

private void coinChange(int[] coins, int amount, int index, int cnt) {
if (amount == 0) {
minAns = Math.min(minAns, cnt);
return;
}

if (index < 0) {
return;
}

for (int k = amount / coins[index]; k >= 0 && k + cnt < minAns; k--) {
coinChange(coins, amount - k * coins[index], index - 1, cnt + k);
}
}
}

Memory DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount <= 0) {
return 0;
}

return coinChange(coins, amount, new int[amount]);
}

private int coinChange(int[] coins, int rem, int[] count) {
if (rem < 0) {
return -1;
}

if (rem == 0) {
return 0;
}

if (count[rem - 1] != 0) {
return count[rem - 1];
}

int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, rem - coin, count);
if (res >= 0 && res < min) {
min = 1 + res;
}
}
count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[rem - 1];
}
}

Analysis

  • Time Complexity: O(amount * n)
  • Space Complexity: O(amount)
阅读全文 »

By Long Luo

This article is the solution DP: Top-Down and Bottom-Up Approach of Problem 120. Triangle.

Intuition

This problem is a classic and typical dynamic programming problem. We can break the large problem into sub-problems.

We can use both the Top-Down and Bottom-Up approach to solve this problem.

Top-Down Approach

  1. State definition:

dp[i][j]dp[i][j] represents the minimum path sum of row ii and column jj.

  1. State Analysis:

dp[0][0]=c[0][0]dp[0][0]=c[0][0]

  1. The State Transfer Equation:

dp[i][j]={dp[i1][0]+c[i][0]j=0dp[i1][i1]+c[i][i]j==imin(dp[i1][j1],dp[i1][j])+c[i][j]0<j<idp[i][j] = \begin{cases} dp[i-1][0] + c[i][0] & j=0 \\ dp[i-1][i-1] + c[i][i] & j==i \\ min(dp[i-1][j-1],dp[i-1][j]) + c[i][j] & 0 < j < i \\ \end{cases}

so we can easily write such code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}

int len = triangle.size();
int[][] dp = new int[len][len];
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < len; i++) {
dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
for (int j = 1; j < i; j++) {
dp[i][j] = Math.min(dp[i - 1][j - 1] + triangle.get(i).get(j), dp[i - 1][j] + triangle.get(i).get(j));
}
}

int min = dp[len - 1][0];
for (int i = 1; i < len; i++) {
min = Math.min(min, dp[len - 1][i]);
}

return min;
}

In fact, dp[i][j]dp[i][j] is only relevant to dp[i1][j]dp[i-1][j], but dp[i2][j]dp[i-2][j] and previous states are irrelevant, so we don’t have to store these states. We can only use extra O(2n)O(2n) space: two one-dimensional arrays of length nn for the transfer, and map ii to one of the one-dimensional arrays according to the parity, then i1i-1 is mapped to the other one-dimensional array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();
int[][] dp = new int[2][len];

dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < len; i++) {
int cur = i % 2;
int prev = 1 - cur;

dp[cur][0] = dp[prev][0] + triangle.get(i).get(0);
dp[cur][i] = dp[prev][i - 1] + triangle.get(i).get(i);
for (int j = 1; j < i; j++) {
dp[cur][j] = Math.min(dp[prev][j - 1], dp[prev][j]) + triangle.get(i).get(j);
}
}

int min = dp[(len - 1) % 2][0];
for (int i = 1; i < len; i++) {
min = Math.min(min, dp[(len + 1) % 2][i]);
}

return min;
}

We enumerate jj decreasingly from ii to 00, so that we only need a one-dimensional array dpdp of length nn to complete the state transition.

dp[j]=min(dp[j1],dp[j])+c[i][j]dp[j] = min(dp[j-1], dp[j]) + c[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();

int[] dp = new int[len];
dp[0] = triangle.get(0).get(0);

for (int i = 1; i < len; i++) {
dp[i] += dp[i - 1] + triangle.get(i).get(i);

for (int j = i - 1; j > 0; j--) {
dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
}

dp[0] += triangle.get(i).get(0);
}

int min = dp[0];
for (int i = 1; i < len; i++) {
min = Math.min(min, dp[i]);
}

return min;
}
阅读全文 »

By Long Luo

This article is the solution How to Maintain the Enqueued Tasks? | Sorting the array then Priority Queue | minHeap of Problem 1834. Single-Threaded CPU.

Intuition

To simulate the CPU operations, there comes 33 questions:

  1. Which task should int the enqueued tasks list?

  2. How to maintain the enqueued tasks?

  3. Which task of the enqueued tasks should the CPU choose?

Let’s answer the 33 questions:

  1. We assign the tasks to the CPU by enqueueTime\textit{enqueueTime}, so we sort the array first by enqueueTime\textit{enqueueTime}. However, we will lose the index\textit{index} of the task.

We can parse the task by creating a new class Job\texttt{Job}, whose members are id\textit{id}, enqueueTime\textit{enqueueTime}, processTime\textit{processTime}.

  1. We put all the tasks assigned to the CPU into a Priority Queue and poll out the task whose processTime\textit{processTime} is the least each time.

  2. We can maintain a curTime\textit{curTime} variable, which represents the current time with initial value is 00.

If the CPU has no tasks to execute, we set the curTime\textit{curTime} to enqueueTime\textit{enqueueTime} of the next task in the array that has not yet been assigned to the CPU.

After this, we put all enqueueTimecurTime\textit{enqueueTime} \le \textit{curTime} tasks into the Priority Queue.

阅读全文 »

By Long Luo

This article is the solution 4 Approaches: Brute Force, HashMap, Binary Search, Two Pointers of Problem 167. Two Sum II - Input Array Is Sorted.

Here shows 4 Approaches to slove this problem: Brute Force, HashMap, Binary Search, Two Pointers.

Brute Force

It’s easy to use Brute Force to find the answer, however, the time complexity is O(n2)O(n^2), so the BF solution will Time Limit Exceeded!

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] twoSum_bf(int[] numbers, int target) {
int len = numbers.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (numbers[i] + numbers[j] == target) {
return new int[]{i + 1, j + 1};
}
}
}

return new int[0];
}

Analysis

  • Time Complexity: O(n2)O(n^2).
  • Space Complexity: O(1)O(1).

HashMap

We can use a extra HashMap\texttt{HashMap} to record the element we traversalled.

阅读全文 »

By Long Luo

This article is the solution 3 Approaches: BFS, BFS + LinkedList, Recursion of Problem 440. K-th Smallest in Lexicographical Order.

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findKthNumber(int n, int k) {
if (n == 1) {
return 1;
}

String[] numStrs = new String[n + 1];
for (int i = 0; i <= n; i++) {
numStrs[i] = "" + i;
}

Arrays.sort(numStrs);

return Integer.parseInt(numStrs[k]);
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn).
  • Space Complexity: O(n)O(n).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. ???

By Long Luo

This article is the solution 5 Approaches: BF use Long, BF use Int, Binary Search use Long, Binary Search use Int, Recursion of Problem 29. Divide Two Integers , Chinese version is 3种方法:暴力法,二分搜索,递归 .

Here shows 5 Approaches to slove this problem: BF use long, BF use int, Binary Search use Long, Binary Search use Int, Recursion.

Intuition

To divide two integers without using multiplication, division, and mod operator, so we can subtract the divisor\textit{divisor} from the dividend\textit{dividend} util the result0\textit{result} \ge 0.

Brute Force use Long

We can make the dividend\textit{dividend} and divisor\textit{divisor} positive, and cast to long, then process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}

long dividendLong = dividend;
long divisorLong = divisor;

boolean sign = false;
if (dividendLong < 0 && divisorLong < 0) {
dividendLong = -dividendLong;
divisorLong = -divisorLong;
} else if (dividendLong < 0 && divisorLong > 0) {
sign = true;
dividendLong = -dividendLong;
} else if (dividendLong > 0 && divisorLong < 0) {
sign = true;
divisorLong = -divisorLong;
}

long ans = 0;
while (dividendLong >= divisorLong) {
dividendLong -= divisorLong;
ans++;
}

ans = sign ? -ans : ans;

return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

The solution will Time Limit Exceeded, we have to deal with some corner cases.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int divide(int dividend, int divisor) {
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}

if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return dividend;
} else if (divisor == -1) {
return Integer.MAX_VALUE;
}
} else if (dividend == Integer.MAX_VALUE) {
if (divisor == 1) {
return dividend;
} else if (divisor == -1) {
return -dividend;
}
}

long dividendLong = dividend;
long divisorLong = divisor;

boolean sign = false;
if (dividendLong < 0 && divisorLong < 0) {
dividendLong = -dividendLong;
divisorLong = -divisorLong;
} else if (dividendLong < 0 && divisorLong > 0) {
sign = true;
dividendLong = -dividendLong;
} else if (dividendLong > 0 && divisorLong < 0) {
sign = true;
divisorLong = -divisorLong;
}

long ans = 0;
while (dividendLong >= divisorLong) {
dividendLong -= divisorLong;
ans++;
}

ans = sign ? -ans : ans;

return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

Analysis

  • Time Complexity: O(x/y)O(x / y).
  • Space Complexity: O(1)O(1).
阅读全文 »

By Long Luo

微博热搜爬虫

前几天外甥女要我帮她完成一个小作业,用 Python 完成一个爬虫,于是在网上找了点资料[1] 和 Github 上找了个爬虫[2] 的例子,改简单了点,只爬取 微博热搜 数据并存储到 Excel 中,使用 Python Jupyter 编写。

具体代码见:https://github.com/longluo/spider/blob/master/weibohot.ipynb

微博爬虫

微博爬虫 [3] 的代码及功能太多太复杂,但我目前只需要爬取下列信息:

  1. 个人信息
  2. 具体时间段全部博文;
  3. 将数据存入 Excel 和数据库中。

所以需要精简其代码。

微博API

微博获取个人信息API:https://weibo.cn/1565668374/info

微博获取个人全部博文API:https://weibo.cn/1565668374?page=1

具体代码见:https://github.com/longluo/spider/blob/master/weibo.py

博客爬虫

在写完上述两个爬虫之后,趁热打铁,也把之前自己一直想做完的功能做完了!

功能

  1. 获取某网站的全部博文比如 http://www.longluo.me/
  2. 爬取内容:文章标题、发布时间、分类、链接、正文(HTML格式)等。
阅读全文 »