Huahua’s Tech Road

花花酱 LeetCode 2770. Maximum Number of Jumps to Reach the Last Index

By zxi on July 11, 2023

You are given a 0-indexed array nums of n integers and an integer target.

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target

Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

Example 1:

Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3.

Example 2:

Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5.

Example 3:

Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.

Constraints:

2 <= nums.length == n <= 1000
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Solution: DP

Let dp(i) denotes the maximum jumps from index i to index n-1.

For each index i, try jumping to all possible index j.

dp(i) = max(1 + dp(j)) if j > i and abs(nums[j] – nums[i) <= target else -1

Time complexity: O(n²)
Space complexity: O(n)

Python3

# Author: Huahua

class Solution:

def maximumJumps(self, nums: List[int], target: int) -> int:

n = len(nums)

@cache

def dp(i):

if i == n - 1: return 0

ans = -1

for j in range(i + 1, n):

if abs(nums[j] - nums[i]) <= target and dp(j) != -1:

ans = max(ans, 1 + dp(j))

return ans

return dp(0)

花花酱 LeetCode 2769. Find the Maximum Achievable Number

By zxi on July 11, 2023

You are given two integers, num and t.

An integer x is called achievable if it can become equal to num after applying the following operation no more than t times:

Increase or decrease x by 1, and simultaneously increase or decrease num by 1.

Return the maximum possible achievable number. It can be proven that there exists at least one achievable number.

Example 1:

Input: num = 4, t = 1
Output: 6
Explanation: The maximum achievable number is x = 6; it can become equal to num after performing this operation:
1- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5. 
It can be proven that there is no achievable number larger than 6.

Example 2:

Input: num = 3, t = 2
Output: 7
Explanation: The maximum achievable number is x = 7; after performing these operations, x will equal num: 
1- Decrease x by 1, and increase num by 1. Now, x = 6 and num = 4.
2- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
It can be proven that there is no achievable number larger than 7.

Constraints:

1 <= num, t <= 50

Solution: Greedy

Always decrease x and always increase num, the max achievable number x = num + t * 2

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int theMaximumAchievableX(int num, int t) {

return num + t * 2;

}

};

花花酱 LeetCode 2666. Allow One Function Call

By zxi on May 7, 2023

Given a function fn, return a new function that is identical to the original function except that it ensures fn is called at most once.

The first time the returned function is called, it should return the same result as fn.
Every subsequent time it is called, it should return undefined.

Example 1:

Input: fn = (a,b,c) => (a + b + c), calls = [[1,2,3],[2,3,6]]
Output: [{"calls":1,"value":6}]
Explanation:
const onceFn = once(fn);
onceFn(1, 2, 3); // 6
onceFn(2, 3, 6); // undefined, fn was not called

Example 2:

Input: fn = (a,b,c) => (a * b * c), calls = [[5,7,4],[2,3,6],[4,6,8]]
Output: [{"calls":1,"value":140}]
Explanation:
const onceFn = once(fn);
onceFn(5, 7, 4); // 140
onceFn(2, 3, 6); // undefined, fn was not called
onceFn(4, 6, 8); // undefined, fn was not called

Constraints:

1 <= calls.length <= 10
1 <= calls[i].length <= 100
2 <= JSON.stringify(calls).length <= 1000

Solution:

JavaScript

// Author: Huahua

