Solution for Search Insert Position

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)

Solution for Maximum Subarray

Maximum Subarray

题目描述很简单:给定一个数组nums,在所有子数组的和中求最大值

  • 暴力求解

从题目描述来看,可以使用穷举的方式求助所有子数组的和,比较最大值返回即可,代码实现如下:

Solution for Count and Say

Count and Say

题目定义的比较难懂,查看下列序列的规律:

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
10.     13211311123113112211

Solution for Remove Element

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的值不自增,可以解决上面描述的遍历问题

Implement strStr()

Implement strStr()

给定两个字符串strA / strB,计算后者在前者第一次出现的首字母位置(javaindexOf()CstrStr()

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