WEEK 2 - 簡書

leetcode:

no_22 括號生成：

image.png

思路：
先通過一個遞歸程序獲取所有的' (' 數(shù)為n且括號總數(shù)為2*n的括號排列字符串歌馍，放在一個list中滚朵。再對該list遍歷湾碎，找出符合要求的字符串尸闸。
代碼：

class Solution(object):
    def generateParenthesis(self, n):
        allUse = []
        def myget(now,n1,n2):
            if n1==0 and n2==0:
                allUse.append(now)
                return 0
            if n1 == 0 and n2 > 0:
                now += ')'
                myget(now,n1,n2-1)
            if n1 > 0 and n2==0:
                now+='('
                myget(now,n1-1,n2)
            if n1 > 0 and n2 > 0:
                myget(now + '(', n1 - 1, n2)
                myget(now + ')', n1, n2 - 1)
        myget('',n,n)
        result = []
        for i in range(len(allUse)):
            this_str = allUse[I]
            top = 0
            flag = 0
            for j in range(len(this_str)):
                if this_str[j] == '(':
                    top += 1
                else:
                    if top == 0:
                        flag = 1
                        break
                    else:
                        top -= 1
            if flag == 0:
                result.append(this_str)
        return result

no_162 尋找峰值

image.png

思路：
循環(huán)觉增，找到后值比前一位的值小時就返回前一個值的下標兵拢，注意左右兩側(cè)的邊界判定即可
代碼

class Solution(object):
    def findPeakElement(self, nums):
        if len(nums) == 1:
            return 0
        for i in range(len(nums)):
            if i == 0 :
                last = nums[0]
            else:
                if nums[i] > last:
                    last = nums[I]
                if nums[i] < last:
                    return i-1
            if i==len(nums)-1:
                return I

no_1170 比較字符串最小字母出現(xiàn)頻次

image.png

思路
先設(shè)計一個f函數(shù)來找出str中的最小字母頻次，用兩個列表分別裝querys和words中的字符串最小字母出現(xiàn)頻次逾礁，然后利用一個雙循環(huán)來做比較
代碼：

class Solution(object):
    def numSmallerByFrequency(self, queries, words):
        def f(mystr):
            return mystr.count(min(mystr))
        queries_num = []
        words_num = []
        for i in range(len(queries)):
            queries_num.append(f(queries[I]))
        for i in words:
            words_num.append(f(i))
        # print(queries_num)
        result = []
        for i in range(len(queries_num)):
            num = 0
            for j in range(len(words_num)):
                if words_num[j] > queries_num[I]:
                    num+=1
            result.append(num)
        return result

no_1233 刪除子文件夾

image.png

思路：
一開始是雙循環(huán)去判斷字符串说铃，提交超時，看了評論里的方法嘹履。本題如果想到先排序再做就簡單了許多腻扇。排序后的有序字符串就不再需要雙循環(huán)了，因為是有序的砾嫉，每次對比是否是子文件夾時只需要與list的尾元素進行對比幼苛。需要注意的是可能會有“/a/b”和"/a/bc"這種情況，只用python內(nèi)置的find函數(shù)做判斷的話會造成誤判焕刮，所以還需要做一下手動的判斷舶沿。
代碼

class Solution(object):
    def removeSubfolders(self, folder):
        mylist = folder
        mylist.sort()
        out = []
        top = -1
        for item in mylist:
            if top == -1:
                out.append(item)
                top += 1
            else:
                topStr = out[top]
                if item.find(topStr) == 0:
                    if item[len(topStr):][0] != '/':
                        out.append(item)
                        top += 1
                else:
                    out.append(item)
                    top += 1
        return out

no_1343 大小為K且平均值大于等于閾值的子數(shù)組數(shù)目

image.png

思路：
一開始用的這樣的代碼：

class Solution(object):
    def numOfSubarrays(self, arr, k, threshold):
        flag = 0
        for i in range(len(arr)-k+1):
            sum_n = sum(arr[i:i+k])
            if sum_n / k >= threshold:
                flag += 1
        return flag

