LeetCode 2022三月刷题日记

LC 232.用栈实现队列

题目大意

请你仅使用两个栈实现先入先出队列,队列支持一般队列支持的所有操作(push、pop、peek、empty) 实现 MyQueue 类:

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空,返回 true ;否则,返回 false  

题解

栈、队列和模拟的综合应用

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MyQueue {
public:
    stack<int> stIn;  //创建一个栈stIn 用于进栈
    stack<int> stOut; //创建一个栈stOut 用于出栈
    MyQueue() {
    }

    void push(int x) {
        stIn.push(x);  //将元素压入栈中
    }

    int pop() {
        if(stOut.empty())  //如果栈stOut为空 则将栈stIn中所有元素压入栈stOut中
        {
            while(!stIn.empty())
            {
                stOut.push(stIn.top());  //将栈stIn栈顶元素压入栈stOut中
                stIn.pop();  //栈顶元素压入栈stOut后将元素删除
            }
        }
        //当栈stOut不为空时 则直接弹出栈stOut栈顶元素
        int res = stOut.top();
        stOut.pop();
        return res;
    }

    int peek() {
        int res = this->pop();  //直接使用已有的pop函数获取栈顶元素
        stOut.push(res);  //因为pop函数弹出了元素res 所以再添加回去
        return res;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();  //当栈stIn和栈stOut都不为空时 队列才不为空
    }
};

LeetCode题解+动画演示:https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/232-yong-zhan-shi-xian-dui-lie-liang-ge-zhan-lai-m/

LC 225.用队列实现栈

题目大意

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、 pop 和 empty)。 实现 MyStack 类:

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。  

题解

栈、队列和模拟的综合应用

方法1:两个队列实现栈

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MyStack {
public:
    queue<int> queue1;  //创建一个队列queue1 用于存储所有入栈元素
    queue<int> queue2;  //创建一个队列queue2 用于临时存储即将入栈的元素
    MyStack() {
    }

    //使用两个队列模拟元素入栈
    void push(int x) {
        queue2.push(x);  //将入栈元素插入临时队列queue2
        while(!queue1.empty())  //将队列queue1中所有元素插入临时队列queue2
        {
            queue2.push(queue1.front());  //将队列queue1中头元素插入队列queue2中
            queue1.pop();  //删除队列queue1头元素
        }
        swap(queue1,queue2);  //为了避免打乱元素顺序 交换队列queue1和queue2
    }

    int pop() {
        int res = queue1.front();
        queue1.pop();
        return res;
    }

    int top() {
        int res = queue1.front();
        return res;
    }

    bool empty() {
        return queue1.empty();  //因为queue1包含了栈中所有元素 所以只需要检查queue1是否为空即可
        //queue2作为临时队列 不永久存储栈中的元素
    }
};

方法二:一个队列实现栈

入栈操作时,首先获得入栈前的元素个数 n,然后将元素入队到队列,再将队列中的前 n 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列,此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。  

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MyStack {
public:
    queue<int> q;
    MyStack() {
    }

    void push(int x) {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int r = q.front();
        q.pop();
        return r;
    }

    int top() {
        int r = q.front();
        return r;
    }

    bool empty() {
        return q.empty();
    }
};

LeetCode题解:https://leetcode-cn.com/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/

LC 112.二叉树路径总和

题目大意

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。  

题解

本题核心思想是对树进行一次遍历,在遍历是记录从根节点到当前节点的路径总和,以防止重复计算。

方法1:广度优先搜索

使用广度优先搜索的方式,记录从根节点到当前节点的路径和,以防止重复计算。 这样我们可以使用两个队列,分别存储将要遍历的节点,以及根节点到这些节点的路径和。  

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr)  //首先判断根节点是否存在
        {
            return false;
        }
        queue<TreeNode*> que_node;  //定义一个队列 用于存储将要遍历的结点
        queue<int> que_val;  //定义一个队列 用于记录从根节点到当前节点路径和
        que_node.push(root);  //将根节点加入第一个队列
        que_val.push(root->val);  //将根节点的值加入第二个队列
        //迭代循环队列 直到队列为空
        while(!que_node.empty())
        {
            TreeNode* now = que_node.front();
            int temp = que_val.front();
            que_node.pop();
            que_val.pop();
            if(now->left == nullptr && now->right == nullptr)  //不存在左右节点 则为叶节点
            {
                if(temp == targetSum)  //判断路径和与目标值是否相等
                {
                    return true;
                }
                continue;  //不相等则迭代继续
            }
            if(now->left != nullptr)  //存在左子节点
            {
                que_node.push(now->left);  //将左子节点加入第一个队列
                que_val.push(now->left->val + temp);//将左子节点值与当前路径和相加加入第二个队列
            }
            if(now->right != nullptr)  //存在右子节点
            {
                que_node.push(now->right);  //将右子节点加入第一个队列
                que_val.push(now->right-val + temp);//将右子节点值与当前路径和相加加入第二个队列
            }
        }
        return false;  //没有满足条件的 返回false
    }
};

