网站建设不足之处,免费房屋设计app,室内设计网站排行榜前十名知乎,网站开发 常德242. 有效的字母异位词
给定两个字符串 s 和 t #xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意#xff1a;若 s 和 t 中每个字符出现的次数都相同#xff0c;则称 s 和 t 互为字母异位词。
class Solution(object):def isAnagram(self, s, t):编写一个函数来判断 t 是否是 s 的字母异位词。 注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。
class Solution(object):def isAnagram(self, s, t)::type s: str:type t: str:rtype: boolss list(s)tt list(t)ss.sort()tt.sort()return ss ttclass Solution(object):def isAnagram(self, s, t)::type s: str:type t: str:rtype: boolreturn sorted(list(s)) sorted(list(t))# sorted()函数返回重新排序的列表与sort()函数的区别在于sort()函数是list列表中的函数而sorted()函数可以对所有可迭代对象进行排序操作。并且用sort()函数对列表排序时会影响列表本身而sorted()函数则不会。class Solution(object):def isAnagram(self, s, t)::type s: str:type t: str:rtype: bool# 两个字典dict1 {} # {a:1 b:2}dict2 {}for ch in s:dict1[ch] dict1.get(ch, 0) 1for ch in t:dict2[ch] dict2.get(ch, 0) 1return dict1 dict274. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中是否存在一个目标值。该矩阵具有如下特性 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 线性查找 or 二分查找
class Solution(object):def searchMatrix(self, matrix, target)::type matrix: List[List[int]]:type target: int:rtype: boolfor line in matrix:if target in line:return Truereturn Falseclass Solution(object):def searchMatrix(self, matrix, target)::type matrix: List[List[int]]:type target: int:rtype: boolh len(matrix) # 长度 几行if h 0:return False #[]w len(matrix[0]) # 宽度 几列if w 0:return False # [[], [], []]left 0right w * h - 10 1 2 34 5 6 78 9 10 11第9个位置num//4行num%4列i num // 4j num % 4while left right: # 二分查找代码 候选区有值mid (left right) // 2i mid // wj mid % wif matrix[i][j] target:return Trueelif matrix[i][j] target: # 待查找的值在mid左侧right mid - 1else: # matrix[mid] target 待查找的值在mid右侧left mid 1else:return False1. 两数之和 167.两数之和 II → 输入无序/有序数组
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
class Solution(object):def twoSum(self, nums, target)::type nums: List[int]:type target: int:rtype: List[int]n len(nums)for i in range(n):for j in range(i):if nums[i] nums[j] target:return sorted([i,j])若为有序数组可二分查找
class Solution(object):def binary_search(self, li, left, right, val): # 二份查找函数# left 0# right len(li) - 1while left right: # 候选区有值mid (left right) // 2if li[mid] val:return midelif li[mid] val: # 待查找的值在mid左侧right mid - 1else: # li[mid] val 待查找的值在mid右侧left mid 1else:return Nonedef twoSum(self, nums, target)::type nums: List[int]:type target: int:rtype: List[int]for i in range(len(nums)):a nums[i]b target - aif b a:j self.binary_search(nums, i 1, len(nums) - 1, b)else:j self.binary_search(nums, 0, i - 1, b)if j:breakreturn sorted([i1, j1]) # 题目需要输出index无序列表的二分查找
class Solution(object):def binary_search(self, li, left, right, val): # 二份查找函数# left 0# right len(li) - 1while left right: # 候选区有值mid (left right) // 2if li[mid][0] val:return midelif li[mid][0] val: # 待查找的值在mid左侧right mid - 1else: # li[mid] val 待查找的值在mid右侧left mid 1else:return Nonedef twoSum(self, nums, target)::type nums: List[int]:type target: int:rtype: List[int]new_nums [[num, i] for i, num in enumerate(nums)] # 二维列表 每一行有 数字num 下标inew_nums.sort(key lambda x:x[0]) # 按照数num排序 new_nums[i][0]是数new_nums[i][1]是原来的下标for i in range(len(new_nums)):a new_nums[i][0]b target - aif b a:j self.binary_search(new_nums, i 1, len(new_nums) - 1, b)else:j self.binary_search(new_nums, 0, i - 1, b)if j:breakreturn sorted([new_nums[i][1], new_nums[j][1]])
