【基础】哈希基础
《stl源码剖析》、可以了解更多哈希碰撞的细节、了解set multiset unordered_set map multimap unordered_map的底层实现和使用特点
【基础】leetcode 242 有效的字母异位词
两个细节：1.只用一个hash table，不需要两个 2.hash table简化成数组，可以占用更小的内存
"那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。
直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。
不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。"
# python3
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
res = [0] * 26
for c in s:
res[ord(c) - ord('a')] += 1
for c in t:
res[ord(c) - ord('a')] -= 1
for r in res:
if r != 0:
return False
return True
【基础】leetcode 349 两个数组的交集
没想出来计算出两个set之后怎么比较
时间复杂度O（m+n），空间复杂度O（max（m，n））？对吗？对的！跟这位大神想的一样：https://leetcode.cn/problems/intersection-of-two-arrays/solutions/1229152/acm-xuan-shou-tu-jie-leetcode-liang-ge-s-qzbi/?languageTags=python3
hash虽然有key和value，但是一般不会带来量级的变化，空间复杂度一般就是O（n）
不过大神又比我多想到一个优化的细节：自己用dict模拟set时，对于value>1，都令它为1，更方便实现过程中又发现漏了一个细节，遍历第二个数组的时候，如果数值append到结果数组了，要对dict值做置零操作，不然就重复append了
# python3
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
d_nums1 = dict()
res = list()
for num in nums1:
if not d_nums1.get(num):
d_nums1[num] = 1
for num in nums2:
if num in d_nums1.keys() and d_nums1[num] == 1: # 优化：if d_nums1.get(num): 可以这样用吗？首先要知道get的逻辑
res.append(num)
d_nums1[num] = 0
return res
【基础】leetcode 202 快乐数
没想出来，陷入数学题目里面去了
看了解题思路之后，确认直接用python的set实现，但是发现不是很确定set有哪些方法…（还是要多用，多用就熟悉了
时间复杂度O
# python3
class Solution:
def isHappy(self, n: int) -> bool:
sum = n # sum存储平方计算之后的数值
appeared = set()
while sum != 1:
if sum in appeared:
return False
else:
appeared.add(sum)
# mid每次计算平方和都初始化为0
mid = 0
while sum:
mid += (sum % 10) ** 2
sum = sum // 10
sum = mid # 更新sum为新的平方和
return True
【基础】leetcode 1 两数之和
直接看了题解思路，自己尝试用python做一下
判断dict：if target - nums[i] in res判断res是否有key，而我写成了if res.get(target - nums[i])，这样返回值就是括号里的key对应的value，而如果value恰好是0，就不是我的本意了
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = dict()
for i in range(len(nums)):
if target - nums[i] in res:
return [i, res[target - nums[i]]]
else:
res[nums[i]] = i
【复习】leetcode 203 移除链表元素
耗时10min，且漏洞百出
再刷
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy_head = new ListNode(); // 1.指针 2.new
dummy_head -> next = head; // 3.箭头
ListNode* cur = dummy_head;
while (cur -> next != nullptr) {
if (cur -> next -> val == val) {
ListNode* tmp = cur -> next;
cur -> next = cur -> next -> next;
delete tmp; // 4.delete 5.无括号
}
else { // 6.整个else被我省了。。
cur = cur -> next;
}
}
head = dummy_head -> next;
delete dummy_head;
return head;
}
};
【复习】leetcode 707 设计链表
不会写c++的节点和链表类初始化
day6 语法积累
- python3 ascii相关
https://blog.csdn.net/weixin_45750972/article/details/124700242
- python3 defaultdict collections相关
- python3 dict get get不到返回什么？get的返回值是0默认False？dict方法！！！
- python3 判断相等操作的底层逻辑
- python3 要熟悉set的方法有哪些
- c++ 访问链表值和指针用->
- c++ 删除链表节点用delete x ;
