# 2021/4/5
目录
反转字符串
【题目】
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
【我的代码】
tip之用一个非常优雅的方式来交换变量：
x,y = y,x原因：Python的变量并不直接存储值，而只是引用一个内存地址，交换变量时，只是交换了引用的地址。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
if len(s)<2:
return
i = 0
j = len(s)-1
while(i<j):
s[i],s[j]=s[j],s[i]
i+=1
j-=1
执行结果：
执行用时：64 ms, 在所有 Python3 提交中击败了14.32%的用户
内存消耗：19.2 MB, 在所有 Python3 提交中击败了32.27%的用户
【其他代码】
@
lollipopnougat
的评论：
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s[:]=s[::-1]
执行结果：
执行用时：52 ms, 在所有 Python3 提交中击败了57.14%的用户
内存消耗：19.3 MB, 在所有 Python3 提交中击败了9.30%的用户
将有序数组转换为二叉搜索树
【题目】
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列
【我的代码】
递归。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if len(nums) == 0:
return None
else:
midn = len(nums)//2
root = TreeNode(nums[midn],self.sortedArrayToBST(nums[:midn]),self.sortedArrayToBST(nums[midn+1:]))
return root
执行结果：
执行用时：52 ms, 在所有 Python3 提交中击败了66.11%的用户
内存消耗：15.9 MB, 在所有 Python3 提交中击败了99.49%的用户
二叉树的最大深度
【题目】
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
【我的代码】
递归。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
elif not root.left:
return 1+self.maxDepth(root.right)
elif not root.right:
return 1+self.maxDepth(root.left)
else:
return 1+max(self.maxDepth(root.right), self.maxDepth(root.left))
执行结果：
执行用时：40 ms, 在所有 Python3 提交中击败了97.47%的用户
内存消耗：16.6 MB, 在所有 Python3 提交中击败了48.25%的用户