KK's blog

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i<sup>th</sup> line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

n == height.length 2 <= n <= 10<sup>5</sup>
* 0 <= height[i] <= 10<sup>4</sup>

1
2
3
4
5
6
7
8
9
10

def maxArea(self, height: List[int]) -> int:
	res = 0
	i, j = 0, len(height) - 1
	while i < j:
		res = max(res, min(height[i], height[j]) * (j - i))
		if height[i] < height[j]:
			i += 1
		else:
			j -= 1
	return res

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job.
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job.
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

`1 <= startTime.length == endTime.length == profit.length <= 5 10<sup>4</sup>*1 <= startTime[i] < endTime[i] <= 10<sup>9</sup>*1 <= profit[i] <= 10<sup>4</sup>`

dp[i] = max -> dp[j] + profits[i-1]), 第i个job的startTime[i-1] >= endTime[j], 第j个job与第i个job没有conflicts
            -> dp[j]                                                          第j个job与第i个job有conflicts

dp[i] = max -> dp[j] + profits[i-1]), j = start[i-1]对应的Endtime下标, 第j个job与第i个job没有conflicts
            -> dp[j]                                                   第j个job与第i个job有conflicts

1
2
3
4
5
6
7
8
9
10
11
12

def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
	# dp[i] = max{d[j] + profit[i], dp[i-1]}
	schedules = []
	for i in range(len(profit)):
		schedules.append((endTime[i], startTime[i], profit[i]))
	schedules.sort()
	end_times = [pair[0] for pair in schedules]
	dp = [0] * (len(schedules) + 1)
	for i in range(1, len(dp)):
		j = bisect.bisect(end_times, schedules[i-1][1])
		dp[i] = max(dp[j] + schedules[i-1][2], dp[i-1])
	return dp[-1]

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3. For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object. void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10<sup>-5</sup> of the actual answer will be accepted.

Example 1:

Input
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints: -10<sup>5</sup> <= num <= 10<sup>5</sup>
There will be at least one element in the data structure before calling findMedian. At most 5 * 10<sup>4</sup> calls will be made to addNum and findMedian.

Follow up:

If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

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

class MedianFinder(TestCases):

    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.max_heap, -num)
        max_value = -heapq.heappop(self.max_heap)
        heapq.heappush(self.min_heap, max_value)
        if len(self.min_heap) - len(self.max_heap) >= 2:
            min_value = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -min_value)

    def findMedian(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return self.min_heap[0]

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group’s length is 1, append the character to s. Otherwise, append the character followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”2”,”b”,”2”,”c”,”3”]
Explanation: The groups are “aa”, “bb”, and “ccc”. This compresses to “a2b2c3”.

Example 2:

Input: chars = [“a”]
Output: Return 1, and the first character of the input array should be: [“a”]
Explanation: The only group is “a”, which remains uncompressed since it’s a single character.

Example 3:

Input: chars = [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”]
Output: Return 4, and the first 4 characters of the input array should be: [“a”,”b”,”1”,”2”].
Explanation: The groups are “a” and “bbbbbbbbbbbb”. This compresses to “ab12”.

Example 4:

Input: chars = [“a”,”a”,”a”,”b”,”b”,”a”,”a”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”3”,”b”,”2”,”a”,”2”].
Explanation: The groups are “aaa”, “bb”, and “aa”. This compresses to “a3b2a2”. Note that each group is independent even if two groups have the same character.

Constraints:

1 <= chars.length <= 2000 chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

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

def compress(self, chars: List[str]) -> int:
	res, count = 1, 1
	for i in range(1, len(chars)):
		if chars[i - 1] == chars[i]:
			count += 1
		else:
			if count > 1:
				res = self.populate_count(chars, res, count)
			count = 1
			chars[res] = chars[i]
			res += 1
	if count > 1:
		res = self.populate_count(chars, res, count)
	return res

def populate_count(self, chars, res, count):
	num_str = str(count)
	chars[res:res + len(num_str)] = [c for c in num_str]
	res += len(num_str)
	return res

Give a binary string s, return the number of non-empty substrings that have the same number of 0‘s and 1‘s, and all the 0‘s and all the 1‘s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: s = “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.

Example 2:

Input: s = “10101”
Output: 4
Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.

Constraints:

1 <= s.length <= 10<sup>5</sup> s[i] is either '0' or '1'.

1
2
3
4
5
6
7
8
9
10
11
12
13

def countBinarySubstrings(self, s: str) -> int:
	presum, count, res = [], 1, 0
	for i in range(1, len(s)): #
		if s[i - 1] == s[i]:
			count += 1
		else:
			presum.append(count) #[2, 2,2,2]
			count = 1
	if count > 0:
		presum.append(count)
	for i in range(1, len(presum)):
		res += min(presum[i - 1], presum[i])
	return res