方法2:递归

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }
        return hasPathSum(root->left, sum - root->val) 
               hasPathSum(root->right, sum - root->val);
    }
};

LeetCode题解:https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/

LC 98.验证二叉搜索树

题目大意

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。  

题解

有效二叉搜索树定义:
1.节点左子树只包含小于当前节点的数
2.节点右子树只包含大于当前节点的数
3.所有左子树和右子树自身必须也是二叉搜索树

方法1:递归法

定义一个函数bool helper(TreeNode*,long long int lower,long long int upper) 如果上界和下界存在,判断当前节点的值是否在界内,如果不在界内,返回false。将当前节点的值作为上界,继续对node->left进行递归;将当前节点作为下界,继续对node->right进行递归。  

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool helper(TreeNode* root,long long int lower,long long int upper){
        if(root == nullptr)
        {
            return true;  //空节点是合理的二叉搜索树
        }
        if(root->val <= lower  root->val >= upper)  //节点不为空,判断节点上的值是否在上下界内
        {
            return false;
        }
        //更改上下界 递归遍历二叉树的左右子树
        return helper(root->left,lower,root->val) && helper(root->right,root->val,upper);
    }

    bool isValidBST(TreeNode* root) {
        return helper(root,LONG_MIN,LONG_MAX);  //从根节点开始,上下界都为空
    }
};

方法2:中序遍历

根据二叉搜索树的性质,得知二叉搜索树中序遍历得到的值构成的序列一定是升序的,在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的,整棵树是二叉搜索树,否则不是。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;  //定义栈stack来存储未拜访过的树节点
        long long inorder = (long long)INT_MIN-1;  //inorder用来存储上一个遍历到的树节点的值
        while(!stack.empty() || root != nullptr)
        {
            //不断将root的左子节点加入栈 直到没有剩余的左节点
            while(root != nullptr)
            {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();  //将当前子树最左边的节点从stack中取出
            //如果中序遍历得到的节点的值小于等于前一个inorder,说明不是二叉搜索树
            if (root->val <= inorder)
            {
                return false;
            }
            inorder = root->val;  //将inorder设为当前节点的值
            root = root->right;  //将root设为当前节点的右子节点,继续循环
        }
        return true;
    }
};

LeetCode题解:https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/

LC 15.三数之和

题目大意

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。  

题解

方法1:排序+双指针

关键字:不可以包含重复
模式识别:利用排序避免重复答案
降低复杂度变成twoSum
利用双指针找到所有解
数组有序,和为定值的两个数一定可以通过头尾指针向中间移动获得。
关键去重,每次移动跳过与当前值相同的元素,枚举第三个元素也要跳过重复元素。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());  //对数组进行排序方便去重
        //枚举a
        for(int i=0; i<nums.size(); i++)
        {
            if(i>0 && nums[i] == nums[i-1])  continue;  //去重,需要和上次遍历的元素不同
            int target = 0-nums[i];  //定义目标值target,转化为二元组问题target = b+c
            int l = i+1,r = nums.size()-1;  //定义首尾指针,通过首尾指针移动获取定值target
            while(l<r)  //通过首尾指针获取定值target
            {
                if(nums[l]+nums[r] == target)
                {
                    ans.push_back({nums[i],nums[l],nums[r]});  //将符合的元组加入结果ans中
                    while(l<r && nums[l] == nums[l+1])  l++;  //去除重复的左指针元素
                    while(l<r && nums[r] == nums[r-1])  r--;  //去除重复的右指针元素
                    l++;  //左指针向右移
                    r--;  //右指针向左移
                }
                else if(nums[l]+nums[r] > target)
                {
                    r--;  //结果大于目标值,右指针向左移
                }
                else
                {
                    l++;  //结果小于目标值,左指针向右移
                }
            }
        }
        return ans;  //返回结果
    }
};

B站视频讲解:https://www.bilibili.com/video/BV1Jq4y1A7u7?spm_id_from=333.337.search-card.all.click  

LC 705.设计哈希集合

题目大意

不使用任何内建的哈希表库设计一个哈希集合(HashSet)。 实现 MyHashSet 类:

void add(key) 向哈希集合中插入值 key 。

bool contains(key) 返回哈希集合中是否存在这个值 key 。

void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。  

题解

