lc marathon 7.26

146. LRU cache

utilize python Of dic Deposit in key There is a sequence

Add a number ： If the number exists , Delete the original , Rejoin the number And update the value

                     If the number does not exist , And it's full , Then delete the first key. If it is not full, you can save it directly 

Access a number ： If the number exists , The retention value, Then delete , Save again

                     non-existent , return -1

class LRUCache:

    def __init__(self, capacity: int):
        self.dic={
    }
        self.cap=capacity


    def get(self, key: int) -> int:
        if key in self.dic.keys():
            value=self.dic[key]
            del self.dic[key]
            self.dic[key]=value
            return self.dic[key]
        return -1


    def put(self, key: int, value: int) -> None:
        if key in self.dic.keys():
            del self.dic[key]
         
        elif len(self.dic.keys())>=self.cap:
            del self.dic[list(self.dic.keys())[0]]
        self.dic[key]=value

130. The surrounding area

First of all, for every one on the boundary ’O’ Do depth first search , All that will be connected to it ’O’ Change it to ’-‘. Then traverse the matrix , Put all of... In the matrix ’O’ Change it to ’X’, Put all of... In the matrix ’-‘ Turn into ’O’

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """ Do not return anything, modify board in-place instead. """
        """ Do not return anything, modify board in-place instead. """
        for i in range(len(board)):
            if board[i][0]=='O':
                vis=[[ 0 for j in range(len(board[0]))] for i in range(len(board))]
                dfs(board,i,0,vis)
            if board[i][len(board[0])-1] == 'O':
                vis = [[0 for j in range(len(board[0]))] for i in range(len(board))]
                dfs(board,i,len(board[0])-1,vis)
        for j in range(len(board[0])):
            if board[0][j]=='O':
                vis=[[ 0 for j in range(len(board[0]))] for i in range(len(board))]
                dfs(board,0,j,vis)
            if board[len(board)-1][j] == 'O':
                vis = [[0 for j in range(len(board[0]))] for i in range(len(board))]
                dfs(board,len(board)-1,j,vis)
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]=='O':
                    board[i][j]='X'
                if board[i][j]=='-':
                    board[i][j]='O'
        
                
        
    


def dfs(board,i,j,visited):
    #  Border crossing 
    if i<0 or i>=len(board) or j<0 or j>=len(board[0]):
        return
    #  Can't move forward 
    print(i,j)
    if board[i][j]=='X':
        return
    #  Have visited 
    if visited[i][j]==1:
        return 
    #  Accessible O, Replace with others first 
    if board[i][j]=='O':
        board[i][j]='-'
        visited[i][j]=1
        #  To move forward 
        dfs(board, i - 1, j, visited)
        dfs(board, i + 1, j, visited)
        dfs(board, i, j-1, visited)
        dfs(board, i, j+1, visited)
        visited[i][j]=0
    return 

133. Clone map

The key is to establish the mapping from old nodes to new nodes

Then traverse with depth

""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """
dic={
    }
ls=set()
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node ==None:
            return None
        global dic,ls
        dic={
    }
        ls=set()
        dfs(node)
        for old_node in list(ls):
            dic[old_node].neighbors=[dic[old_neighbor] for old_neighbor in old_node.neighbors]
        return dic[node]



def dfs(node):
    global dic,ls
    if node==None:
        return
    if node in ls:
        return 
    #  Copy   And establish old nodes - Mapping of new nodes 
    new_node=Node(val=node.val)
    dic[node] = new_node
    #  Save the original node
    ls.add(node)
    for inode in node.neighbors:
        dfs(inode)
    return

134. Gas station

There is a ring road with n One site ; Every site has a good person or a bad person ; Good people will give you money , The bad guys will charge you a certain toll , If you don't have enough money to pay the fare , Bad guys will jump up and cut you to death ; ask ： From which station , Can go around and get back to the starting point alive ?

First consider a situation ： If all the good people give you My money adds up Less than The sum of the tolls charged by the bad guys , Then there will always be a time when you don't have enough money to pay the fare , Your ending is doomed to be cut to death .

If you choose at random start set out , Then you will definitely choose a site with good people to start , Because you didn't have money at first , If you meet bad people, you can only be hacked to death ;

Now you are start set out , Went to a site end, By end The bad guys on the site are hacked to death , Explain that you are [start, end) There is not enough money saved to pay end Some bad guys' tolls , because start The site is a good man , So in (start, end) Start at any point in the , You'll save less money than you do now , Still will be end The bad guys on the site are hacked to death ;

So you reread the file , Smart choices start with end+1 Leaves at , Continue your tragic journey ; One day at last , You find yourself at the end （ The subscript is n-1) Without being hacked to death ; Now you hesitate , Then I'll go on , If you have enough money on you, go on to the starting point Start?

Certainly. , Because I have judged at the beginning , The amount of money a good person gives you is greater than or equal to the toll charged by a bad person , The money you save now can cope with [0, start) The passage fee charged by the bad guys to you . At this time, the corners of your mouth rise slightly , The eyes are slightly moist , Because you already know the ultimate mystery of the world ：Start It's the answer to this question .

Why if k+1->end All can pass normally , And rest>=0 It shows that the car started from k+1 Starting from the station can complete the whole journey ？

• because , The starting point divides the current path into A、B Two parts . among , There must be (1)A Part of the remaining oil <0.(2)B Part of the remaining oil >0.

• therefore , No matter how many stations , Can be abstracted into two sites （A、B）.(1) from B Fill up the station and start ,(2) Go to A standing , vehicle refueling ,(3) Reopen B The process of standing .

a key ：B Remaining oil >=A Lack of total oil . Must be able to launch ,B Remaining oil >=A The lack of oil in each sub site of the site .

The problem can be abstracted into two stations

B standing Extra oil can be obtained A standing Consume more oil

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 0 1 2 3 4 
        # -2 -2 -2 3 3
        start=0
        havgas=0
        co=[ga-cos for ga,cos in zip(gas,cost)]
        if sum(co)<0:
            return -1
        for index,c in enumerate(co):
            havgas+=c
            if havgas<0:
                start=index+1
                havgas=0
        return start