代碼相對精簡且只有一次顯式的for循環(huán)，
不過執(zhí)行最后一個用例的時候超時了济锄。
看了題解暑椰，用了滑動窗口的解決辦法霍转。對比兩種解決辦法荐绝，上面的方法雖然看上去只有一次循環(huán)，但是每次循環(huán)時都要進行一次sum操作避消，導(dǎo)致性能低下低滩。而滑動窗口方法只有第一次計算時將k個數(shù)字相加了，而后的循環(huán)中每一次都是減去首位再加上末尾的下一位并做比較的簡易運算岩喷。

class Solution(object):
   def numOfSubarrays(self, arr, k, threshold):
       flag = 0
       start = 0
       allN = sum(arr[0:k]) - k*threshold
       if allN >= 0:
           flag += 1
       while k<len(arr):
           allN = allN + arr[k] - arr[start]
           k +=1 
           start += 1
           if allN >= 0 :
               flag += 1
       return flag

no_1414 和為K的最少斐波拉契數(shù)字數(shù)目

image.png

思路：
這個題用遞歸很好理解
在每一層遞歸中根據(jù)傳入的K值恕沫，構(gòu)造一個Fib數(shù)列，判斷尾項與K的大小纱意，確定新的K值婶溯，并+1，新的K表示原本K減去了能夠被減的最大項偷霉，迄委。.如果K為1或2或者K和尾項的值剛好相等，直接return 1即可类少，表示此時的K只需要一個fib數(shù)即可減空叙身。

class Solution(object):
    def findMinFibonacciNumbers(self, k):
        def getFib(K):
            Fib = [1, 1]
            fib = 0
            while fib < K:
                fib = Fib[-1] + Fib[-2]
                Fib.append(fib)
            if K == 1 or K == 2:
                return 1
            if Fib[-1] == K:
                return 1
            if K < Fib[-1]:
                return 1+getFib(K-Fib[-2])
            if K>Fib[-1]:
                return 1+getFib(K-Fib[-1])
        return getFib(k)

no_1487 保證文件名唯一

image.png

一開始的遞歸，總是超時硫狞。

class Solution(object):
    def getFolderNames(self, names):
        mylist = names
        mydict = {}
        out = []
        def now(mystr,state):
            if mydict.get(mystr,'no') == 'no' : #字典中沒有
                mydict[mystr] = 1
                out.append(mystr)
                return
            else: #字典中有這個值了
                if state == 0: #state == 0 表示需要后面加（）
                    a = mystr + "(1)"
                    now(a,1)
                else:
                    flag = len(mystr)-1
                    while flag > 0:
                        if mystr[flag] == '(':
                            strNum_L = flag
                            flag = -1
                        flag -= 1
                    strNum = str(int(mystr[strNum_L+1:-1])+1)
                    # strNum = str(int(mystr[-2])+1)
                    a = mystr[:strNum_L]
                    a = a+'('+strNum+')'
                    now(a,1)
        for item in mylist:
            now(item,0)
        return out

對該遞歸做了優(yōu)化后就可以通過了：

class Solution(object):
   def getFolderNames(self, names):
       mylist = names
       mydict = {}
       out = []
       def now(mystr,a,state):
           if mydict.get(a,'no') == 'no' : #字典中沒有
               mydict[a] = 1
               out.append(a)
               return
           else: #字典中有這個值了
               if state == 0: #state == 0 表示需要后面加（）
                   aa = a + "(1)"
                   now(mystr,aa,1)
               else:
                   k = mydict[a]
                   mydict[a] += 1
                   aa= mystr + "(" + str(k) +")"
                   now(mystr,aa,1)
       for item in mylist:
           now(item,item,0)
       return out

這個優(yōu)化是：
1信轿、原本字典的功能只是記錄有還是沒有晃痴，現(xiàn)在通過字典值的遞增，不僅記錄了某個文件名有或者是沒有财忽，還記錄了有具體多少個倘核，減少了后續(xù)操作（但是不能完全依賴該記錄值，不然再某些特定輸入下會報錯即彪，比如：["a(1)","a","a","a"]笤虫，不過相比以前的話，還是可以有效降低遞歸層數(shù)的）
2祖凫、給遞歸函數(shù)增加了一個參數(shù)琼蚯，這個參數(shù)始終記錄初次傳入該遞歸函數(shù)時的字符串原值，并保證在遞歸過程中不變惠况，簡化了字符串的拼接操作

淺層神經(jīng)網(wǎng)絡(luò)

page1

page2

page3

page4

page5

page6

page7