为了实现哈希集合这一数据结构,有以下几个关键问题需要解决:
1.哈希函数:能够将集合中任意可能的元素映射到一个固定范围的整数值,并将该元素存储到整数值对应的地址上。
2.冲突处理:由于不同元素可能映射到相同的整数值,因此需要在整数值出现冲突时,需要进行冲突处理。总的来说,有以下几种策略解决冲突:
链地址法:为每个哈希值维护一个链表,并将具有相同哈希值的元素都放入这一链表当中。
开放地址法:当发现哈希值 hh 处产生冲突时,根据某种策略,从 hh 出发找到下一个不冲突的位 置。例如,一种最简单的策略是,不断地检查 h+1,h+2,h+3,… 这些整数对应的位置。
再哈希法:当发现哈希冲突后,使用另一个哈希函数产生一个新的地址。
3.扩容:当哈希表元素过多时,冲突的概率将越来越大,而在哈希表中查询一个元素的效率也会越来越低。因此,需要开辟一块更大的空间,来缓解哈希表中发生的冲突。

方法1:链地址法

设哈希表的大小为 base,则可以设计一个简单的哈希函数:hash(x) = x mod base。 开辟一个大小为 base 的数组,数组的每个位置是一个链表。当计算出哈希值之后,就插入到对应位置的链表当中。 由于使用整数除法作为哈希函数,为了尽可能避免冲突,应当将 base 取为一个质数。取 base=769。  

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class MyHashSet {
public:
    vector<list<int>> data;  //定义一个数组base,数组的每一个位置是一个链表
    static const int base = 769;  //定义哈希表的大小
    //用链地址法设计一个哈希表
    static int hash(int key)
    {
        return key % base;
    }

    MyHashSet():data(base) {}

    //插入
    void add(int key) {
        int h = hash(key);  //找出key在哈希表中对应的位置
        for(auto it=data[h].begin(); it!=data[h].end(); it++)  //迭代法遍历key在哈希表中对应位置的链表
        {
            //如果插入元素存在 则返回空
            if(*it == key)
            {
                return;
            }
        }
        //如果元素不存在则插入元素
        data[h].push_back(key);
    }

    //删除
    void remove(int key) {
        int h = hash(key);
        for(auto it=data[h].begin(); it!=data[h].end(); it++)
        {
            if(*it == key)
            {
                data[h].erase(it);
                /*
                    注意:data\[h\].erase(it) 这里的it不可写成\*it或者key
                    因为删除的是key在链表上的地址而不是值
                */
                return;
            }
        }
    }

    //判断key是否存在
    bool contains(int key) {
        int h = hash(key);
        for(auto it=data[h].begin(); it!=data[h].end(); it++)
        {
            if(*it == key)  /* 注意:*it */
            {
                return true;
            }
        }
        return false;
    }
};

 

LC 706.设计哈希映射

题目大意

不使用任何内建的哈希表库设计一个哈希映射(HashMap)。 实现 MyHashMap 类:

MyHashMap() 用空映射初始化对象

void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中,则更新其对应的值 value 。

int get(int key) 返回特定的 key 所映射的 value ;如果映射中不包含 key 的映射,返回 -1 。

void remove(key) 如果映射中存在 key 的映射,则移除 key 和它所对应的 value 。  

题解

设计哈希映射设计哈希集合 解法接近,唯一的区别在于哈希映射存储的不是 key 本身,而是键值对(key,value)。  

哈希表增加键值对的函数:map1.insert(make_pair(n,1))
哈希表删除键值对的函数:data[h].erase(it)
哈希表使用迭代器遍历时:
i->first:表示键
i->second:表示值  

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class MyHashMap {
public:
    vector<list<pair<int,int>>> data;
    static const int base = 769;
    static int hash(int key)
    {
        return key % base;
    }

    MyHashMap():data(base) {}

    void put(int key, int value) {
        int h = hash(key);
        for(auto it=data[h].begin(); it!=data[h].end(); it++)
        {
            if(it->first == key)
            {
                it->second = value;
                return;
            }
        }
        data[h].push_back(make_pair(key,value));
    }

    int get(int key) {
        int h = hash(key);
        for(auto it=data[h].begin(); it!=data[h].end(); it++)
        {
            if(it->first == key)
            {
                return it->second;
            }
        }
        return -1;
    }

    void remove(int key) {
        int h = hash(key);
        for(auto it=data[h].begin(); it!=data[h].end(); it++)
        {
            if(it->first == key)
            {
                data[h].erase(it);
                return;
            }
        }
    }
};

LeetCode 2022三月刷题日记
https://yiqiangshiyia.cn/2022/03/11/LeetCode 2022三月刷题日记/
作者
一腔诗意啊
发布于
2022年3月11日
许可协议