12 Aug 2018
Search Insert Position
根据输入的数组nums
和一个数字target
,查找按照从小到大顺序下target
在数组中的插入位置
- 遍历数组
nums
,如果当前元素num
大于等于target
,返回当前位置index
- 如果整个数组中不存在一个元素大于等于
target
,那么返回当前数组长度len(nums)
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
for index, num in enumerate(nums):
if target <= num:
return index
return len(nums)
12 Aug 2018
Maximum Subarray
题目描述很简单:给定一个数组nums
,在所有子数组的和中求最大值
从题目描述来看,可以使用穷举的方式求助所有子数组的和,比较最大值返回即可,代码实现如下:
12 Aug 2018
Count and Say
题目定义的比较难懂,查看下列序列的规律:
1. 1
2. 11
3. 21
4. 1211
5. 111221
6. 312211
7. 13112221
8. 1113213211
9. 31131211131221
10. 13211311123113112211
10 Aug 2018
Remove Element
给出的数组nums
和数值val
,在满足o(1)
空间复杂度的前提下,计算出删除val
后剩余数组的长度len
,要求处理后的数组前len
个元素不包含val
题目比较简单,但是有些隐藏的陷阱:
- 遍历数组的同时删除元素,不能采用
for
循环进行,否则如果出现两个以上相等的元素,遍历时会跳过删除后前移的元素,如
for i,n in enumerate(nums):
if n == val:
del nums[i] #删除元素后,数组后面列表元素自动前移,如果删除前nums[i+1] == val,那么删除后这个val自动移动到了nums[i]的位置,但是循环已经认为这个位置的元素处理过了不会再重复处理
return len(nums)
- 解决方案1:使用
while
循环和下标,控制遍历过程:
i = 0
while(i < len(nums)):
if nums[i] == val:
del nums[i]
else:
i = i + 1
return len(nums)
在遍历时使用下标i
控制遍历过程,如果匹配到了要删除的元素,下标i
的值不自增,可以解决上面描述的遍历问题
10 Aug 2018
Implement strStr()
给定两个字符串strA
/ strB
,计算后者在前者第一次出现的首字母位置(java
的indexOf()
和C
的strStr()
)
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if not needle:
return 0
if haystack == needle:
return 0
for i in range(len(haystack)):
subStr = ''.join(haystack[i : i + len(needle)])
if len(needle) > len(subStr): #在输入的两个字符很长的情况下,有可能存在资源消耗过大,因此先用长度做简单判断
return -1
if subStr == needle:
return i
return -1