lincode 題目記錄5

Course Schedule 安排課表   Frog Jump  最長迴文字元串長度

Course Schedule 

選課方案問題，題目說的很清楚了就是bfs或者dfs，然後加個字典優化，弄了好久沒弄出來··網上查的演算法··提交的是bfs的演算法，dfs的演算法給的用例好像是遞歸太深了· python編譯器直接崩了··本地調試也是直接崩了··

bfs的核心是用一個數組記錄每個數字的深度··就是要上這個課之前你得上多少門課，把是0的都加到隊列裡邊，後邊遍歷的時候遍歷到這個點的時候 減一，直到減完，遍歷完瞭如果還有點的入度不為0 ，就不能完成

網站上的python不知道是啥版本·· 隊列是大寫的Q ，我本地的是python3.5 是小寫的 ··dfs的遞歸好像通不過

class Solution:
    # @param {int} numCourses a total of n courses
    # @param {int[][]} prerequisites a list of prerequisite pairs
    # @return {boolean} true if can finish all courses or false
    def canFinish(self, numCourses, prerequisites):
        import Queue
        import sys
        sys.setrecursionlimit(1000000)
        if len(prerequisites)<2:return True
        dicp={}
        inlist=[0]*numCourses
        for p in prerequisites:
            dicp.setdefault(p[1],[])
            dicp[p[1]].append(p[0])
            inlist[p[0]] += 1
        q=Queue.Queue()
        for i in range(numCourses):
            if inlist[i] == 0:q.put(i)
        
        while not q.empty():
            cur=q.get()
            if cur not in dicp:continue
            for i in dicp[cur]:
                inlist[i] -=1
                if inlist[i]==0:q.put(i)
        
        for i in inlist:
            if i !=0 :return False

        return True  
        ''' DFS  
        visit=[0]*numCourses
        def canfinishdfs(visit,i):
            if visit[i]==-1:return False
            if visit[i]==1:return True
            visit[i]=-1
            if i in dicp:
                for cur in dicp[i]:
                    if not canfinishdfs(visit,cur):return False
            visit[i]=1
            return True
            
        for i in range(numCourses):
             if not canfinishdfs(visit,i):
                 return False
        
        return True
        '''
        

 安排課程問題，跟上邊一樣·· 加一個數組輸出就行了·最後可以選課就是輸出，不能就是輸出空數組

class Solution:
    # @param {int} numCourses a total of n courses
    # @param {int[][]} prerequisites a list of prerequisite pairs
    # @return {int[]} the course order
    def findOrder(self, numCourses, prerequisites):
        # Write your code here
        import Queue
        dicp={}
        inlist=[0]*numCourses
        for p in prerequisites:
            dicp.setdefault(p[1],[])
            dicp[p[1]].append(p[0])
            inlist[p[0]] += 1
        q=Queue.Queue()
        res=[]
        for i in range(numCourses):
            if inlist[i] == 0:
                q.put(i)
                res.append(i)
        
        while not q.empty():
            cur=q.get()
            if cur not in dicp:continue
            for i in dicp[cur]:
                inlist[i] -=1
                if inlist[i]==0:
                    q.put(i)
                    res.append(i)
                        
        for i in inlist:
            if i !=0 :
                return []
        return res

Frog Jump

跳青蛙問題,從後往前遍歷，從倒數第3個開始計算是否能到達該點，DFS演算法，第一個遞歸的一個迴圈的··，關鍵在那個失敗的緩存節點，

if len(stones)==1:return True
        # memo=set()
        # target=stones[-1]
        # stones=set(stones)
        
        # def bt(cur,k):
        #     if (cur,k) in memo:
        #         return False
        #     if cur==target:
        #         return True
        #     if cur>target or cur<0 or k<=0 or cur not in stones:
        #         return False
        #     dirs=[k-1,k,k+1]
        #     for c in dirs:
        #         if (cur+c)in stones:
        #             if bt(cur+c,c):
        #                 return True
        #     memo.add((cur,k))
        #     return False
        # return bt(0,0)
        
        stone_set, fail = set(stones), set()
        stack = [(0, 0)]
        while stack:
            stone, jump = stack.pop()
            for j in (jump-1, jump, jump+1):
                s = stone + j
                if j > 0 and s in stone_set and (s, j) not in fail:
                    if s == stones[-1]:
                        return True
                    stack.append((s, j))
            fail.add((stone, jump))
        return False

 最長迴文字元串長度·直接分組遍歷就行了：

class Solution:
    # @param {string} s a string which consists of lowercase or uppercase letters
    # @return {int} the length of the longest palindromes that can be built
    def longestPalindrome(self, s):
        # Write your code here
        dics={}
        for i in s:
            dics.setdefault(i,[])
            dics[i].append(i)
        sum=0
        flag=False
        for di in dics:
            n=len(dics[di])
            if n>1:
                if n%2 !=0:
                    sum+=n-1
                    flag=True
                else:
                    sum+=n
            else:
                flag=True
        if flag:sum+=1
        return sum