26-Remove Duplicates from Sorted Array
问题描述
给定一个排好序的数组nums，就地删除重复的元素，从而使得每个元素只出现一次，并且返回新的长度。不要为另一个数组分配额外的空间，我们需要使用O(1)的额外空间来实现就地修改输入数组。
示例1
Input: nums = [1,1,2]
Output: 2，nums数组的前两个元素应该分别为1和2
示例2
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 4，nums数组的前两个元素应该分别为0,1,2,3
说明：为什么返回的是一个整数而回答是一个数组？因为输入数组是地址引用，这就意味着对输入数组的修改也会同步到调用者。可以看做是下面的做法：
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解题思路
使用两个指针，第一个指针指向当前无重复的最后一个数字，第二个指针指向下一个数字，如果两个指针所指的数相等，那么第一个指针不动，第二个指针向前移动，否则的话，将第二个指针所指的值和第一个指针后面的值进行交换，再将连个指针同时向前移动一位；直到第二个指向前走到数组的最后一位为止。
此时，时间复杂度为O(n)，空间复杂度为O(1)，使用了两个指针来存储数组的下标值。
代码
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return len(nums)
first = 0
end = first + 1
while end < len(nums):
if nums[first] == nums[end]:
end += 1
else:
nums[first+1], nums[end] = nums[end], nums[first+1]
first += 1
end += 1
return first + 1
27-Remove Element
问题描述
给定一个数组nums和值val，就地删除该值的所有元素并且返回新的长度。不要为另一个数组分配额外的空间，我们需要使用O(1)的额外空间来实现就地修改输入数组。
示例1
Input: nums = [3,2,2,3], val = 3
Output: 2，nums数组的前两个元素应该均为2
示例2
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5，nums数组的前五个元素应该为：0,1,3,0,4
注意：这五个元素的顺序可以随意交换
说明：为什么返回的是一个整数而回答是一个数组？因为输入数组是地址引用，这就意味着对输入数组的修改也会同步到调用者。可以看做是下面的做法：
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解题思路
使用两个指针，从前到后进行遍历：第一个指针指向第一个等于该val的值，第二个指针指向第一个指针后第一个不等于该val的值，将两个值交换，然后继续遍历，直到第二个指针到达数组末尾为止。
特别注意：最后需要判断一下最后一个指针的值是否等于val，如果不判断的话，可能会出现少1的情况。
代码
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
if len(nums) == 0:
return 0
first = 0
end = first + 1
while end < len(nums):
if nums[first] != val:
first += 1
end += 1
else:
if nums[end] != val:
nums[first], nums[end] = nums[end], nums[first]
first = first + 1
end = end + 1
else:
end += 1
if nums[end-1] != val:
return first + 1
else:
return first
28-Implement strStr()
问题描述
实现strStr()。
返回字符串中出现指针的第一个为止，如果指针不在字符串中，返回-1。
示例1
Input: haystack = "hello", needle = "ll"
Output: 2
示例2
Input: haystack = "aaaaa", needle = "bba"
Output: -1
说明
如果needle是一个空字符串，那么返回0即可。与C的strstr()、Java的indexOf()等方法保持一致。
解题思路
很明显，这是一道子字符串匹配的题目。如果使用暴力破解法的话，时间复杂度为O(m*n)，其中m为haystack的长度，而n为needle的长度。
那么传统的字符串匹配的方法应该如何解呢？不难想到KMP算法。关于KMP算法，找到一篇很不错的博客：从头到尾彻底理解KMP（2014年8月22日版）。
稍微提一下Sunday算法：
字符串匹配算法优化的核心都是尽量避免重复的比较，而Sunday算法的核心是，针对没有被匹配成功的字符串，一般要往后移动一位，因此当面对齐的最后一个字符串后面的那个字符串（假设此时该字符的索引为endIdx）：
– 如果该字符没有在模式串中，那么匹配串下次匹配的起始索引应该为endIdx+1
– 如果该字符在模式串中，那么应该将匹配串中的该字符与该字符在模式串中最右边的字符串进行对齐，也就是说需要将i移动到endIdx-len(p)+x，其中，x为该字符在模式串中最右边的字符距离末尾的距离
最后，再从头开始进行匹配。这样可以大大减少移动的次数，从而缩短匹配时间。
代码
KMP算法
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if len(needle) == 0:
return 0
next = self.GetNext(needle)
i = 0
j = 0
sLen = len(haystack)
pLen = len(needle)
while i < sLen and j < pLen:
if j == -1 or haystack[i] == needle[j]:
i += 1
j += 1
else:
j = next[j]
if j == pLen:
return i - j
else:
return -1
def GetNext(self, p):
pLen = len(p)
next = [0 for i in range(pLen)]
next[0] = -1
k = -1
j = 0
while j < pLen - 1:
if k == -1 or p[j] == p[k]:
k += 1
j += 1
next[j] = k
else:
k = next[k]
return next
Sunday算法
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if len(needle) == 0:
return 0
nextDict = self.getNext(needle)
sLen = len(haystack)
pLen = len(needle)
i = 0
j = 0
while i < sLen:
endIdx = i + pLen
while j < pLen and i < sLen and haystack[i] == needle[j]:
i += 1
j += 1
if j < pLen and endIdx < sLen:
endVal = haystack[endIdx]
if endVal in nextDict:
#moving nextDict[endVal]
i = endIdx - pLen + nextDict[endVal]
else:
i = endIdx + 1
j = 0
else:
break
if j == pLen:
return i - j
else:
return -1
def getNext(self, p):
nextDict = dict()
pLen = len(p)
for i in range(pLen):
nextDict[p[i]] = pLen - i
return nextDict
29-Divide Two Integers
问题描述
给定两个整数dividend和divisor，将两个数相除，不要使用乘法，除法和取余操作符。
将dividend除以divisor之后，返回商。
示例1
Input: dividend = 10, divisor = 3
Output: 3
示例2
Input: dividend = 7, divisor = -3
Output: -2
注意：
– 除数和被除数都是32位有符号整数
– 被除数不会为0
– 假设我们现在只能存储下32位有符号的整数范围：[-2^31,2^21-1]，在这个问题的背景下，当除数结果溢出的时候，函数返回2^31-1。
解题思路
注意题干条件：不能用乘除和取余，是希望我们用加减来解决问题。根据乘法的定义：a*b=a+a+...+a，第一想法是通过累加多次与除数进行比较，直到累加到第一次等于或者超过除数为止。
考虑到溢出的问题：由于除数和被除数都是整数，所以只有在除数为-2^31，被除数为-1的时候才有可能溢出。提前做好判断即可。
看来还是低估了这道题目的难度，按照上面的想法提交代码之后报错了，超过时间限制，案例是2147483647,1，思考了下，一个一个叠加的速度确实很慢，我们应该怎么加速呢？
首先想到，是否可以成倍地叠加？直到无法成倍叠加之后，使用递归的方法不断调用，直到divident<divisor的时候，返回0接口
代码
class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
minVal = -1 * math.pow(2, 31)
if dividend == minVal and divisor == -1:
return int(math.pow(2, 31) - 1)
flag = 1
if divisor < 0 and divisor < 0:
divisor = divisor * -1
dividend = dividend * -1
if divisor > 0 > dividend:
flag = -1
dividend = dividend * -1
if divisor < 0 < dividend:
flag = -1
divisor = divisor * -1
return flag * self.dividePos(dividend, divisor)
def dividePos(self, dividend, divisor):
if dividend < divisor:
return 0
ret = 1
nowSum = divisor
while nowSum + nowSum <= dividend:
nowSum += nowSum
ret += ret
return ret + self.divide(dividend - nowSum, divisor)
30-Substring with Concatenation of All Words
问题描述
给定一个字符串s和一个所有元素长度都相等的单词列表words。找到s中包含words中每个单词组合（只出现一次）的字串起始索引。
示例1
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
解释：起始索引为`0`和`9`的字符字串分别为"barfoo"和"foobar"，不考虑返回的顺序
示例2
Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []
解题思路
最最简单的思路：使用一个hashmap来存储words中出现的词。然后，我们从0开始遍历，用left来记录左边界的位置，count表示当前已经匹配的单词的个数。然后我们一个单词一个单词的遍历，如果当前遍历的到的单词t在m1中存在，那么我们将其加入另一个哈希表m2中，如果在m2中个数小于等于m1中的个数，那么我们count自增1，如果大于了，那么需要做一些处理，比如下面这种情况,s = barfoofoo, words = {bar, foo, abc}, 我们给words中新加了一个abc，目的是为了遍历到barfoo不会停止，那么当遍历到第二foo的时候, m2[foo]=2, 而此时m1[foo]=1，这是后已经不连续了，所以我们要移动左边界left的位置，我们先把第一个词t1=bar取出来，然后将m2[t1]自减1，如果此时m2[t1]<m1[t1]了，说明一个匹配没了，那么对应的count也要自减1，然后左边界加上个len，这样就可以了。如果某个时刻count和cnt相等了，说明我们成功匹配了一个位置，那么将当前左边界left存入结果res中，此时去掉最左边的一个词，同时count自减1，左边界右移len，继续匹配。如果我们匹配到一个不在m1中的词，那么说明跟前面已经断开了，我们重置m2，count为0，左边界left移到j+len。
代码
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
if len(words) == 0:
return []
wcDict = self.prepareDict(words)
wordLen = len(words[0])
wordNum = len(words)
matchIdxList = []
for i in range(wordLen):
nowDict = dict()
matchCnt = 0
curIdx = i
for j in range(i,len(s)-wordLen+1,wordLen):
nowWord = s[j:j+wordLen]
if nowWord in wcDict:
cnt = 1
if nowWord in nowDict:
cnt += nowDict[nowWord]
nowDict[nowWord] = cnt
if cnt <= wcDict[nowWord]:
matchCnt += 1
else:
while True:
tmp = s[curIdx: curIdx + wordLen]
nowDict[tmp] = nowDict[tmp] - 1
curIdx += wordLen
if tmp == nowWord:
break
else:
matchCnt -= 1
if matchCnt == wordNum:
matchIdxList.append(curIdx)
tmp = s[curIdx: curIdx + wordLen]
nowDict[tmp] = nowDict[tmp] - 1
curIdx += wordLen
matchCnt -= 1
else:
nowDict = dict()
matchCnt = 0
curIdx = j + wordLen
return matchIdxList
def prepareDict(self, words):
wcDict = dict()
for i in range(len(words)):
cnt = 1
if words[i] in wcDict:
cnt += wcDict[words[i]]
wcDict[words[i]] = cnt
return wcDict
31-Next Permutation
问题描述
实现下一个排序，将数字按照下一个大于数字组合的顺序进行排序。如果无法返回这种组合，那么返回最小的可能的顺序（例如，以升序进行排列）。
必须就地替换并且只能使用常数的额外空间。
下面是一些示例，左边列是输入，而右边列是对应的输出。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解题思路
这个题目有点类似于排序题目，考虑下以下情况：
- 如果末尾两个数字是升序排列，那么直接将两个数交换即可，如果不行的话，则考虑末尾三个数
- 如果末尾三个数不是最大值，那么直接将计算末尾三个数的下一个排序即可
所以问题简化为了：如果找到后面m个数的下一个排序，第一想法是：将m之后的数数字进行升序排列，然后将nums[m]与比nums[m]略大一点的数进行交换。
因此这道题目主要考虑两点：
– 排序
– 插入
在写代码的过程中，发现在递归的过程中其实可以共用一个函数：找到比nums[m]略大的情况，
代码
class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nLen = len(nums)
idx = nLen - 1
while idx > 0:
pivot = nums[idx-1]
k = self.findK(nums, idx-1, nLen-1, pivot)
if k != -1:
nums[idx-1], nums[k] = nums[k], nums[idx-1]
break
else:
idx -= 1
self.quickSort(nums, idx, nLen-1)
def findK(self, nums, start, end, pivot):
if nums[-1] <= pivot:
return -1
if nums[start] > pivot:
return start
mid = (start + end) / 2
if nums[mid] <= pivot:
return self.findK(nums, mid+1, end, pivot)
else:
return self.findK(nums, start, mid, pivot)
def quickSort(self, nums, start, end):
if start > end:
return
i = start
j = end
pivot = nums[start]
while i < j:
while i < j and nums[j] >= pivot:
j -= 1
while i < j and nums[i] <= pivot:
i += 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
nums[start],nums[i] = nums[i], nums[start]
self.quickSort(nums, start, i-1)
self.quickSort(nums, i + 1, end)
32-Longest Valid Parentheses
问题描述
给定一个只包含'('和')'字符的字符串，找到最长有效的括号字符的长度。
示例1
Input: "(()"
Output: 2
解释：最长有效括号对子串是"()"
示例2
Input: ")()())"
Output: 4
解释：最长有效括号对子串是"()()"
解题思路
方法1：暴力破解
在本方法中，我们考虑每一个可能的非空偶数长子串，然后检查其是否是一个有效的括号对，取最长的有效长度。
例如：
"((())"
(( --> invalid
(( --> invalid
() --> valid, length=2
)) --> invalid
((()--> invalid
(())--> valid, length=4
此时，算法复杂度为O(n^3)
算法2：动态规划
使用一个数组dp来存储相关数据，其实dp的第i个元素表示到第i个字符为止的最长括号对。很明显：当s[i]="("时，无法构成有效的括号对，因此仅讨论s[i]=")"的情况：
- 当
s[i-1]="("时，大致是这种形式："...()"，字符串仍然构成有效括号对，dp[i]=dp[i-2]+2 - 当
s[i-1]=")"时，大致是这种形式："...))"，需要先找到s[i]对称的字符，如果等于"("，则为有效括号对，则将前一个有效对的长度（dp[i-dp[i-1]-2]）再加上当前有效对的长度（s[i-1]+2），否则，直接设置为0
得到转移方程之后，就可以写出代码了，此时算法复杂度为O(n)。
算法3：使用堆栈
遍历字符串：
– 对于每一个"("，我们将其下标写入堆栈中
– 对于每一个")"，我们将头部元素取出来，然后用当前元素的索引减去当前栈顶元素，其值为到当前位置有效括号对的长度。当栈为空时，将当前下标push进去，保证能够一直计算有效字符串的长度。
代码
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
sLen = len(s)
dp = [0 for _ in range(sLen)]
maxLen = 0
for i in range(1, sLen):
cur = s[i]
if cur == ")":
pre = s[i-1]
if pre == "(":
dp[i] = (dp[i-2] if i >= 2 else 0) + 2
else:
preIdx = i - dp[i-1] - 1
if preIdx >= 0:
preMatch = s[preIdx]
if preMatch == "(":
dp[i] = dp[i-1] + 2 + (dp[preIdx-1] if preIdx-1 >= 0 else 0)
maxLen = dp[i] if dp[i] > maxLen else maxLen
return maxLen
微信扫一扫，打赏作者吧～