本文共 6255 字，大约阅读时间需要 20 分钟。

自古套路留人心，发现自己对递归这块掌握的真的是“感人肺腑“（最近的语文水平断崖式下跌哎）

来看下Leetcode中Tag为Recursion的题目

• [Leetcode 687] ：给定二叉树，求节点值全部相等的最长路径。路径不一定要通过树根。Easy

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def longestUnivaluePath(self, root):        """        :type root: TreeNode        :rtype: int        """        if not root: return 0        left,right,val = root.left,root.right,root.val        return max(self.longestlength(left,val)+self.longestlength(right,val),                   self.longestUnivaluePath(left),self.longestUnivaluePath(right))    def longestlength(self,root,val):        if not root or root.val != val:  return 0        return 1+max(self.longestlength(root.left,val),self.longestlength(root.right,val))

• [Leetcode 395] ：给定一个字符串s（只包含小写字母），定义子串T，其中所有字符出现次数均不少于k次，返回子串T的最大长度。Medium
  思路：统计当前字符串中出现最少次数的字符c和最少次数s.count(c)。如果该次数s.count(c)>=k说明在字符串中所有的字符次数都大于k，否则用c对字符串进行拆分，然后递归求解

class Solution(object):    def longestSubstring(self, s, k):        """        :type s: str        :type k: int        :rtype: int        """        if len(s)
   
    =k: return len(s)        return max(self.longestSubstring(t,k) for t in s.split(c))
   

• [Leetcode 698] ：判断数组nums是否可以划分为k个和相等的子数组，Medium
  思路：记忆化搜索（Search + Memoization）

class Solution(object):    def canPartitionKSubsets(self, nums, k):        """        :type nums: List[int]        :type k: int        :rtype: bool        """        if sum(nums) % k: return False        dmaps = {}        def dfs(nums, target, k):             if nums == []: return False            if k == 1: return sum(nums) == target            key = (tuple(nums), k)            if key in dmaps: return dmaps[key]            size = len(nums)            ans = False            for x in range(1 << size): #枚举所有的子集                tsums = 0                rest = []                for y in range(size):                    if (x >> y) & 1:                        tsums += nums[y]                    else:                        rest.append(nums[y])                if tsums == target and dfs(rest, target, k - 1):                    ans = True                    break            dmaps[key] = ans            return dmaps[key]        return dfs(sorted(nums), sum(nums) / k, k)

• [Leetcode 779] ：第一行写一个0，接下来的每一行，都把上一行的0换成01，把1换成10，求第N行第K列的数字。Medium
  思路：第N行第K列的数字是和第N-1行第K-1列的数字有关系的（这里需要注意下标是从0开始）即(1,2) -> 1 (3,4)-> 2 … 即 N,K 对应 N,(K+1)/2
  然后 0: 1: 0 2: 1
  1: 1: 1 2: 0
  可以归纳为 return 0 if ans ^ (K%2) else 1

class Solution(object):    def kthGrammar(self, N, K):        """        :type N: int        :type K: int        :rtype: int        """        if N == 1: return 0        ans = self.kthGrammar(N - 1, (K + 1) / 2)        return 0 if ans ^ (K%2) else 1

• [Leetcode 794] ：判断一个3X3棋盘是否合法，先者执’X’，后者执’O’，当横纵或者对角线为相同符号则结束游戏。Medium
  思路：统计当前’X’,’O’的个数nx,no 进行判断

class Solution(object):    def validTicTacToe(self, board):        """        :type board: List[str]        :rtype: bool        """        nx = ''.join(board).count('X')        no = ''.join(board).count('O')        wx,wo = self.iswinner(board,'X'),self.iswinner(board,'O')        if wx: return nx == no + 1 and not wo        if wo: return nx == no        return nx - 1 <= no <= nx    def iswinner(self,board,ch):        if any(r == ch * 3 for r in board): return True        if any(c == ch * 3 for c in zip(*board)): return True        if board[0][0] == board[1][1] == board[2][2] == ch: return True        if board[0][2] == board[1][1] == board[2][0] == ch: return True        return False

• [Leetcode 726] ：将分子式展开，返回各原子的个数，Hard
  思路：字符串处理，分情况讨论（其实我觉得这题放在stack更稳妥些）

import collectionsclass Solution(object):    def countOfAtoms(self, formula):        """        :type formula: str        :rtype: str        """        size = len(formula)        def getDigit(idx):            cnt = 0            while (idx < len(formula) and formula[idx].isdigit()):                cnt = cnt*10+int(formula[idx])                idx += 1            idx-=1            if cnt:                return cnt,idx            else:                return 1,idx        stack = [collections.defaultdict(int)]        idx = 0        while(idx
   
    ='A' and token<='Z':                ch = token                idx+=1                while (idx < len(formula) and formula[idx]>='a' and formula[idx]<='z'):                    ch+=formula[idx]                    idx += 1                cnt,idx = getDigit(idx)                stack[-1][ch]=stack[-1][ch]+cnt             elif token=='(':                stack.append(collections.defaultdict(int))            elif token==')':                idx +=1                cnt,idx = getDigit(idx)                for key in stack[-1]:                    stack[-1][key] = stack[-1][key]*cnt                tstack = stack.pop()                for key in tstack:                    stack[-1][key]+=tstack[key]            idx+=1        ret = ''        for x in sorted(stack[-1].items(),key=lambda x:x[0]):            if x[1]!=1:                ret+=x[0]+str(x[1])            else:                ret+=x[0]        return ret
   

• [Leetcode 761] ：特殊二进制字符串满足以下条件
  1.) 字符串0和1出现的次数相等
  2.) 非常关键，字符串开始一定是以1开头，且前缀1出现的次数至少与0出现的次数相等。比如”11100100”是special binary string，因为1出现的次数始终大于等于0。要求我们任意交换两个相邻的特殊二进制串（可以交换任意次）使得最终得到的序列的字典序最大，并且满足是特殊二进制串。Hard
  按照special binary string的定义，首字母一定是”1”，末尾一定是”0”，这两位是我们无法改变的，所以我们完全可以求解子问题：除了首尾的字符串。各位且慢，举个例子”1010”，是special binary string，首尾的确分别是1和0，但很遗憾”01”并不是special binary string啊，那怎么用递归解决啊！所以我们需要确保找到”1A….B0”之后，”A…B”也是special binary string。 很简单，只要第一次出现count == 0的字符串。它除了首尾的子串一定是special binary string。证明：因为”1A….CB0” count = 0，所以，”1A….CB”时，count = 1，如果”B = 1”，只能为”1A…C” ，count = 0，这就提前出现了count = 0的情况，吼吼，与假设矛盾。
  嘿，既然能够找到第一个count = 0的special binary string，并且确保了子问题也是special binary string，就可以递归求解了。不过，最终还需要输出lexicographically，所以排个序再合并之前分解的special binary string.

class Solution(object):    def makeLargestSpecial(self, S):        """        :type S: str        :rtype: str        """        cnt,i,ret = 0,0,[]        for j,v in enumerate(S):            cnt = cnt + 1 if v == '1' else cnt-1            if cnt==0:                ret.append('1'+self.makeLargestSpecial(S[i+1:j])+'0')                i = j+1        return ''.join(sorted(ret)[::-1])

Github答案链接（Python）

转载地址：http://lfqmi.baihongyu.com/