题解

单词搜索 柱状图最大矩形 解码方法 加油站 分割回文串 单词接龙 最长连续序列

单词搜索


思路

  • 是一个比较典型的dfs
  • 每次搜寻路径的时候需要将已经走过的路径标记已走，但是结束这条路径搜索之后需要重新标为未走，否则后面开始搜寻的路径就没法通过这个格子
  • 这个只需要能找到一条可行的路径，所以只要找到True的路径马上返回！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(board,i,j,vis,word):
            if not word:
                return True
            vis[i][j]=False
            if i+1<len(board) and board[i+1][j]==word[0] and vis[i+1][j] and dfs(board,i+1,j,vis,word[1:]):
                    return True
            if i-1>=0 and board[i-1][j]==word[0] and vis[i-1][j] and dfs(board,i-1,j,vis,word[1:]):
                return True
            if j+1<len(board[0]) and board[i][j+1]==word[0] and vis[i][j+1] and dfs(board,i,j+1,vis,word[1:]):
                return True
            if j-1>=0 and board[i][j-1]==word[0] and vis[i][j-1] and dfs(board,i,j-1,vis,word[1:]):
                return True
            vis[i][j]=True
            return False
        col,rank=len(board),len(board[0])
        vis=[[True] * rank for _ in range(col)]
        for i in range(col):
            for j in range(rank):
                if vis[i][j] and board[i][j]==word[0]:
                    if dfs(board,i,j,vis,word[1:]):return True
        return False

柱状图中最大的矩形


思路

  • 是一个DP题
  • 一个矩形的大小等于宽度*高度，在宽度固定的情况下，高度越高，面积越大
  • 假设当前的立柱是最矮的立柱，创建两个列表l,r分别用来记录以当前立柱为高的矩形的左右坐标
  • l列表从左往右遍历，如果当前柱i比i-1柱高，那么矩形的左坐标为i-1。如果当前柱比i-1柱矮，那么向左去找比i-1柱高的那根柱；
  • r列表从右往左遍历，如果当前柱j不j+1高，那么矩形的右坐标为i+1，如果当前柱比i+1矮，向右去找比i+1高的那根柱；
  • 为了防止无限循环，在原来的柱两边各加一根高度为-1的柱，作为出口
  • 最终得到列表l和r，(l[i]-r[i]-1)*柱高 就能得到当前柱的矩形面积

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(-1)
        heights.insert(0,-1)
        lens=len(heights)
        l=[0]*lens
        r=[lens-1]*lens
        for i in range(1,lens-1):
            if heights[i]>heights[i-1]:
                l[i]=i-1
            else:
                tmp=i-1
                while tmp>=0 and heights[tmp]>=heights[i]:
                    tmp=l[tmp]
                l[i]=tmp
        for i in range(lens-2,0,-1):
            if heights[i]>heights[i+1]:
                r[i]=i+1
            else:
                tmp=i+1
                while tmp<=lens-1 and heights[tmp]>=heights[i]:
                    tmp=r[tmp]
                r[i]=tmp
        mx=0
        print(l,r)
        for i in range(1,lens-1):
            mx=max(mx,(r[i]-l[i]-1)*heights[i])
        return mx

解码方法

思路

  • 是一个加了限制的爬楼梯，也是DP问题
  • 它的限制是这样：
    • 如果当前字符是一个合法的个位数，dp[i]+=dp[i-1]
    • 如果当前字符和前一个字符组成一个合法的十位数，dp[i]+=dp[i-2]
    • 如果当前字符不合法，返回0
  • 最后dp[-1]就是这个字符串的解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0]=='0':
            return 0
        if len(s)==1:
            return 1
        tol=[1,1]
        for i in range(1,len(s)):
            sm=0
            if 0<int(s[i])<=9:
                sm+=tol[-1]
            if int(s[i-1:i+1])<=26 and s[i-1]!='0':
                sm+=tol[-2]
            if sm:
                tol.append(sm)
            else:return 0
        return tol[-1]

加油站


思路

  • 先判断cost是否小于gas，如果不是的话这个车一定跑不了全程
  • 从头开始向后遍历，直到找到第一个gas>cost的加油站，从这里出发
  • 如果当前的加油站不能支持跑完全程，那么当前加油站到达的最后一站开始向后查找gas>cost的加油站，因为从前面的任何一站出发都一定会在这站或这站之前停下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas)<sum(cost):return -1
        i,e,tag=1,-1,-1
        while i!=0:
            if gas[i-1]>=cost[i-1]:
                s=e=i-1             
                oil=gas[i-1]
                while oil>=cost[s]:
                    oil-=cost[s]
                    s=(s+1)%len(gas)
                    oil+=gas[s]
                    if s==e:return e
                i=(s+1)%len(gas)
            i+=1
        return -1

分割回文串


