KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 = 2 + 3


Example 2:

Input: n = 9
Output: 3
Explanation: 9 = 4 + 5 = 2 + 3 + 4


Example 3:

Input: n = 15
Output: 4
Explanation: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5


Constraints:

* 1 <= n <= 10<sup>9</sup>

题目大意：

求连续整数的和等于N的个数

解题思路：

只有Fintech考，数学题。思路见注释

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
# x, x+1, ... , x+k-1
# (x + x+k-1) * k / 2 = 2x+k-1) = n, x = [n - k(k-1)/2]/k
def consecutiveNumbersSum(self, n: int) -> int:
	res = 1
	for i in range(2, int(math.sqrt(2 * n) + 1)):
		if (n - i * (i - 1) / 2) % i == 0:
			res += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Posted on Edited on Disqus:

LeetCode



Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.


Example 2:

Input: nums = [2,3,0,1,4]
Output: 2


Constraints:

1 <= nums.length <= 10<sup>4</sup> 0 <= nums[i] <= 1000

题目大意：

N/A

解题思路：

BFS，但不需要用queue

解题步骤：

N/A

注意事项：

  1. end, next_end分别表示该层和下一层的边界，end从0开始，表示第0个数是第一层，遍历每个数，从0开始。
  2. 这个边界是inclusive的，所以当i==end时候，不应该res加1，是下一轮循环才是下一层的开始。有两种实现，我的实现是第一种，标准答案是遍历到最后一个数的前一个，因为最后一个数已经是目标，所以不需要计算next_end，更不需要层数+1。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def jump2(self, nums: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	update_end = False
	for i in range(len(nums)):
		if update_end:
			res += 1
			update_end = False
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
			update_end = True
	return res

Python代码：

1
2
3
4
5
6
7
8
9
def jump(self, nums: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	for i in range(len(nums) - 1):
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
			res += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Posted on Edited on Disqus:

LeetCode



You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.


Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.


Constraints:

1 <= nums.length <= 10<sup>4</sup> 0 <= nums[i] <= 10<sup>5</sup>

题目大意：

N/A

解题思路：

BFS，但不需要用queue

解题步骤：

N/A

注意事项：

  1. 参考Jump game II，区别在于如果i <= end才更新，
  2. 返回next_end要大于等于(可以cover)最后一个元素下标

Python代码：

1
2
3
4
5
6
7
8
def canJump(self, nums: List[int]) -> bool:
	end, next_end = 0, 0
	for i in range(len(nums) - 1):
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
	return next_end >= len(nums) - 1

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Posted on Edited on Disqus:

LeetCode



There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:



Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]


Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.


Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3


Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2


Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1


Constraints:

1 <= n <= 10<sup>4</sup> ranges.length == n + 1
* 0 <= ranges[i] <= 100

题目大意：

用多少个水龙头覆盖整个花园

解题思路：

两个难点，此题类似于jump game，这一层某个水龙头浇到最远点的水龙头也就是这一层的水龙头，这是难点一。
难点二是跟jump game不同，这题可以往前跳，也就是如例子中，点2表示从1跳到3，因为它的范围是1. 所以要重新计算每个水龙头的起点=它的左半范围起点

解题步骤：

N/A

注意事项：

  1. 第一步转化成jump game，jump game每个数值都是长度。若左半范围起点小于等于0，所有这些水龙头归结到起点0，长度为i + ranges[i], 其余情况是ranges[i] * 2
  2. 完全用jump game的程序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def minTaps(self, n: int, ranges: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	nums = [0] * len(ranges)
	for i in range(len(ranges)):
		if i - ranges[i] <= 0:
			nums[0] = max(nums[0], ranges[i] + i)
		else:
			nums[i - ranges[i]] = max(nums[i - ranges[i]], ranges[i] * 2)

	for i in range(len(nums) - 1): # remember
		if i <= end:  # -3 <= 0
			next_end = max(next_end, i + nums[i])  # 3
		if i == end:
			end = next_end
			res += 1
	return res if next_end >= len(nums) - 1 else -1

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode



An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

void checkIn(int id, string stationName, int t) A customer with a card ID equal to id, checks in at the station stationName at time t.
A customer can only be checked into one place at a time. void checkOut(int id, string stationName, int t)
A customer with a card ID equal to id, checks out from the station stationName at time t. double getAverageTime(string startStation, string endStation)
Returns the average time it takes to travel from startStation to endStation. The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation. There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t<sub>1</sub> then checks out at time t<sub>2</sub>, then t<sub>1</sub> < t<sub>2</sub>. All events happen in chronological order.

Example 1:

Input
[“UndergroundSystem”,”checkIn”,”checkIn”,”checkIn”,”checkOut”,”checkOut”,”checkOut”,”getAverageTime”,”getAverageTime”,”checkIn”,”getAverageTime”,”checkOut”,”getAverageTime”]
[[],[45,”Leyton”,3],[32,”Paradise”,8],[27,”Leyton”,10],[45,”Waterloo”,15],[27,”Waterloo”,20],[32,”Cambridge”,22],[“Paradise”,”Cambridge”],[“Leyton”,”Waterloo”],[10,”Leyton”,24],[“Leyton”,”Waterloo”],[10,”Waterloo”,38],[“Leyton”,”Waterloo”]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, “Leyton”, 3);
undergroundSystem.checkIn(32, “Paradise”, 8);
undergroundSystem.checkIn(27, “Leyton”, 10);
undergroundSystem.checkOut(45, “Waterloo”, 15);  // Customer 45 “Leyton” -> “Waterloo” in 15-3 = 12
undergroundSystem.checkOut(27, “Waterloo”, 20);  // Customer 27 “Leyton” -> “Waterloo” in 20-10 = 10
undergroundSystem.checkOut(32, “Cambridge”, 22); // Customer 32 “Paradise” -> “Cambridge” in 22-8 = 14
undergroundSystem.getAverageTime(“Paradise”, “Cambridge”); // return 14.00000. One trip “Paradise” -> “Cambridge”, (14) / 1 = 14
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);    // return 11.00000. Two trips “Leyton” -> “Waterloo”, (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, “Leyton”, 24);
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);    // return 11.00000
undergroundSystem.checkOut(10, “Waterloo”, 38);  // Customer 10 “Leyton” -> “Waterloo” in 38-24 = 14
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);    // return 12.00000. Three trips “Leyton” -> “Waterloo”, (10 + 12 + 14) / 3 = 12


