小李飛刀：刷題第五彈！

Miracle 發(fā)布于2019-07-31 10:08 / 3125人閱讀

摘要：寫在前面的話好幾天木有刷題啦，今天猛刷了一把，要梳理一個(gè)順序好好的學(xué)習(xí)啦一定要好好執(zhí)行每天做題的計(jì)劃最近真的好忙碌啊，還要做視頻。第二題最大子序和難度簡單給定一個(gè)整數(shù)數(shù)組，找到一個(gè)具有最大和的連續(xù)子數(shù)組子數(shù)組最少包含一個(gè)元素，返回其最大和。

寫在前面的話

好幾天木有刷題啦，今天猛刷了一把，要梳理一個(gè)順序好好的學(xué)習(xí)啦~
一定要好好執(zhí)行每天做題的計(jì)劃！
最近真的好忙碌啊，還要做視頻。
不過呢，看了高效學(xué)習(xí)的書，感覺其實(shí)不能說太分散的學(xué)習(xí)，應(yīng)該考慮多方面的聯(lián)系，形成整體性的學(xué)習(xí)，還得琢磨琢磨...
小李加油呀！

認(rèn)真做題

第一題

58. 最后一個(gè)單詞的長度
難度：簡單
給定一個(gè)僅包含大小寫字母和空格 " " 的字符串，返回其最后一個(gè)單詞的長度。
如果不存在最后一個(gè)單詞，請(qǐng)返回0。
說明：一個(gè)單詞是指由字母組成，但不包含任何空格的字符串。
我的題解：

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        lastindex = 0
        res = 0
        for i in s:
            if i == " ":
                lastindex = 0
            else:
                lastindex = lastindex + 1
            if lastindex > 0:
                res = lastindex
        return res

方法的效率不是太高。

解題思路：
每次遇到空格的時(shí)候，單詞的長度就置空，不是的話就加1，然后用res記錄上一次的lastindex長度。
其他
這題也要再多刷一次。

第二題

53. 最大子序和
難度：簡單
給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
我的題解：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxSum = nums[0]
        sum = 0
        for i in nums:
            sum = sum + i
            if sum > maxSum:
                maxSum = sum
            if sum < 0:
                sum = 0
        return maxSum

解題思路：
這題是參考了小佳揚(yáng)的思路。
重點(diǎn)考慮什么時(shí)候會(huì)有最大的值。
maxSum其實(shí)相當(dāng)于一個(gè)記住上次最大值的點(diǎn)，sum則是移動(dòng)的點(diǎn)。
當(dāng)遇到會(huì)導(dǎo)致總和小于0的值，那一定是要排除的，因?yàn)榭隙〞?huì)拉低總和大小。
其他：
這次還要多考慮情況，然后再刷一次。

第三題

35. 搜索插入位置
難度：簡單
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(shè)數(shù)組中無重復(fù)元素。
我的題解：

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        for i in range(length):
            if nums[i] == target:
                return i 
            if nums[i] > target:
                nums.insert(i,target)
                return i
        nums.append(target)
        return length

解題思路：
用了insert的辦法，找到對(duì)應(yīng)的Index之后插入即可。

第四題

28. 實(shí)現(xiàn)strStr()
難度：簡單
實(shí)現(xiàn) strStr() 函數(shù)。

給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)。如果不存在，則返回 -1。
我的題解：

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if needle == "":
            return 0
        length_a = len(needle)
        length_b = len(haystack)
        if length_b < length_a:
            return -1
        for i in range(length_b):
            if haystack[i] == needle[0]:
                for j in range(length_a):
                    if i+j == length_b:
                        return -1
                    if haystack[i+j] != needle[j]:
                        i = -1
                if j == length_a-1 and i !=-1:
                    return i 
        i = -1
        return i

解題思路：
這串代碼其實(shí)寫的有點(diǎn)土，還得優(yōu)化下，用的就是反復(fù)循環(huán)check，暴力破解。