/**

* @param {Function} fn

* @return {Function}

var once = function(fn) {

this.called = false;

return function(...args){

if (this.called === false) {

this.called = true;

return fn(...args);

} else {

return undefined;

}

};

花花酱 LeetCode 2667. Create Hello World Function

By zxi on May 7, 2023

Write a function createHelloWorld. It should return a new function that always returns "Hello World".

Example 1:

Input: args = []
Output: "Hello World"
Explanation:
const f = createHelloWorld();
f(); // "Hello World"
The function returned by createHelloWorld should always return "Hello World".

Example 2:

Input: args = [{},null,42]
Output: "Hello World"
Explanation:
const f = createHelloWorld();
f({}, null, 42); // "Hello World"
Any arguments could be passed to the function but it should still always return "Hello World".

Constraints:

0 <= args.length <= 10

Solution:

JavaScript

// Author: Huahua

/**

* @return {Function}

var createHelloWorld = function() {

return function(...args) {

return "Hello World";

}

};

花花酱 LeetCode 2662. Minimum Cost of a Path With Special Roads

By zxi on April 30, 2023

You are given an array start where start = [startX, startY] represents your initial position (startX, startY) in a 2D space. You are also given the array target where target = [targetX, targetY] represents your target position (targetX, targetY).

The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|.

There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1_i, y1_i, x2_i, y2_i, cost_i] indicates that the i^th special road can take you from (x1_i, y1_i) to (x2_i, y2_i) with a cost equal to cost_i. You can use each special road any number of times.

Return the minimum cost required to go from (startX, startY) to (targetX, targetY).

Example 1:

Input: start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
Output: 5
Explanation: The optimal path from (1,1) to (4,5) is the following:
- (1,1) -> (1,2). This move has a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) -> (3,3). This move uses the first special edge, the cost is 2.
- (3,3) -> (3,4). This move has a cost of |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5). This move uses the second special edge, the cost is 1.
So the total cost is 1 + 2 + 1 + 1 = 5.
It can be shown that we cannot achieve a smaller total cost than 5.

Example 2:

Input: start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
Output: 7
Explanation: It is optimal to not use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.

Constraints:

start.length == target.length == 2
1 <= startX <= targetX <= 10⁵
1 <= startY <= targetY <= 10⁵
1 <= specialRoads.length <= 200
specialRoads[i].length == 5
startX <= x1_i, x2_i <= targetX
startY <= y1_i, y2_i <= targetY
1 <= cost_i <= 10⁵

Solution: Dijkstra

Create a node for each point in special edges as well as start and target.
Add edges for special roads (note it’s directional)
Add edges for each pair of node with default cost, i.e. |x1-x2| + |y1-y2|
Run Dijkstra’s algorithm

Time complexity: O(n²logn)
Space complexity: O(n²)

C++

// Author: Huahua

class Solution {

public:

int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {

unordered_map<long, int> ids;

vector<pair<int, int>> pos;

auto getId = [&](int x, int y) {

const auto key = ((unsigned long)x << 32) | y;

if (ids.count(key)) return ids[key];

const int id = ids.size();

ids[key] = id;

pos.emplace_back(x, y);

return id;

};

const int s = getId(start[0], start[1]);

const int t = getId(target[0], target[1]);

vector<vector<pair<int, int>>> g;

auto addEdge = [&](int x1, int y1, int x2, int y2, int c = INT_MAX) {

int n1 = getId(x1, y1);

int n2 = getId(x2, y2);

if (n1 == n2) return;

while (g.size() <= max(n1, n2)) g.push_back({});

int cost = min(c, abs(x1 - x2) + abs(y1 - y2));

g[n1].emplace_back(cost, n2);

// directional for special edge

if (c == INT_MAX) g[n2].emplace_back(cost, n1);

};

for (const auto& r : specialRoads)

addEdge(r[0], r[1], r[2], r[3], r[4]);

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

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

addEdge(pos[i].first, pos[i].second,

pos[j].first, pos[j].second);

vector<int> dist(ids.size(), INT_MAX);

dist[s] = 0;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

q.emplace(0, s);

while (!q.empty()) {

auto [d, u] = q.top(); q.pop();

if (d > dist[u]) continue;

if (u == t) return d;

for (auto [c, v] : g[u])

if (d + c < dist[v])

q.emplace(dist[v] = d + c, v);

}

return -1;

}

};

Huahua's Tech Road

花花酱 LeetCode 2770. Maximum Number of Jumps to Reach the Last Index

Solution: DP

Python3

花花酱 LeetCode 2769. Find the Maximum Achievable Number

Solution: Greedy

C++

花花酱 LeetCode 2666. Allow One Function Call

JavaScript

花花酱 LeetCode 2667. Create Hello World Function

JavaScript

花花酱 LeetCode 2662. Minimum Cost of a Path With Special Roads

Solution: Dijkstra

C++