Example 2:

Input
[“UndergroundSystem”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”]
[[],[10,”Leyton”,3],[10,”Paradise”,8],[“Leyton”,”Paradise”],[5,”Leyton”,10],[5,”Paradise”,16],[“Leyton”,”Paradise”],[2,”Leyton”,21],[2,”Paradise”,30],[“Leyton”,”Paradise”]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, “Leyton”, 3);
undergroundSystem.checkOut(10, “Paradise”, 8); // Customer 10 “Leyton” -> “Paradise” in 8-3 = 5
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, “Leyton”, 10);
undergroundSystem.checkOut(5, “Paradise”, 16); // Customer 5 “Leyton” -> “Paradise” in 16-10 = 6
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, “Leyton”, 21);
undergroundSystem.checkOut(2, “Paradise”, 30); // Customer 2 “Leyton” -> “Paradise” in 30-21 = 9
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667


Constraints:

1 <= id, t <= 10<sup>6</sup> 1 <= stationName.length, startStation.length, endStation.length <= 10
All strings consist of uppercase and lowercase English letters and digits. There will be at most 2 * 10<sup>4</sup> calls in total to checkIn, checkOut, and getAverageTime.
* Answers within 10<sup>-5</sup> of the actual value will be accepted.

题目大意：

求两站之间的平均时间。checkin和checkout都会发生，一个人不能连续checkin两次。站都是按先到后。

解题思路：

用两个Map来记录customer id -> 站台和时间，另一个记录起始站pair -> 总距离多少trip pair

解题步骤：

N/A

注意事项：

  1. collections.defaultdict(lambda: [0, 0]) 用于value是pair

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(TestCases):

    def __init__(self):
        self.start_to_end_time = {}
        self.start_end_to_total = collections.defaultdict(lambda: [0, 0])  # cant use defaultdict

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.start_to_end_time[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        if id not in self.start_to_end_time:
            return
        (start_station, start_time) = self.start_to_end_time[id]
        total, n_trips = self.start_end_to_total[(start_station, stationName)]
        total += t - start_time
        n_trips += 1
        self.start_end_to_total[(start_station, stationName)] = (total, n_trips)

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total, n_trips = self.start_end_to_total[(startStation, endStation)]
        return total / n_trips

算法分析：

时间复杂度为O(1)，空间复杂度O(n)

Free mock interview