0%

leetcode4-6

1. 寻找两个有序数组的中位数(Hard)

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解答:

*思路一:时间复杂度$O((m+n)log(m+n))$,空间复杂度$O(m+n)$

首先最简单粗暴的方法,就是我们将两个数字列表合并起来,排好序,找到中间的median就ok了,但是千万要注意一点,如果median有两个,需要算平均。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums = sorted(nums1 + nums2)
if len(nums) % 2 == 1:
return nums[len(nums)//2]
else:
return (nums[len(nums)//2-1] + nums[len(nums)//2]) / 2.0

思路二:时间复杂度$O(log(m+n))$,空间复杂度$O(1)$

这时候我们观察到题目给的一个条件,nums1nums2本身也是有序的,放着这个条件不用反而用思路一是不是有点浪费了?换句话说我们没必要把他们整个排序,于是我们可以把它转化成经典的 findKth问题

首先转成求AB数组中第k小的数的问题, 然后用k//2AB中分别找。

比如 k = 6, 分别看AB中的第3个数, 已知 A1 <= A2 <= A3 <= A4 <= A5...B1 <= B2 <= B3 <= B4 <= B5..., 如果A3 <= B3, 那么第6小的数肯定不会是A1, A2, A3, 因为最多有两个数小于A1(B1, B2), 三个数小于A2(A1, B1, B2), 四个数小于A3(A1, A2, B1, B2)。 关键点是从k//2 开始来找。那就可以排除掉A1, A2, A3, 转成求A4, A5, ... B1, B2, B3, ...这些数中第3小的数的问题, k就被减半了。

k == 1或某一个数组空了, 这两种情况都是终止条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def findKth(A,B,k):
if len(A) == 0:
return B[k-1]
if len(B) == 0:
return A[k-1]
if k == 1:
return min(A[0],B[0])

a = A[k//2-1] if len(A) >= k // 2 else None
b = B[k//2-1] if len(B) >= k // 2 else None

# if a is None:
# return findKth(A, B[k // 2:], k - k // 2) # 这里要注意:因为 k//2 不一定等于 (k - k//2)
# if b is None:
# return findKth(A[k // 2:], B, k - k // 2)
# if a < b:
# return findKth(A[k // 2:], B, k - k // 2)
# else:
# return findKth(A, B[k // 2:], k - k // 2)

if b is None or (a is not None and a < b):
return findKth(A[k // 2:], B, k - k // 2)
return findKth(A, B[k // 2:], k - k // 2)

n = len(nums1) + len(nums2)
if n % 2 == 1:
return findKth(nums1,nums2,n//2+1)
else:
small = findKth(nums1,nums2,n//2)
large = findKth(nums1,nums2,n//2+1)
return (small + large) / 2.0

思路三:时间复杂度$O(log(m+n))$,空间复杂度$O(1)$

findKth 函数我们可以用双指针的方式实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def findKth(A, pa, B, pb, k):
res = 0
m = 0
while pa < len(A) and pb < len(B) and m < k:
if A[pa] < B[pb]:
res = A[pa]
pa += 1
else:
res = B[pb]
pb += 1
m += 1
while pa < len(A) and m < k:
res = A[pa]
pa += 1
m += 1
while pb < len(B) and m < k:
res = B[pb]
pb += 1
m += 1
return res
n = len(nums1) + len(nums2)
if n % 2 == 1:
return findKth(nums1, 0, nums2, 0, n // 2 + 1)
else:
smaller = findKth(nums1, 0, nums2, 0, n // 2)
bigger = findKth(nums1, 0, nums2, 0, n // 2 + 1)
return (smaller + bigger) / 2.0

2. 最长回文字串(Medium)

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

1
2
输入: "cbbd"
输出: "bb"

解答:

思路一:时间复杂度$O(n^2)$,空间复杂度$O(n^2)​$

动态规划思想:dp[i][j]表示s[i:j+1]是否是palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
res = ''
dp = [[False] * len(s) for i in range(len(s))]
for i in range(len(s),-1,-1):
for j in range(i,len(s)):
dp[i][j] = (s[i] == s[j]) and (j-i<3 or dp[i+1][j-1])
if dp[i][j] and j-i+1>len(res):
res = s[i:j+1]
return res

思路二:时间复杂度$O(n^2)$,空间复杂度$O(1)​$

回文字符串长度为奇数和偶数是不一样的:

  1. 奇数:'xxx s[i] xxx', 比如 'abcdcba'
  2. 偶数:'xxx s[i] s[i+1] xxx', 比如 'abcddcba'

我们区分回文字符串长度为奇数和偶数的情况,然后依次把每一个字符当做回文字符串的中间字符,向左右扩展到满足回文的最大长度,不停更新满足回文条件的最长子串的左右index: lr,最后返回s[l:r+1]即为结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l = 0 # left index of the current substring
r = 0 # right index of the current substring
max_len = 0 # length of the longest palindromic substring for now
n = len(s)
for i in range(n):
# odd case: 'xxx s[i] xxx', such as 'abcdcba'
for j in range(min(i+1, n-i)): # 向左最多移动 i 位,向右最多移动 (n-1-i) 位
if s[i-j] != s[i+j]: # 不对称了就不用继续往下判断了
break
if 2 * j + 1 > max_len: # 如果当前子串长度大于目前最长长度
max_len = 2 * j + 1
l = i - j
r = i + j

# even case: 'xxx s[i] s[i+1] xxx', such as 'abcddcba'
if i+1 < n and s[i] == s[i+1]:
for j in range(min(i+1, n-i-1)): # s[i]向左最多移动 i 位,s[i+1]向右最多移动 [n-1-(i+1)] 位
if s[i-j] != s[i+1+j]: # 不对称了就不用继续往下判断了
break
if 2 * j + 2 > max_len:
max_len = 2 * j + 2
l = i - j
r = i + 1 + j
return s[l:r+1]

思路三:时间复杂度$O(n)$,空间复杂度$O(n)​$

Manacher算法

Useful link

3. Z字形变换(Medium)

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下:

1
2
3
L   C   I   R
E T O E S I I G
E D H N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数:

1
string convert(string s, int numRows);

示例 1:

1
2
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

1
2
3
4
5
6
7
8
9
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L D R
E O E I I
E C I H N
T S G

解答:

思路一:时间复杂度$O(n)$,空间复杂度$O(n)​$

idx0开始,自增直到numRows-1,此后又一直自减到0,重复执行。

给个例子容易懂一些:s = “abcdefghijklmn”, numRows = 4

1
2
3
4
a    g    n 
b f h l m
c e i k
d j

从第一行开始往下,走到第四行又往上走,这里用 step = 1 代表往下走, step = -1代表往上走

因为只会有一次遍历,同时把每一行的元素都存下来,所以时间复杂度和空间复杂度都是 O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows == 1 or len(s) <= numRows:
return s

res = [''] * numRows
idx,step = 0,1

for c in s:
res[idx] += c
if idx == 0:
step = 1
elif idx == numRows - 1:
step = -1
idx += step
return ''.join(res)

思路二:模拟过程

Z字形,就是两种状态,一种垂直向下,还有一种斜向上

控制好边界情况就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def convert(self, s: str, numRows: int) -> str:
if not s:
return ""
if numRows == 1:return s
s_Rows = [""] * numRows
i = 0
n = len(s)
while i < n:
for j in range(numRows):
if i < n:
s_Rows[j] += s[i]
i += 1
for j in range(numRows-2,0,-1):
if i < n:
s_Rows[j] += s[i]
i += 1
return "".join(s_Rows)