KK's blog

LeetCode 1200 Minimum Absolute Difference

Posted on 2026-06-30 Disqus:

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints: 2 <= arr.length <= 105
* -106 <= arr[i] <= 106

题目大意：

数组中求最小差值的所有数值pair，pair中按数值排序

解题思路：

其中一个例子是有序的，就联想到排序，然后遍历求最小插值并记录对应的结果

解题步骤：

N/A

注意事项：

N/A

Python代码：

def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
	arr.sort()
	min_diff, res = float('inf'), []
	for i in range(1, len(arr)):
		if arr[i] - arr[i-1] <= min_diff:
			if arr[i] - arr[i-1] < min_diff:
				res = []
				min_diff = arr[i] - arr[i-1]
			res.append([arr[i-1], arr[i]])
	return res

算法分析：

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

LeetCode 622 Design Circular Queue

Posted on 2026-06-30 Disqus:

LeetCode

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implement the MyCircularQueue class:

MyCircularQueue(k) Initializes the object with the size of the queue to be k. int Front() Gets the front item from the queue. If the queue is empty, return -1.
int Rear() Gets the last item from the queue. If the queue is empty, return -1. boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful. boolean isEmpty() Checks whether the circular queue is empty or not.
boolean isFull() Checks whether the circular queue is full or not.

You must solve the problem without using the built-in queue data structure in your programming language.

Example 1:

Input
[“MyCircularQueue”, “enQueue”, “enQueue”, “enQueue”, “enQueue”, “Rear”, “isFull”, “deQueue”, “enQueue”, “Rear”]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear(); // return 3
myCircularQueue.isFull(); // return True
myCircularQueue.deQueue(); // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear(); // return 4

Constraints: 1 <= k <= 1000
0 <= value <= 1000 At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

题目大意：

实现循环队列

解题思路Array(推荐)：

用两个指针为维持数据的开始和结束+1，由于循环队列，所以用mod来找到数组下标，也就是start和end一样时候，既可能是empty也可能是full，所以加一个变量记录

解题步骤：

用count就可以省去end和is_full两个变量
如果要实现同步队列，就引入self.queueLock = Lock(), with self.queueLock: 就进行enQueue操作

注意事项：

N/A

Python代码：

class MyCircularQueue:

    def __init__(self, k: int):
        self.data = [0] * k
        self.start = 0 # starting point of data
        self.end = 0 # ending point + 1 of data
        self.size = k
        self.is_full = False

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.end] = value
        self.end = (self.end + 1) % self.size
        if self.start == self.end:
            self.is_full = True
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.start = (self.start + 1) % self.size
        self.is_full = False
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[self.start]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.end - 1) % self.size]

    def isEmpty(self) -> bool:
        return not self.is_full and self.start == self.end

    def isFull(self) -> bool:
        return self.is_full

算法分析：

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

算法II解题思路Linked List：

比较简单，省略

算法分析：

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

LeetCode 761 Special Binary String

Posted on 2026-06-29 Edited on 2026-06-30 Disqus:

LeetCode

Special binary strings are binary strings with the following two properties:

The number of 0‘s is equal to the number of 1‘s. Every prefix of the binary string has at least as many 1‘s as 0‘s.

You are given a special binary string s.

A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.

Return the lexicographically largest resulting string possible after applying the mentioned operations on the string.

Example 1:

