LeetCode 每日一题 2021/11/22

LeetCode 每日一题 2021/11/22"/>

LeetCode 每日一题 2021/11/22

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

目录

• • • 11/22 384. 打乱数组
    • 11/23 859. 亲密字符串
    • 11/24 423. 从英文中重建数字
    • 11/25 458. 可怜的小猪
    • 11/26 700. 二叉搜索树中的搜索
    • 11/27 519. 随机翻转矩阵
    • 11/28 438. 找到字符串中所有字母异位词

11/22 384. 打乱数组

i为当前考虑位置
i位置的数随机从[i,n]中选取一个loc
交换i,loc的数值 继续考虑下一个位置

import random
class Solution(object):def __init__(self, nums):""":type nums: List[int]"""self.n = len(nums)self.ori = numsdef reset(self):""":rtype: List[int]"""return self.oridef shuffle(self):""":rtype: List[int]"""ans = []ans.extend(self.ori)for i in range(self.n):loc = random.randint(i,self.n-1)ans[i],ans[loc]=ans[loc],ans[i]return ans

11/23 859. 亲密字符串

分情况考虑
长度不同 必定不可以
如果字符串完全相同 需要存在重复的字符
遍历字符串 记录字符不同的个数
如果超过两个或者只有一个则不可以
如果刚好有两个不同 判断是否调换相同

def buddyStrings(s, goal):""":type s: str:type goal: str:rtype: bool"""if len(s)!=len(goal):return Falseif s==goal:if len(set(s))==len(s):return Falsereturn Truediff = 0diffs = []diffg = []for i in range(len(s)):if s[i]!=goal[i]:diff+=1diffs.append(s[i])diffg.append(goal[i])if diff>2:return Falseif diff==2:if diffs[0]==diffg[1] and diffs[1]==diffg[0]:return Truereturn Falseif diff==1:return False

11/24 423. 从英文中重建数字

按照每个单词特殊字母考虑
zero-z,two-w,four-u,six-x,eight-g
one-o,three-r,five-f,seven-s
nine-n

def originalDigits(s):""":type s: str:rtype: str"""from collections import defaultdictm = defaultdict(int)for c in s:m[c]+=1l = [0]*10l[0] = m['z']l[2] = m['w']l[4] = m['u']l[6] = m['x']l[8] = m['g']l[1] = m['o'] - l[0]-l[2]-l[4]l[3] = m['r'] - l[4]-l[0]l[5] = m['f'] - l[4]l[7] = m['s'] - l[6]l[9] = m['i'] - l[5]-l[6]-l[8]ans = ""for i in range(10):ans += str(i)*l[i]return ans

11/25 458. 可怜的小猪

首先考虑只有一只小猪
m = minutesToTest/minutesToDie
m表示在没有喝到毒药的情况下 小猪最多能和几桶水
那么一只小猪最多可以判断n=m+1桶液体中的毒药 如果喝了m桶都没死 说明最后一桶是毒药
现在如果有两只小猪 则根据两个维度考虑
假设m=2 每次我们给小猪喝3桶液体 小猪1每次喝一行 小猪2每次喝一列
x x x
x x x
x x x
如果小猪1在第1行死了 小猪2在第2列死了 说明毒药的位置在第一行第二列
如果小猪1喝了两行都没死 小猪2喝了两列都没死 说明毒药在第三行第三列
由此可知 两只小猪可以判断出33=9桶液体中的毒药 及nn
一次推导 三只小猪可以试作三维考虑 可以试出nnn桶毒药
回到题目 已知n=minutesToTest/minutesToDie+1 桶buckets已知 求小猪数量
及 n**x<=buckets 求最小的x

def poorPigs(buckets, minutesToDie, minutesToTest):""":type buckets: int:type minutesToDie: int:type minutesToTest: int:rtype: int"""n = minutesToTest/minutesToDie+1num = 0tmp = 1while tmp<buckets:tmp *= nnum +=1return num

11/26 700. 二叉搜索树中的搜索

根据BTS的属性
小于当前节点找左子树 大于当前节点找右子树

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def searchBST(root, val):""":type root: TreeNode:type val: int:rtype: TreeNode"""node = rootwhile node:if node.val==val:return nodeelif node.val<val:node = node.rightelse:node = node.leftreturn node

11/27 519. 随机翻转矩阵

total记录当前拥有的可选择位置个数
每次从[0,total-1]中选择idx = x*n+y (x,y)
选择一个后调换当前位置与最后位置的值 使用map记录map[idx]=total

import random
class Solution(object):def __init__(self, m, n):""":type m: int:type n: int"""self.m=mself.n=nself.total = m*nself.map = {}def flip(self):""":rtype: List[int]"""tmp = random.randint(0,self.total-1)self.total-=1idx = self.map.get(tmp,tmp)self.map[tmp] = self.map.get(self.total,self.total)return [idx//self.n,idx%self.n]def reset(self):""":rtype: None"""self.map={}self.total = self.n*self.m

11/28 438. 找到字符串中所有字母异位词

滑动窗口
need记录需要的字符个数
window记录当前窗口内的字符个数
left,right记录滑动窗口左右边界
allvalid代表需要的字符种类
valid代表当前窗口满足个数的字符种类

def findAnagrams(s, p):""":type s: str:type p: str:rtype: List[int]"""from collections import defaultdictneed=defaultdict(int)window = defaultdict(int)for c in p:need[c]+=1left,right=0,0valid=0allvalid = len(need)ret = []while right<len(s):c = s[right]right+=1if need[c]>0:window[c]+=1if window[c]==need[c]:valid+=1while right-left>=len(p):if valid==allvalid:ret.append(left)d = s[left]left+=1if need[d]>0:if window[d]==need[d]:valid-=1window[d]-=1return ret