LeetCode 第十三天 huawei测试准备 python （字符串 二分查找 BFS）

以下题目来源力扣
93. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

终止条件： 搜索路径深度大于4
当搜索路径大于4 且路径别完全分割时，加入正确路径
从0开始遍历到最后的每一个子串，寻找合适正确的地址值，且

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res = []path = []def backip(s,start):if len(path) >4 : #搜索路径大于4，进行剪枝returnif len(path) == 4 and ''.join(path) == s: #搜索路径为4，且s被完全分割# if len(path) == 4 and start == len(s): #或者开始索引的位置是最后的s长度res.append('.'.join(path[:]))for i in range(start,len(s)): #从start 开始c = s[start:i+1] #子串if c and 0<=int(c)<=255 and str(int(c)) == c: #判断是否满足ip地址path.append(c)#加入当前pathbackip(s,i+1) path.pop()#回溯backip(s,0)return res

33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution:def search(self, nums: List[int], target: int) -> int:n=len(nums)def binary_search(nums,left,right):# nums=sorted(nums)while(left<=right):mid=(left+right)//2if target==nums[mid]:return midelif target<nums[mid]:right=mid-1else:left=mid+1return -1max_index=nums.index(max(nums))left_=binary_search(nums,0,max_index)right_=binary_search(nums,max_index+1,n-1)print(left_,right_)if left_==right_==-1:return -1elif left_!=-1:return left_else: return right_

34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def binary_search(nums,left,right,target):# nums=sorted(nums)while(left<=right):mid=(left+right)//2if target==nums[mid]:return midelif target<nums[mid]:right=mid-1else:left=mid+1return -1n=len(nums)left=0right=n-1start_index=binary_search(nums,left,right,target)end_index=start_indexif start_index==-1:return[-1,-1]while  start_index-1>=0 and  nums[start_index-1]==target:start_index=start_index-1while  end_index+1<=n-1  and  nums[end_index+1]==target:end_index=end_index+1return [start_index,end_index]

139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:# dp[i] 表示第i之前的字符串可以被拼接#    递推公式 dp[i]=dp[j]+dp[i-j]#    dp[]dp=[False]*(len(s)+1)dp[0]=Truefor i in range(len(s)):for j in range(i+1,len(s)+1):if dp[i] and s[i:j] in wordDict:dp[j]=Truereturn dp[-1]

130. 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

今天吃了螺狮粉，要早点回去洗漱了，就先到这里了