438. 找到字符串中所有字母异位词Medium _数组

日常刷题
821. 字符的最短距离（Easy）
4月19号的每日一题。一道简单题。
做法1：遍历每一个位置ｉ，然后在ｉ处定义两个指针 l e f t , r i g h t left, right left,right，两个指针同时向左右移动，当其中一个到头的时候，只移动另一个。直到两个指针中至少有一个指向的字符为目标 c c c 。
想法很简单，复杂度很高。为 O ( n 2 ) O(n^2) O(n2)
class Solution:def shortestToChar(self, s: str, c: str) -> List[int]:ans = [0] * len(s)for i in range(len(s)):cur = s[i]left, right = i, i# 左边走到头了或者没走到头但是不是c and 右边走到头了或者没走到头但是不是cwhile(left == -1 or s[left] != c) and (right == len(s) or s[right] != c):if left >= 0:left -= 1if right < len(s):right += 1# 如果左边没找到，那么left=-1，如果右边没找到，那么right=nif left == -1: ans[i] = right - ielif right == len(s): ans[i] = i - leftelse: ans[i] = min(i-left, right-i)return ans
为什么每次在位置 i i i上都要向左右两边遍历呢。其实可以想象，位置 i i i左边和右边的 c c c的位置和 i ? 1 i-1 i?1是没区别的，只要他们两个都不是 c c c，只是相对位置有变化。那么，每次在位置 i i i，不需要再重新开始向左右两边遍历了。
class Solution:def shortestToChar(self, s: str, c: str) -> List[int]:n = len(s)ans = [1] * n# 左边的c，如果左边没c，就加上一个很大的数，之后取min的时候会直接passidx = -2 * n# 只要是一个大于n的数即可for i in range(n):if s[i] == c:idx = ians[i] = i - idx # 右边的cidx = 3 * n# 只要是一个大于n的数即可for i in range(n-1, -1, -1):if s[i] == c:idx = ians[i] = min(ans[i], idx-i)return ans
230. 二叉搜索树中第K小的元素（）
暴力解法，利用二叉搜索树中序遍历是递增序列的特性。
# 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 = rightclass Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:# 二叉搜索树的中序遍历是递增序列nums = []def dfs(root):if not root: returndfs(root.left)nums.append(root.val)dfs(root.right)dfs(root)return nums[k-1]
使用迭代法的话，可以不需要遍历整棵树，只需要找到K个从最小开始递增的数即可。
# 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 = rightclass Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:# 使用迭代法来进行中序遍历，当从小到大找到k个数时就可以停止stack = []while root or stack:while root:# 先暂存根节点，一致往左遍历到空节点stack.append(root)root = root.leftroot = stack.pop()k -= 1if k == 0: return root.valroot = root.right
739. 每日温度
暴力解法，会超时。
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)res = [0] * nfor i in range(n-1):if temperatures[i+1] > temperatures[i]:res[i] = 1continuefor j in range(i+1, n):if temperatures[j] > temperatures[i]:res[i] = j - ibreakreturn res
单调栈解法：
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)res = [0] * nstack = []for i in range(n):temperature = temperatures[i]while stack and temperature > temperatures[stack[-1]]:prev_index = stack.pop()res[prev_index] = i - prev_indexstack.append(i)return res