KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>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. </pre>

Constraints:

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

</div>

题目大意：

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

<div>

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:

<pre>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] </pre>

Example 2:

<pre>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. </pre>

Example 3:

<pre>Input: n = 7, ranges = [1,2,1,0,2,1,0,1] Output: 3 </pre>

Example 4:

<pre>Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4] Output: 2 </pre>

Example 5:

<pre>Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4] Output: 1 </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

两个难点，此题类似于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

<div>

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:

<pre>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 </pre>

Example 2:

<pre>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 </pre>

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.

</div>

题目大意：

求两站之间的平均时间。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)

Posted on Edited on Disqus:

LeetCode

<div>

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i<sup>th</sup> index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

  • For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

Example 1:

<pre>Input ["Solution","pickIndex"] [[[1]],[]] Output [null,0]

Explanation Solution solution = new Solution([1]); solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w. </pre>

Example 2:

<pre>Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0]

Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed. All of the following outputs can be considered correct: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... and so on. </pre>

Constraints:

  • 1 <= w.length <= 10<sup>4</sup>
  • 1 <= w[i] <= 10<sup>5</sup>
  • pickIndex will be called at most 10<sup>4</sup> times.

</div>

题目大意：

根据数组每个元素的weight来决定其出现的概率： weight/sum of weight

解题思路：

模拟运算过程，先求和，然后根据上述公式分配概率： 如[1, 3], 小于0.25属于第一个元素，大于属于后一个元素，我们不用小数，还原回整数
所以数值小于1属于第一个元素，大于1小于4属于后一个，想到用presum，然后在presum搜索某个value，就想到二分法。

解题步骤：

N/A

注意事项：

  1. random.randint前闭后闭

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(TestCases):

    def __init__(self, w: List[int]):
        self.presum = []
        sum = 0
        for n in w:
            sum += n
            self.presum.append(sum)

    def pickIndex(self) -> int:
        rand_value = random.randint(0, self.presum[-1] - 1)
        return bisect.bisect(self.presum, rand_value)

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

<pre>Input: strs = ["flower","flow","flight"] Output: "fl" </pre>

Example 2:

<pre>Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. </pre>

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

</div>

题目大意：

字符串列表的最长前缀

算法思路：

N/A

注意事项：

  1. 求最小值len初始值用最大值而不是0
  2. char = strs[0][i]而不是char = strs[i]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestCommonPrefix(self, strs: List[str]) -> str:
	min_len, res = sys.maxsize, ''
	for s in strs:
		min_len = min(min_len, len(s))
	for i in range(min_len):
		char = strs[0][i]
		same_char = True
		for j in range(1, len(strs)):
			if char != strs[j][i]:
				same_char = False
				break
		if not same_char:
			break
		res += char
	return res

算法分析：

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

Free mock interview