KK's blog

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>

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

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

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

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

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:

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.

Example 2:

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.

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.

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)

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.

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

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Example 1:

Input: s = “3[a]2[bc]”
Output: “aaabcbc”

Example 2:

Input: s = “3[a2[c]]”
Output: “accaccacc”

Example 3:

Input: s = “2[abc]3[cd]ef”
Output: “abcabccdcdcdef”

Example 4:

Input: s = “abc3[cd]xyz”
Output: “abccdcdcdxyz”

Constraints:

1 <= s.length <= 30 s consists of lowercase English letters, digits, and square brackets '[]'.
s is guaranteed to be a valid input. All the integers in s are in the range [1, 300].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def decodeString(self, s: str) -> str:
	res, num, stack_num, stack_str = '', 0, [], []
	for char in s:
		if char.isdigit():
			num = num * 10 + int(char)
		if char.isalpha():
			res += char
		if char == '[':
			stack_num.append(num) # [3]
			stack_str.append(res) # 2c
			num = 0
			res = ''
		if char == ']':
			tmp = stack_str.pop() # '2c'
			n = stack_num.pop() # 3
			res = tmp + n * res # 2c + 3*d=ccddd
	return res

1
2
3
4
5
6
7
8

decodeString('3[a2[c]]')
    k = 3  
    acc = decodeString('a2[c]')
         result = a
         k = 2
         'c'  = decodeString('c')
         result = acc
   result = accaccacc