KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2


Example 2:

Input: nums = [1,2,3], k = 3
Output: 2


Constraints:

`1 <= nums.length <= 2 104*-1000 <= nums[i] <= 1000*-107 <= k <= 107`

题目大意：

子数组和等于k的个数

解题思路：

子数组和第一时间想到presum，而数组元素之间关系也应该想到two sum

解题步骤：

N/A

注意事项：

  1. 加0到presum中或者加0到sum_to_idx字典中，确保presum本身可以等于k
  2. 数组含负数，也即是presum中可以含有多个相同的值，所以sum_to_idx要转成频数而不是下标。如[-1, 1, -1, 1], k=0结果为4，而不是3, 容易漏整个数组和

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# presum = [0, 1, 2, 3], target = presum[i] - k = presum[j]
# add 0 to presum so that presum[i] = k
# [0, -1, 0, -1, 0]
# [0, 1]
def subarraySum(self, nums: List[int], k: int) -> int:
	presum, res = [0], 0 #
	for n in nums:
		presum.append(presum[-1] + n) # 0, 1, 2, 3
	sum_to_idx = collections.defaultdict(int)
	for i in range(len(presum)): #
		if presum[i] - k in sum_to_idx: # 1-1
			res += sum_to_idx[presum[i] - k] #4
		sum_to_idx[presum[i]] += 1 # {0:2, -1:2, 2:2}
	return res

算法分析：

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

Posted on Disqus:

LeetCode



Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

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


Example 2:

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


Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]


Example 4:

Input: nums = [1]
Output: [1]


Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 100

题目大意：

下一个全排列数

解题思路：

N/A

解题步骤：

  1. 找到从后往前升序的第一个非升序数，如135864的5
  2. 找到从后往前比步骤1中大的数，调换，如6，变成136854
  3. 后边部分按升序排列或者做reverse(更高效)

注意事项：

  1. Python语法问题： reverse子列表，跟倒序遍历数组一样，要指明前后边界，前面边界值更大

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 135864 -> 136854 -> 136458
# 1355864 -> 1356458
# 99
def nextPermutation(self, nums: List[int]) -> None:
	to_be_swapped_index, greater_index = -1, -1
	for i in range(len(nums) - 2, -1, -1):
		if nums[i] < nums[i + 1]: # 5 < 8
			to_be_swapped_index = i # 2
			break
	if to_be_swapped_index == -1:
		nums.sort()
		return nums
	for i in range(len(nums) - 1, to_be_swapped_index, -1): #
		if nums[to_be_swapped_index] < nums[i]: # 5 < 6
			greater_index = i # 4
			break # 136854
	nums[to_be_swapped_index], nums[greater_index] = nums[greater_index], nums[to_be_swapped_index]
	# nums[to_be_swapped_index + 1:] = sorted(nums[to_be_swapped_index + 1:]) # 136458
	nums[to_be_swapped_index + 1:] = nums[:to_be_swapped_index:-1]
	return nums

算法分析：

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

Posted on Edited on Disqus:

LeetCode

题目大意：

N/A

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2


算法分析：

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

Posted on Disqus:

LeetCode



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:

Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”


Example 2:

Input: strs = [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.


Constraints:

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

题目大意：

字符串列表的最长前缀

算法思路：

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)

Posted on Edited on Disqus:

LeetCode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.



You may assume the two numbers do not contain any leading zero, except the number 0 itself.



 


Example 1:



Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.


Example 2:



Input: l1 = [0], l2 = [0]
Output: [0]


Example 3:



Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]


 


Constraints:




  • The number of nodes in each linked list is in the range [1, 100].

  • 0 <= Node.val <= 9

  • It is guaranteed that the list represents a number that does not have leading zeros.


题目大意：

数位链表(从最低位到最高位)相加

算法思路：

类似于merge sort

注意事项：

  1. 其中一个可能较长，所以主循环出来后还要继续循环较长的链表，类似于merge sort
  2. 所有链表遍历完后，carry可能还会是1，要加一个if语句特别处理

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
	fake_head = ListNode(0)
	carry = 0
	it, it2, it_res = l1, l2, fake_head
	while it or it2:
		value = carry
		if it:
			value += it.val
			it = it.next
		if it2:
			value += it2.val
			it2 = it2.next
		carry = 1 if value >= 10 else 0
		value %= 10
		it_res.next = ListNode(value)
		it_res = it_res.next
	if carry == 1:
		it_res.next = ListNode(1)
	return fake_head.next

算法分析：

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

Free mock interview