第一周周报完整 pdf 版下载地址:
https://t.zsxq.com/rBMVzbM
第二周周报完整 pdf 版星球内下载
作者:算法刷题日记全体星友
版权归属:算法刷题日记全体星友
整理:振哥
哈希表是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。
有两种不同类型的哈希表:哈希集合和哈希映射。
哈希集合是集合数据结构的实现之一,用于存储非重复值。
哈希映射是映射数据结构的实现之一,用于存储(key, value)键值对。
哈希表的关键思想是使用哈希函数将键映射到存储桶。
当插入一个新键时,哈希函数决定该键应该分配到哪个桶中,并将该键存储在相应的桶中;
当搜索一个键时,哈希表使用相同的哈希函数来查找对应的桶,并只在特定的桶中进行搜索。
哈希集是集合的实现之一,对应 Python 中的 set 类型
哈希映射是用于存储 (key, value) 键值对的一种实现,对应 Python 中的dict类型
设计哈希表时,选择合适的键是一门艺术。
这次 Day 10:字母异位词分组 打卡题来训练一下,如何为哈希表设计合适的键。
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明:
所有输入均为小写字母。
不考虑答案输出的顺序。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
今天很多星友都提交了很不错的答案,切实感受到设计哈希表的键是一门艺术,同时也真正体会到众人拾柴火焰高,越来越喜欢咱们的星友们和这个平台,我们一起加油走下去,3个月后遇见更好的自己。
参考大家的打卡,精选几种解法:
对原数组中的每个字符串进行排序,如果是字母异位词,那排序后的字符串肯定就是相等的。因此可以以排序后的字符串为Key,Value则为字符串列表。
以元组统计字符串中每个字符出现的次数,并做为哈希表的Key,Value为字符串列表
质数方式表示,26个小写字母,以26个质数表示,然后把字符串各个字母相乘即对应的各个质数相乘,得出的结果作为Key,Value为字符串列表。
@Leven 星友非常贴心的提示:注意这里如果字符串长度很长,质数相乘的结果可能会造成int溢出,不过Python3只有长整型,以int表示,基本不会溢出。
怎么样,相比大家也切切实实感受到键设计的艺术了吧。
给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb" 输出: 3
示例 2:
输入: J = "z", S = "ZZ" 输出: 0
注意: S 和 J 最多含有50个字母。
J 中的字符不重复。
class Solution:
def numJewelsInStones(self, J: str, S: str) -> int:
石头与宝石,错过的星友查看作业题目:https://t.zsxq.com/F6eMfIE
我看星友们提交的答案都很不错,主要有两种:
时间复杂度是 len(S) * len(J)
@Leven 还给出一种更加 Pythonic 的写法,利用 sum生成器的方法,好处节省内存,大家不妨留意下。
此解法的时间复杂度是 len(S) + len(J)
根据字符哈希为出现次数,然后挑选出出现在宝石串的字符个数。
相信大家这10天的训练,对算法形成一个大概的时间复杂度概念、
等讲完链表后会单独有一天讲时间复杂度分析。
学习链表
链表这个数据结构是绝对的重中之重,它是线性一维结构的代表,插入和删除具有 O(1)复杂度,也是后面讲二叉树等的基础。
因此,链表务必要掌握。
链表又很容易出错,所以只能掌握它的基本定义后,多做练习巩固它。
链表的基本结构:
链表的顺序访问方法:
那么,Day 12 作业题来了:链表中如何删除一个节点?
比如,插入节点Green
请根据上面的提示,补全下面代码:
# 单向链表的定义
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def deleteNode(self, node):
# 补全代码
#
#
这是leetcode 237 题,写完后建议去验证一下,链接:
https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
删除链表的某个节点 target
下面我们看下星友金金金的精彩回答,从链表的建立到删除指定节点,比较全面。
首先建立 1->7->3->6->5->6 的链表,注意查看链表的迭代过程,对于习惯了 i+=1 迭代的朋友,可能对链表的迭代逐渐熟悉起来:tmp=newNode
上面的删除是根据val
判断删除的节点,这与 Day12
题目删除节点 node 略有区别(题目中 target直接就是一个节点指针)
回答这个题目,注意leetcode中237题,是删除非尾部节点。
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
举例,删除节点 5:
第一步:
第二步:
但是,星友们想过没有,为什么要题目要敲掉删除的是非尾部节点。
这是因为,如果删除尾节点,node.next 就不适应上面的操作步骤,必须要找到倒数第二个节点才可,但是对于单向链表只知道当前删除节点 node,是无法定位到的。所以才需要这个限制条件。
对于初次接触链表的朋友,可能觉得使用起来比较别扭,可能需要勤加练习才行和多多理解。
依然考虑到新接触链表的朋友不习惯使用它,本次作业还是强化下链表的基本操作。
# 定义单链表
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def getiNode(head,n,i):
"""
head:链表头结点
n:链表长度
i: 返回的第 i 个节点 nodei
"""
#
#补全代码
#
Day12 作业是删除链表中某个节点node
,Day13 遍历获得链表的第i
个节点,至此相信大家对链表的基本操作已经掌握。
获得长度为n
头节点为head
链表的第i
个节点,代码如下:
def getiNode( head, n, i):
if i < 0 or i > n: # 检查边界条件
raise IndexError
cur = head
for _ in range(i):
cur = cur.next
return cur
对于如下链表,值为23的节点为表头,它的指针域取值是下一个节点的指针,依次类推,最后串成一条线:
这是链表这个数据结构的特点。
这两天训练链表时,也有一些星友实际上完成了列表转化为链表的任务,代码如下所示:
传入lst
转化链表返回cur_Node
:
以上代码实现有一个巧妙之处:self.head=ListNode(None)
,设置一个空的哨兵表头,并使tmp
和cur_Node
分别指向这个空表头,for 中依次创建一个节点,tmp完成链表串联任务。
遍历完成后,cur_Node.next 便是真正的链表表头。
初次接触链表的星友,不妨多理解一下,慢慢就会习惯链表这种数据结构。
反转单链表检验我们是否能够真正灵活使用它,也是面试频频被问道的一个题目。
例如反转上面单链表的方法之一:
黑色结点的下一个结点现在是空。因此,我们停止这一过程并返回新的头结点 15。
根据以上提示,请补全下面代码:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#
#补全代码
#
写完后去这里验证:
https://leetcode-cn.com/explore/learn/card/linked-list/195/classic-problems/750/
反转链表的方法:迭代和递归。
Step 1 先标记下这个节点
Step 2 一个迭代步中,curNode 指向 preNode,便完成当前迭代步的反转
Step 3 每次迭代,preNode 和 curNode 向前移动 1 步
以上步骤归结为如下代码(代码来自我的星友 Leven):
2 递归法 首先反转自 head.next 后的链表,node 此时指向翻转后链表的头部;最后将 head.next 节点链接到 head 节点,最后的最后将 head 节点的 next 域置为 None,因为 head 是终点了。
代码如下:
3 尾递归 还有一位星友诚Slime提供了第二种递归思路,gif 演示如下:
请停留一秒
代码如下:
又是七天一周过去了,Day16 我们思考和讨论如下话题:
程序员一定要学算法吗,说出你为什么要学习算法?
可以参考:https://www.zhihu.com/question/290268306
加入星球 加入星球,从零学程序员必备的算法,每天在星球内记录学习过程并打卡,超赞!
打卡 300 天,退还除平台收取的其他所有费用。
近来经常有朋友问,程序员需要学算法吗?为什么需要学算法?不会算法也能找个Java开发岗造软件所以就别浪费时间了。如果真要学,算法感觉很高深,需要数学,可是我数学不好,所以放弃它吧?
面对这些疑问,我昨日在星球里留作业想听听星友们怎么看,程序员为什么要学习算法。来,一起看看他们的回答。
张=小红= 7 小时前
【打卡】第十五天。算法对我这个数学专业的学生来说,就是一种解决问题的方法。
方法的重要性在于能够在时间性或者空间性上面比起常规解法有领先。
作为学生的话,学习算法更多就是让我在以后就业先人一步?,毕竟你说你会python,然后你就只会调个库,算法什么都不会,那只能算个业余爱好者吧。
更多回答,请参考:为什么还要学算法?且看这 25 个回答,第 17 个回答一针见血!
我们都知道描述机器学习算法好坏的指标常用什么ROC,AUC,精确率和召回率等,机器学习算法也是算法,除了这些,描述算法好坏的一个必备基础指标:时间复杂度,衡量时间复杂度的常见方法:大 O 记号。
今天的作业题:
在大 O 记号下,等于多少?是 O(
)?还是其他?你是怎么得出来的?
一般按照步数严格计算得到
,
为计算规模,但是
往往比较复杂,比如为:
,如果每一个算法都这么去计算衡量效果,这显然不便于交流,所以 1894 年 Paul Bachmann 提出了大 O 记号。
,进一步表达为对于任意
,当计算规模
足够大时,都满足下面式子:
根据如上定义,我们可以看出来,大 O 标记下的
不关心系数
,并且
是对 T(n) 的一种放大,由此得到是算法的最坏情况,这也是我们最关心的,一个算法的最坏情况是什么。
,大 O 记号下等于多少?
根据定义,我们这样放大
:
根据定义只要满足
,
,所以
为 O(
,即最坏时间复杂度为
参考星友 聂磊 2 小时前 的回答:
Day16(计算时间复杂度)学习时间复杂度的基本原则
忽略次要项和常数项,以及最高项的系数,得出时间复杂度为
开根号,即
请列举时间复杂度分别为
,
,
,
,
,
的算法
如果你想从零学习算法,不妨加入下面星球,现在是最划算的时候,还提供专门的星友微信交流社群,每天在星球里记录自己的学习过程,学习其他星友的解题分析思路。打卡 300 天退换除平台收取的其他所有费用。
本文分享自 程序员郭震zhenguo 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!