开始刷leetcode，简单题就懒得写出来了，把有点难度或者思路有趣的题记录一下。写业务写久了，整个人都变蠢了，需要刷一下智商了。
5. Longest Palindromic Substring
题意：求给定字符串的最长回文子串
思路：
比较简单，暴力一点写就是枚举回文串的中点，向两边扩展，复杂度O(n^2)，要考虑回文串为奇数和偶数的情况。
更好一点的方法，可以使用Manacher算法，之前看过，有点忘了，复习一下，实际上感觉和kmp的思路很想，最主要的思想就是利用已经计算过的结果。
这篇文章讲的很清晰，可以看一下：https://segmentfault.com/a/1190000003914228
代码：
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
ss = "#"
for i in range(len(s)):
ss += s[i]
ss += "#"
pos = maxRight = 0
maxp = 0
n = len(ss)
p = [0 for i in range(n)]
for i in range(n):
j = 2 * pos - i
if j > 0 and i <= maxRight:
p[i] = min(p[j], maxRight - i)
else:
p[i] = 0
while (i + p[i] + 1 < n and i - p[i] - 1 >= 0 and ss[i + p[i] + 1] == ss[i - p[i] - 1]):
p[i] += 1
if i + p[i] > maxRight:
maxRight = i + p[i]
pos = i
if p[i] > p[maxp]:
maxp = i
start = maxp - p[maxp]
end = maxp + p[maxp]
result = ""
while (start <= end):
if ss[start] != "#":
result += ss[start]
start += 1
return result
11. Container With Most Water
题意：给一组点ai，点(i, ai) 和 (i, 0)形成一个线段，现在要取两个线段，并与x轴形成一个容器，问这个容器最多能装多少水。
思路1：
容器能装水的多少取决于两点，一是最短的那个线段的长度，另一个是两个线段的距离。考虑一种特殊的情况，最短的那个线段就在长的线段的右边，以这种前提来看题目，那么就可以用一个数组保存一个单调的线段集合，保证数组中的线段是递增的，因为小于前面线段的线段是没有意义的，取前面的那个结果一定不比当前这个差。对于遍历到的线段，在这个单调集合中选择一个大于等于当前线段并且更靠左边的就好了。然后把数组翻转一下，另一种情况也就算出来了，复杂度O(nlog(n))。
代码1：
class Solution(object):
def binarySearch(self, orderList,n , value):
l = 0
r = n - 1
if orderList[r] < value:
return -1
result = -1
while (l <= r):
m = (l + r) // 2
if orderList[m][1] >= value:
result = orderList[m][0]
r = m - 1
else:
l = m + 1
return result
def getOrderMaxArea(self, height):
n = len(height)
m = 0
orderList = []
maxValue = 0
for i in range(n):
if i == 0:
orderList.append((0,height[0]))
m += 1
else:
findPos = self.binarySearch(orderList, m ,height[i])
if findPos >= 0:
maxValue = max(maxValue, (i - findPos)*height[i])
if height[i] > orderList[m - 1][1]:
orderList.append( (i,height[i]))
m += 1
return maxValue
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
result = self.getOrderMaxArea(height)
height.reverse()
result = max(result, self.getOrderMaxArea(height))
return result
思路2：
上面的代码交上去虽然过了，但是时间不能忍。有更好的方法，最开始考虑用最左边的线段l，和最右边的线段r组成容器，此时答案在[l,r]区间内，这个时候可以把l和r中较小的那个删掉。假设较小的那个是l，那么不可能有一更大的容器是(l,x)，因为r > l 并且 x < r，所以(l,r)一定比(l,x)更优。
代码2：
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
l = 0
r = n - 1
result = 0
while l <= r:
result = max(result,min(height[l],height[r])*(r - l))
if height[l] < height[r]:
l += 1
else:
r -= 1
return result
29. Divide Two Integers
题意：不用语言自带的除法做除法。
思路：
不能用除法就用减法呗，就是看能减多少个除数。当然，也不能一个一个去减，那复杂度就太高了，可以每次把除数乘个2，然后尝试去减，直到不能减，然后再从1倍的除数开始减，直到被除数小于除数。
代码：
class Solution(object):
def divide(self, dividend, divisor):
res = 0
neg = 1
if dividend < 0:
dividend *= -1
neg *= -1
if divisor < 0:
divisor *= -1
neg *= -1
while dividend >= divisor:
value = divisor
count = 1
while dividend >= value:
dividend -= value
res += count
count <<= 1
value <<= 1
res *= neg
return min(max(-2147483648, res), 2147483647)
32. Longest Valid Parentheses
题意：给一个括号序列，求最长的合法括号序列长度。合法就是左括号和右括号能够一一匹配。
思路：好久没做过dp了，状态方程一直没推出来，感觉弄了好久。用dp[i]表示以第i个字符为结尾的最长合法串的长度。
当s[i] == '(' 时，dp[i] = 0，因为不可能以'('结尾。
当s[i] == ')' 时：
1.如果s[i - 1] == '(' ， 那么dp[i] = dp[i - 2] + 2。
2.如果s[i - 1] == ')' 并且s[i - dp[i - 1] - 1] == '('，dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 1] + 2
边界的代码没写好，有点丑
class Solution(object):
def longestValidParentheses(self, s):
n = len(s)
result = 0
dp = [0 for i in range(n + 1)]
i = 1
while i <= n:
j = i - 1
if s[j] == '(':
dp[i] = 0
elif j > 0:
if s[j - 1] == '(':
dp[i] = dp[i - 2] + 2
elif s[j - 1] == ')' and j - dp[i - 1] - 1 >= 0 and s[j - dp[i - 1] - 1] == '(':
dp[i] = dp[i - 1] + 2
if i - dp[i - 1] - 2 >= 0:
dp[i] += dp[i - dp[i - 1] - 2]
result = max(dp[i], result)
i += 1
return result
33. Search in Rotated Sorted Array
题意：把一个有序序列划分为AB两部分，然后组成BA这样的新序列，要求实现一个搜索函数，这个数组中查找对应值。
思路：这题还算有趣，正常的有序序列的话可以使用二分法查找，但这个序列并不是完全有序的，不过实际上也没有复杂多少。还是用二分搜索的思路，如果当前区间是有序的，即nums[l] <= nums[r]，那么这个区间内也是有序的，正常二分搜索即可，如果nums[l] > nums[r]，那么也简单，还是正常搜索，但是如果这个区间搜不到，在另一个区间也尝试一下就可以了。
代码：
class Solution(object):
def search(self, nums, target):
def binarySearch(l, r):
if l == r:
if nums[l] == target:
return l
else:
return -1
m = (l + r) // 2
if nums[l] <= nums[r]:
if nums[m] >= target:
return binarySearch(l, m)
else:
return binarySearch(m + 1, r)
else:
res1 = binarySearch(l, m)
if res1 != -1:
return res1
return binarySearch(m + 1,r)
n = len(nums)
return binarySearch(0,n - 1)
41. First Missing Positive
题意：给一个整数数组，求在这个数组中，第一个未出现的正整数，但是需要O(n)的时间复杂度和O(1)的空间复杂度。
思路：
也是个挺有趣的题，这个问题的难点就在于O(1)的空间复杂度的限制，这就决定了你不能使用一个数组记录出现过的数字，而且O(n)的时间复杂度决定了不能暴力查找。
这题说简单也简单，虽然不能创建一个数组，但是可以利用原来的数组，数组只有n个数，也就是说，答案最大只有n + 1，我们可以尝试将数字放到对应的位置中，比如3就放在数组的第3个位置上，以此类推，最后，我们只要从数组遍历一遍，就可以知道缺的是哪个数字了。
class Solution(object):
def firstMissingPositive(self, nums):
n = len(nums)
i = n - 1
while i >= 0:
while nums[i] > 0 and nums[i] <= n:
pos = nums[i] - 1
if nums[pos] == nums[i]:
break
nums[pos], nums[i] = nums[i], nums[pos]
i -= 1
i = 0
while i < n:
if nums[i] != i + 1:
return i + 1
i += 1
return i + 1
42. Trapping Rain Water
题意：如图所示，给出黑块的位置和高度，求一盆水浇下去，最多能装多少水。
思路1：
用一个单调栈，维护一个递减的黑块序列。从左到右遍历黑块，如果比栈顶元素小，那么就可以算出这两个块之间能装水的数量，然后入栈。如果比栈顶元素大，那么就不断从栈中弹出元素，然后计算这两个块之间能装的水，需要注意的是，为了避免重复计算，要维护一个弹出元素的最大值，计高度的时候，要减掉这个值。
代码1：
class Solution(object):
def trap(self, height):
n = len(height)
if n == 0:
return 0
stack = [(0,0)]*n
stack[0] = (height[0], 0)
result = top = 0
i = 1
while i < n:
val = stack[top][0]
pos = stack[top][1]
if height[i] <= val:
result += (i - pos - 1)*height[i]
else:
maxHeight = 0
while top >= 0 and val <= height[i]:
result += (i - pos - 1)*(val - maxHeight)
maxHeight = max(maxHeight, val)
top -= 1
if top >= 0:
val = stack[top][0]
pos = stack[top][1]
if top >= 0 and stack[top][0] > height[i]:
result += (i - stack[top][1] - 1)*(height[i] - maxHeight)
top += 1
stack[top] = (height[i], i)
i += 1
return result
思路2：
思路2就有点意思了。记黑块的两边分别为l和r，挑一个height[l]和height[r]中较小的那边开始计算，假设是l，那么l的右边肯定至少有一个比它高的块，然后就可以开始向右遍历了，如果第i个的高度height[i] < height[l] ，那么就在结果加上height[l] - height[i]，否则，就把i当做新的l，以此类推。
代码2：
class Solution(object):
def trap(self, height):
n = len(height)
if n < 3:
return 0
result = 0
l = 0
r = n - 1
while (l < r):
leftVal = height[l]
rightVal = height[r]
if leftVal <= rightVal:
while l < r and leftVal >= height[l + 1]:
l += 1
result += leftVal - height[l]
l += 1
else:
while l < r and rightVal >= height[r - 1]:
r -= 1
result += rightVal - height[r]
r -= 1
return result
287. Find the Duplicate Number
题意：给一个长度为n + 1的数组，这个数组中的数字范围是[1,n]，并且这个数组中，有且只有一个会重复的数字，要求找出这个数字。但是有几个条件：
1.不能修改原数组的值。
2.必须使用O(1)的空间复杂度解决问题。
3.时间复杂度不能超过O(n^2)。
4.只有一个重复数字，但是这个数字可能重复多次。
思路：
二分一下重复数字的区间，然后遍历一下数组，计算一下在这个区间中的数字有多少个，如果大于区间长度，那么说明这个区间中有重复数字，时间复杂度O(nlogn)。
AC完以后发现还有O(n)的方法，大概是用数字和位置坐了一个映射，然后转换为找环的问题，道理我都懂，但是不会证，暂时不写了。
代码：
class Solution(object):
def findDuplicate(self, nums):
m = len(nums)
n = m - 1
l = 1
r = n
while (l < r):
midValue = (l + r) // 2
i = 0
count = 0
while i < m:
if nums[i] >= l and nums[i] <= midValue:
count += 1
i += 1
if count > midValue - l + 1:
r = midValue
else:
l = midValue + 1
return l
312. Burst Balloons
题意：给你一排气球，每个气球上有一个分数，当你打爆一个气球时，你会获得这个气球上的分数乘两边气球上的分数的乘积的分数。问最多能获得多少分。
思路：
刚开始总觉的做过这题啊，想了半天终于想起来应该是和优化矩阵乘法差不多，但是还有些不一样，在一个区间[l,r]中，不能保证最后剩下的是l和r，所以不能像那样计算，不过肯定是dp了，但是状态转移方程想了很久没想出来，去查一下题解，发现都是类似这种说法：
dp[i][j]表示气球i到气球j的最佳coins
首先，一排气球左边是L，右边是R，我们可以假设最后一个打爆的气球是i，那倒数第二个打爆的气球j就出现在L-i或者i-R.
dp[L][R] = nums[i] * nums[L] * nums[R] + dp[L][i]+dp[i][R];
设dp[i][j]为i到j这段区间所能得到的最大值，状态转移方程为dp[i][j] = max(i < k < j) (dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
怎么说呢，不知道是这些博主没有理解就往外发，还是语言没有组织好，如果是dp[i][j]表示区间能得到的最大值，那么这个状态转移方程根本不能成立，因为你不能保证最后取i和j才是最大值。
但是为什么错误的转移方程能AC？反正看到这里是蛮气的，好好研究了一下，之前的大体思路是对的，状态转移方程其实也没错，但是状态表示是不对的。正确的理解应该是：dp[i][j]表示，当不打爆i和j时，区间[i,j]能取到的最大值，这样思考的话，状态转移方程就对了，在原来的气球数组最前面和最后面插入一个1，不会影响结果，dp[0][n + 1]就是最终结果了。
代码：
class Solution(object):
def maxCoins(self, nums):
nums.insert(0, 1)
nums.append(1)
n = len(nums)
dp = [[0]*n for i in range(n)]
d = 2
while d < n:
left = 0
while left + d < n:
right = left + d
k = left + 1
temp = 0
while k < right:
temp = max(temp, dp[left][k] + nums[left]*nums[k]*nums[right] + dp[k][right])
k += 1
dp[left][right] = temp
left += 1
d += 1
return dp[0][n - 1]
这道问题带来的思考：
1.思考问题的时候不要钻牛角尖，多尝试以不同的角度思考问题。
2.没有理解的问题，匆忙AC又有什么意义呢？
网友评论