Leetcode编程实践

利用在线资源如LeetCode进行实践 #生活知识# #生活经验# #编程#

文章目录 一. 知识点 1.1 二分查找 1.2 数据结构：字典/集合 1.3 巧用Python的内置函数 二. 查找算法的应用 35. 搜索插入位置 202. 快乐数 √ 242. 有效的字母异位词 √ 205. 同构字符串 290. 单词规律 349. 两个数组的交集 350. 两个数组的交集 II 410. 分割数组的最大值 √ 451. 根据字符出现频率排序 540. 有序数组中的单一元素 √ 三. 参考资料 一. 知识点 1.1 二分查找

A）注意点

外层循环必须是l < r 内部用if判断是否满足条件 -> 修改上下界 若下界修改为r = mid - 1，则前面mid 语句应为mid = (l + r + 1) //2（避免死循环）

B）二分查找算法模板

假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半。当l = r时，即找到了目标值。
1）右半段 - 找满足某条件的第一个数（例如：大于等于给定数的第一个位置）

将区间[l, r]划分成[l, mid]和[mid + 1, r]，更新操作是r = mid或者l = mid + 1

while l < r: mid = (l + r) >> 1 if check(mid): r = mid else: l = mid + 1 return l 1234567

2）左半段 - 找满足某条件的最后一个数（例如：小于等于给定数的最后一个位置）

将区间[l, r]划分成[l, mid - 1]和[mid, r]，更新操作是r = mid - 1或者l = mid

while l < r: mid = (l + r + 1) >> 1 # 为了防止死循环，额外+1 if check(mid): l = mid else: r = mid - 1 return l 1234567 1.2 数据结构：字典/集合

空间换时间，多用字典

A）字典的排序操作

s = sorted(dic.items(), key=lambda x:x[1], reverse = True) # 根据value值由大到小排序 keys = sorted(dic, key = dic.get) # 根据value由小到大排序，返回key s = sorted(dic.items(), key=lambda x:x[0]) # 根据key由小到大排序

B）集合
查找有无常用集合~ 集合内部实现是dict，在in操作上也是O(1)。

1.3 巧用Python的内置函数

A）Python zip() 函数

将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。

例如：输入a = [1,2,3], b = [4,5,6], zipped = zip(a,b) # 打包为元组的列表 => 输出[(1, 4), (2, 5), (3, 6)]

B）Python map() 函数

第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表

例如：输入map(lambda x: x ** 2, [1, 2, 3, 4, 5]) # 使用 lambda 匿名函数 => 输出[1, 4, 9, 16, 25]

二. 查找算法的应用 35. 搜索插入位置

A）题目描述

35. Search Insert Position

给定排序数组和目标值，如果找到目标，则返回索引。如果不是，则返回按顺序插入索引的位置的索引。 您可以假设数组中没有重复项。

B）思路

有序数组，考虑二分。题目可转化为 - 返回有序数组中第一个大于等于目标元素的位置。

r = len(nums)因为最终结果可能超出数组范围
右半段套用模板1（即更新操作是r = mid或者l = mid + 1）

C）代码
时间复杂度O(logn)，空间复杂度O(1)

class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ l, r = 0, len(nums) while l < r: mid = (l + r) >> 1 if nums[mid] == target: return mid if nums[mid] > target: r = mid else: l = mid + 1 return l

1234567891011121314151617 202. 快乐数 √

A）题目描述

202. Happy Number

编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

B）思路 & 代码

非happy数求解的中间结果会是非1的无休止的循环.

思路1 - 考虑将中间结果存入集合中，判断是否进入循环。空间复杂度O(n)
时间复杂度O(n)，空间复杂度O(n)

class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ record = set() num = n while num != 1: summ = 0 while num: summ += (num % 10) ** 2 num //= 10 if summ in record: return False num = summ record.add(summ) return True

123456789101112131415161718

思路2 - 优化解法：用快慢指针 - 判断是否有环，将空间复杂度降低到O(1)
时间复杂度O(n)，空间复杂度O(1)

class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ slow, fast = n, self.getNext(n) while slow != fast: if slow == 1 or fast == 1: return True 12345678910

网址：Leetcode编程实践 https://www.yuejiaxmz.com/news/view/517030

相关内容

python编程实践
Python实现个人记账系统：高效管理财务的编程实践
幸福生涯实践教程
实用的生活查询工具
【LeetCode/力扣】1723. 完成所有工作的最短时间
藤编家具：环保理念在生活中的实践
生活美学实践课程.pptx
纸编小篮子（教案） 综合实践活动三年级上册
金小 实践课程
整理厨房综合实践课程设计.pptx

随便看看