[数据结构与算法]leetcode-指剑offer

1. 剑指 Offer 54. 二叉搜索树的第k大节点
2. 剑指 Offer 55 - I. 二叉树的深度
3. 剑指 Offer 55 - II. 平衡二叉树
4. 剑指 Offer 57. 和为s的两个数字
5. 剑指 Offer 57 - II. 和为s的连续正数序列
6. 剑指 Offer 58 - I. 翻转单词顺序
7. 剑指 Offer 58 - II. 左旋转字符串
8. 剑指 Offer 61. 扑克牌中的顺子

剑指 Offer 54. 二叉搜索树的第k大节点

二叉搜索树的中序遍历为递增序列，因此这个题目就倒着中序遍历，就可以得到递减序列，然后到第k大的节点的值

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        def dfs(root):
            if not root:
                return
            dfs(root.right)
            self.k -= 1
            if self.k == 0:
                self.res = root.val
                return root.val
            dfs(root.left)
        self.k = k
        dfs(root)
        return self.res

剑指 Offer 55 - I. 二叉树的深度

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return 1+max(left, right)

剑指 Offer 55 - II. 平衡二叉树

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            return 1+max(left, right)
        if not root:
            return True
        elif abs(dfs(root.left)-dfs(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right):
            return True
        return False 

剑指 Offer 57. 和为s的两个数字

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums)-1
        while left < right:
            if nums[left] + nums[right] == target:
                return [nums[left], nums[right]]
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                left += 1

剑指 Offer 57 - II. 和为s的连续正数序列

滑动窗口：左右双指针，当窗口内的数字和小于target的时候将右边界+1，即在右边增加一个数字，大于target的时候将左边界+1，即删去原本窗口左边的第一个数字，等于就记录下来。

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        left, right = 1, 1
        summ = 0
        while left <= target//2: # right <= (target//2)+1
            if summ < target:
                summ += right
                right += 1
            if summ > target:
                summ -= left
                left += 1
            if summ == target:
                tmp = list(range(left,right))
                res.append(tmp)
                summ -= left
                left += 1
        return res

剑指 Offer 58 - I. 翻转单词顺序

class Solution:
    def reverseWords(self, s: str) -> str:
        stack = []
        right = 0
        ans = ""
        n = len(s)
        s += " "
        for i in range(n):
            if i == 0 and s[i] != " ":
                left = i
                right = 1
            if s[i] == " " and s[i+1] != " ":
                left = i+1
                right = 1
            if right and s[i+1] == " " and s[i] != " ":
                stack.append(s[left:i+1])
                right = 0
        if right:
            stack.append(s[left:])
        while stack:
            ans += stack.pop()
            ans += " "
        return ans[:-1]

class Solution:
    def reverseWords(self, s: str) -> str:
        p=s.split()[::-1] # 将s以空格为分割符进行分割，得到的list反向保存在p中
        # p = s.strip().split()
        st=""
        for i in p: # 在单词之间加空格
            st+=i
            if i!=p[-1]: # 最后一个单词后面不加
                st+=" "
        return st

剑指 Offer 58 - II. 左旋转字符串

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:]+s[:n]

剑指 Offer 61. 扑克牌中的顺子

牌的取值范围是【0-13】，0可以代替任意数字，因为要求是五张，因此最大和最小差<5 且不能有重复的牌。

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        a = []
        for i in nums:
            if i == 0: continue
            if i in a: return False
            else: a.append(i)
        return max(a)-min(a) < 5