【基础】哈希基础

《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 ;