[Q4] There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 Solution: 按从小到大的顺序依次遍历两个数组，直至中间位置停止，此时： （1）当两个数组长度N1+N2为偶数时，取（中间数+前一数）/2
（2）当N1+N2为奇数时，取当前位置的数
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
""" i,j,idx = 0,0,0
m,n = len(nums1),len(nums2)
N = m+n
prv, cur = None, None while idx<N:
if i<m and j<n and nums1[i]<nums2[j]:
cur = nums1[i]
i = i+1
elif i<m and j<n and nums1[i]>=nums2[j]:
cur = nums2[j]
j = j+1
elif i>=m:
cur = nums2[j]
j = j+1
elif j>=n:
cur = nums1[i]
i = i+1
if N%2 == 0 and idx == N/2: # if m+n is even
return (cur+prv)/2
elif N%2 == 1 and idx == N//2: # floor division
return cur
prv = cur
idx = idx+1
[Q5] 找最长回文序列
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb" Solution：遍历中心，从中心依次向两端迭代
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
maxl = 0
i=0
left, right = 0,0
maxs = ""
while i<len(s): # center location
left = right = i
while left>=0 and right<len(s) and s[left]==s[right]:
left = left-1
right = right+1
tem = s[left+1:right]
if len(tem)>len(maxs):
maxs = tem
left, right = i,i+1
while left>=0 and right<len(s) and s[left]==s[right]:
left = left-1
right = right+1
tem = s[left+1:right]
if len(tem)>len(maxs):
maxs = tem
i = i+1
return maxs
[Q6] 解法很棒
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation: P I N
A L S I G
Y A H R
P I Solution: https://leetcode.com/problems/zigzag-conversion/discuss/3404/Python-O(n)-Solution-in-96ms-(99.43)
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
""" if len(s)<numRows or numRows==1:
return s idx = 0
step = 1
L = ['']*numRows
for x in s:
if idx==0:
step = 1
elif idx==numRows - 1:
step = -1
L[idx] += x
idx = idx+step
return ''.join(L)
重点：
（1）L的初始化，L为一个3行字符串数组
（2）引入Step，相当于把每一行的数直接压缩到同一行的唯一字符串内
（3）join函数：‘sep’.join（seq） 即将seq字符串去sep后连接