思路

  • 是全排列
  • 从左往右遍历，产生一个、两个、三个…n个字符连在一起的子串比如’aab’可以产生:
    • a,a,b
    • a,ab
    • aa,b
    • aab
  • 如果这个子串是回文串，继续向后遍历，如果到达最后一个字符，把当前结果append进结果列表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res=[]
        def findall(s,path):
            if not s:
                res.append(path)
            for i in range(1,len(s)+1):
                tmp=[]#以i结束的，可产生的回文子串
                if s[:i]==s[:i][::-1]:#如果s[:i]是一个回文子串
                    tmp.append(''.join(s[:i]))
                    findall(s[i:],path+tmp)#迭代以s[i:]开始的字符串
        findall(list(s),[])
        return res

被围绕的区域

思路

  • 一看就是bfs！我一看到dfs和bfs就头痛！
  • 看了别人的高效简洁做法：
  • 先把所有在边缘的O区域都找到，把他们标记出来，比如说把他们变成’P’
  • 标记完了之后从头遍历，如果当前是X->跳过，如果是O->变成X，如果是P->变成O
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def dfs(self,board,i,j,vis,flag):
        #通过vis列表标记已经做过BFS的区域
        if vis[i][j]:
            board[i][j]=flag
            vis[i][j]=False
            #去看当前坐标的上下左右有没有O，有的话把它变成P
            if i+1<len(board) and vis[i+1][j] and board[i+1][j]!='X':
                self.dfs(board,i+1,j,vis,flag)
            if i-1>=0 and vis[i-1][j] and board[i-1][j]!='X':
                self.dfs(board,i-1,j,vis,flag)
            if j+1<len(board[0]) and vis[i][j+1] and board[i][j+1]!='X':
                self.dfs(board,i,j+1,vis,flag)
            if j-1>=0 and vis[i][j-1] and board[i][j-1]!='X':
                self.dfs(board,i,j-1,vis,flag)
        return 
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or len(board[0])<3 or len(board)<3:
            return
        vis=[[True] * len(board[0]) for _ in range(len(board))]
        #遍历矩阵的左右两列，如果有O的话对它BFS
        for i in range(len(board)):
            if board[i][0]=='O' and vis[i][0]:
                self.dfs(board,i,0,vis,'P')
            if board[i][-1]=='O' and vis[i][-1]:
                self.dfs(board,i,len(board[0])-1,vis,'P')
        #遍历矩阵的上下两列，如果有O的话对它BFS
        for j in range(len(board[0])):
            if board[0][j]=='O' and vis[0][j]:
                self.dfs(board,0,j,vis,'P')
            if board[-1][j]=='O' and vis[len(board)-1][j]:
                self.dfs(board,len(board)-1,j,vis,'P')
        #最后一次遍历，把O变成X，P变成O
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]=='O':
                    board[i][j]='X'
                elif board[i][j]=='P':
                    board[i][j]='O'

晕了 bfs真的好长

单词接龙


思路

  • 也是bfs！
  • 引入一个defaultdict(list)，对每个wordlist中的单词进行处理，比如令hot变成*ot h*t ho*，以他们为键，将具有同样形式的单词加入他们的列表中
  • 将beginword也做2中的处理，然后对它进行bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        from collections import defaultdict
        if  not (beginWord or endWord or wordList):return 0
        dic=defaultdict(list)
        def bfs(endWord,q,dic,step):
        '''广度遍历dic，如果没有结果的话返回0，有结果的话返回步数'''
            if endWord in q:
                return step+1
            tmp=[]
            #通过队列实现bfs
            while q:
                for i in range(len(q[0])):
                    cur=list(q[0])
                    cur[i]='*'
                    cur=''.join(cur)
                    if dic[cur]:
                        tmp+=dic[cur]
                        dic.pop(cur)
                q.pop(0)
            return bfs(endWord,tmp,dic,step+1) if tmp else 0
        #初始化dic
        for i in wordList:
            for j in range(len(i)):
                cur=list(i)
                cur[j]='*'
                cur=''.join(cur)
                dic[cur].append(i)
        step,q=0,[]
        for i in range(len(beginWord)):
            cur=list(beginWord)
            cur[i]='*'
            cur=''.join(cur)
            if dic[cur]:
                q+=dic[cur]
                dic.pop(cur)
        return bfs(endWord,q,dic,1)

最长连续序列


思路

  • 感觉似乎是个DP，不敢确定
  • 引入defaultdict(int)，以当前元素为键，值为当前元素所在序列的长度
  • 如果当前元素-1或者+1也存在在dic中，更新当前键的值，并且更新这个序列左右边界的值
  • 最后遍历defaultdict，输出最长的结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        from collections import defaultdict
        mlen,ind=0,0
        if not nums:return 0
        dic=defaultdict(int)
        for i in nums:
            if dic[i]:continue
            dic[i]+=1
            s=dic[i]+dic[i-1]+dic[i+1]
            #只需更新区间两端的值就好，因为所有区间内的值都会主动更新区间的边界而最后只需输出最大值
            dic[i]=dic[i-dic[i-1]]=dic[i+dic[i+1]]=s
            mlen=max(mlen,s)
        return mlen