WEEK 2

leetcode:

no_22 括号生成：

image.png

• 思路：
  先通过一个递归程序获取所有的' (' 数为n且括号总数为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

• 思路：
  循环，找到后值比前一位的值小时就返回前一个值的下标，注意左右两侧的边界判定即可
• 代码

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 比较字符串最小字母出现频次

image.png

• 思路
  先设计一个f函数来找出str中的最小字母频次，用两个列表分别装querys和words中的字符串最小字母出现频次，然后利用一个双循环来做比较
• 代码：

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

• 思路：
  一开始是双循环去判断字符串，提交超时，看了评论里的方法。本题如果想到先排序再做就简单了许多。排序后的有序字符串就不再需要双循环了，因为是有序的，每次对比是否是子文件夹时只需要与list的尾元素进行对比。需要注意的是可能会有“/a/b”和"/a/bc"这种情况，只用python内置的find函数做判断的话会造成误判，所以还需要做一下手动的判断。
• 代码

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且平均值大于等于阈值的子数组数目

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循环，
不过执行最后一个用例的时候超时了。
看了题解，用了滑动窗口的解决办法。对比两种解决办法，上面的方法虽然看上去只有一次循环，但是每次循环时都要进行一次sum操作，导致性能低下。而滑动窗口方法只有第一次计算时将k个数字相加了，而后的循环中每一次都是减去首位再加上末尾的下一位并做比较的简易运算。

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的最少斐波拉契数字数目

image.png

思路：
这个题用递归很好理解
在每一层递归中根据传入的K值，构造一个Fib数列，判断尾项与K的大小，确定新的K值，并+1，新的K表示原本K减去了能够被减的最大项，。.如果K为1或2或者K和尾项的值刚好相等，直接return 1即可，表示此时的K只需要一个fib数即可减空。

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

对该递归做了优化后就可以通过了：

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

这个优化是：
1、原本字典的功能只是记录有还是没有，现在通过字典值的递增，不仅记录了某个文件名有或者是没有，还记录了有具体多少个，减少了后续操作 （但是不能完全依赖该记录值，不然再某些特定输入下会报错，比如：["a(1)","a","a","a"]，不过相比以前的话，还是可以有效降低递归层数的）
2、给递归函数增加了一个参数，这个参数始终记录初次传入该递归函数时的字符串原值，并保证在递归过程中不变，简化了字符串的拼接操作

浅层神经网络

page1
page2
page3
page4
page5
page6
page7