Input: s = “11011000”
Output: “11100100”
Explanation: The strings “10” [occuring at s[1]] and “1100” [at s[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.

Example 2:

Input: s = “10”
Output: “10”

Constraints:

1 <= s.length <= 50 s[i] is either '0' or '1'.
* s is a special binary string.

题目大意：

Special string由0和1组成，数目一样且每个前缀1的数目大于等于0的数目。可以交换其内部的子特别字符串，让其数值最大

解题思路：

一开始考虑用统计presum的方法LeetCode 696 Count Binary Substrings，然后如果后者1的数目大于前者0的数目，表示可以交换。但这里只考虑到相邻特别子串的关系，并没有考虑特别字串的内部也是需要排序的。

此题特别串是含有递归定义，所以考虑DFS。首先，一个特别字符串是由多个特别子串连续组成，所以需要找出它们，且进行排序
第二，更难的是每个字串内部特别字串也需要重新排序比如11011000中的10和1100就需要互换。这个串不是直接由内部特殊字串组成而是1+特殊串+0组成(递归式). 根据特殊串定义，是以1开头0结束，类似于统计左右括号数，这点规律比较难找。

总结而已，这题是catalan递归但不是递归两边是，多边。且每个递归都是由总结出来的规律获得1+f(s[start+1:i])获得

解题步骤：

N/A

注意事项：

如果遇到0，count要减一
倒序排序：parts.sort(reverse=True)

Python代码：

def makeLargestSpecial(self, s: str) -> str:
	parts = []
	count = 0
	start = 0
	for i in range(len(s)):
		if s[i] == '1':
			count += 1
		else:
			count -= 1 #attn
		if count == 0:
			sorted_part = '1'+ self.makeLargestSpecial(s[start+1:i]) + '0'
			parts.append(sorted_part)
			start = i + 1
	parts.sort(reverse=True) #attn
	return ''.join(parts)

算法分析：

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

错误的做法，只考虑到相互关系，没考虑内部关系

Python代码：

def makeLargestSpecial(self, s: str) -> str:
	count, presum = 1, []
	for i in range(1, len(s)):
		if s[i] == s[i-1]:
			count += 1
		else:
			presum.append(count)
			count = 1
	if count > 0:
		presum.append(count)
	print(presum)

	def move(presum):
		is_moved = False
		for i in range(2, len(presum), 2):
			if presum[i] > presum[i-1]:
				presum[i-2] += -presum[i-1] + presum[i]
				presum[i+1] += -presum[i] + presum[i-1]
				presum[i-1], presum[i] = presum[i], presum[i-1]
				print(presum)
				is_moved = True
		return is_moved
	
	move_res = True
	while move_res:
		move_res = move(presum)

	res, c = '', '1'
	for n in presum:
		res += c * n
		if c == '1':
			c = '0'
		else:
			c = '1'
	print(res)
	return res

LeetCode 930 Binary Subarrays With Sum

Posted on 2026-06-29 Edited on 2026-06-30 Disqus:

LeetCode

<div>

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

Example 1:

<pre>Input: nums = [1,0,1,0,1], goal = 2 Output: 4 Explanation: The 4 subarrays are bolded and underlined below: [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] </pre>

Example 2:

<pre>Input: nums = [0,0,0,0,0], goal = 0 Output: 15 </pre>

Constraints:

1 <= nums.length <= 3 * 104
nums[i] is either 0 or 1.
0 <= goal <= nums.length

</div>

题目大意：

有0和1组成的字符串，求所有子数组的和等于goal的个数

解题思路Presum(推荐)：

求子数组和第一时间想到presum，然后就是presum-goal是否在hashmap中，类似于Two sum。

解题步骤：

N/A

注意事项：

presum初始值为0，因为如果单元素数组，才能得到它的差值。
val_to_freq的计算要在循环中，类似于Two sum，不能提前用Counter计算，否则会有重复，比如[0, 0], goal=0, 不应该为4.

Python代码：

def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	presum = [0]
	for i in range(len(nums)):
		presum.append(presum[-1] + nums[i])
	val_to_freq, res = collections.defaultdict(int), 0
	for i in range(len(presum)):
		if presum[i] - goal in val_to_freq:
			res += val_to_freq[presum[i] - goal]
		val_to_freq[presum[i]] += 1 #attn
	return res

算法分析：

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

算法II解题思路Sliding Window：

此法虽然空间复杂度较优，但较难想。求字串的和可以考虑用Two pointers两边夹。这里求所有可能性，比如0011100, goal=3, 必须包括前缀0和后缀0，所以用Two pointers最长串的模板
类似于LeetCode 340 Longest Substring with At Most K Distinct Characters，不满足条件为窗口和大于goal，所以满足条件为小于等于goal(类似于at most k)。所以要用at_most(goal) - at_most(goal - 1)才能得到最后结果。
计算的时候，是i-left+1代表窗口和<=subgoal的以nums[i]为结尾的子数组个数，比如10101, i指向最后一个1, left指向第一个0, res是4个，对应1, 01, 101, 0101

注意事项：

模板满足条件在内循环外，所以计算结果在内循环结束后。
subgoal如果小于0，返回0。比如goal为0，nums=[0,0]

Python代码：

def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	def at_most(subgoal):
		if subgoal < 0: #attn
			return 0
		window_sum, left, res = 0, 0, 0
		i = 0
		for i in range(len(nums)):
			window_sum += nums[i]
			while window_sum > subgoal:
				window_sum -= nums[left]
				left += 1
			res += i - left + 1 # ending with nums[i]
		return res

	return at_most(goal) - at_most(goal - 1)

算法分析：

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

LeetCode 875 Koko Eating Bananas

Posted on 2026-06-29 Disqus:

LeetCode

<div>

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

<pre>Input: piles = [3,6,7,11], h = 8 Output: 4 </pre>

Example 2:

<pre>Input: piles = [30,11,23,4,20], h = 5 Output: 30 </pre>

Example 3:

<pre>Input: piles = [30,11,23,4,20], h = 6 Output: 23 </pre>

Constraints:

1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109

</div>

题目大意：

猴子吃n堆香蕉，要在h小时内吃完，求每小时吃的最少k根才能在限定时间内全部吃完。

解题思路：

枚举法，如果对于[3,6,7,11], k=3, 怎么算出多少小时呢? 数组每个数除以k向上取整求和即可，O(n)完成。怎么可以更快找到答案呢，很明显是二分法logn找答案，每次用O(n)算实际吃了多少小时。总的复杂度是O(nlogn).
所以此题是数值二分法，我也曾想过排序，但排序只能影响计算小于k值的小时数，不能优化后半段的，所以不用排序，而且数值二分法也不要求排序。

解题步骤：

数值二分法模板

注意事项：

start是从1开始，不是min(piles)。最大值取max(piles)因为跟取整型最大值是一样的。这样也可以避免单独处理单元素数组。
epsilon取0.5. 一般整数题都取0.5
mid是除2获得不是//2
mid作为参数输入到get_hours()要去int(mid)与题目一致，因为题目的k是整数
模板中h==hours时，不能return，要继续在左半区找，因为要达到误差epsilon内才会停止。类似于first_position

Python代码：

def minEatingSpeed(self, piles: List[int], h: int) -> int:
	#if len(piles) == 1: # attn
	 #   return math.ceil(piles[0] / h)
	# piles.sort()
	
	def get_hours(piles, k):
		return sum([math.ceil(n / k) for n in piles])


	# start, end = piles[0], piles[-1] # 3, 4
	start, end = 1, max(piles) # attn: 1 rather than min(piles)
	while start + 0.5 < end: # attn: use 0.5
		mid = start + (end - start) / 2 # attn /2 not // 2 | 7, 5, 4            
		hours = get_hours(piles, int(mid))  # attn: int(mid) | 5, 8, 8
		if h >= hours: # eat slower, attn 8 > 5
			end = mid # end=7, 5, 4
		else:
                start = mid

算法分析：

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