author avatar

Liu Bang

总共 52 篇文章

题目描述

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

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明: 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端...

题目描述

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

方法一:递归

这道题,最最简洁的方法应该就是使用递归了。主要思路是,每两个一组,进行交换,然后递归执行。

 1class Solution {
 2public:
 3    LinkedList* swapPairs(LinkedList* head) {
 4        if (!head || !head->next) return head;
 5        // 当前组下的新的head
 6        LinkedList* newHead = head...

Ref: https://www.tangramvision.com/blog/c-rust-generics-and-specialization

泛型入门:输入的类型

C++和 Rust 中的泛型都是一种将其他类型作为其定义的一部分的类型。泛型是通过在类型定义中指定占位符的一种方式,然后可以 使用更具体的类型来替换,例如在 C++中可以这定义一个泛型类型:

1template<typename T>
2struct MyArray {
3    T* raw_array;
4    std::size_t size;
5};

对于这个泛型结构而言,MyArray<int>...

题目描述

给你一个 m x n 的矩阵 board ,由若干字符 ‘X’ 和 ‘O’ ,找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

解法一:并查集

这道题通常会用DFS来解,但是也可以用并查集解:首先我们将四条边上的’O’合并成一个连通分量,然后再将圈内的所有相邻的 ‘O’连接起来,最后遍历整个表,将所有为’O’且不与四条边上的’O’所在的连通分量相连的节点设置...

题目描述

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程equations[i]的长度为 4,并采用两种不同的形式之一:"a==b""a!=b"。在这里,ab 是小写字母(不一定不同),表示单字母变量名。 只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false

题解

这一道题,显然是用并查集来解决,思路很简单,由于相等具有传递性,可以认为,一开始所有的字母变量都是独立的 集合,通过等式传递性,可以将这些相等的字母合并到同一个集合,最后看不等式中,是否存在连通的字母,如果存在 则表示等式方程不满足条件。

题目描述

给定一个未排序的整数数nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度O(n)的算法解决此问题。

解法一:并查集

这道题目可以用并查集来解决。初始状态下数组中的每个元素都是一个独立的集合,然后遍历数组,将当前元素相邻的 元素合并到一个集合,最后返回所有集合中元素个数最多的数量。这里要注意去重。

 1#include <vector>
 2#include <unordered_map>
 3
 4class UnionFind {
 5public:
 6    UnionFind(int num) {
 7        for (int...

Ref: https://www.tangramvision.com/blog/c-rust-interior-mutability-moving-and-ownership

C++和 Rust 中的不变性(constness)

Rust 和 C++有两个非常相似的概念,即 Rust 中的 mutability/immutability 和 C++中的 constness/non-constness. 在 Rust 中,一个给定的值要么是可变的(mutable),要么是不可变的(immutable),正如这些限定符名称所代表的含义,可变的值可以被修改,不可变的值不能被修改。 然而与 C++不同的是,Rust 中不可变的值...

在C/C++中,我们经常会像下面的代码那样使用一个指向函数的指针,我们称之为函数指针:

 1// demo.c
 2#include <stdio.h>
 3
 4int func(int a) {
 5    return a + 1;
 6}
 7
 8int main(int argc, char* argv[]) {
 9    int (*f)(int) = func;
10    printf("%p\n", f);
11    return 0;
12}

上面的例子中,我们定义了一个函数func,然后通过函数指针f指向func,接着使用print函数打印指针变量f指向 的地址。代码平淡无奇,...

std::list splice 简介

splice函数通过重新排列链表指针,将一个std::list中的节点转移到另一个std::list中。在元素的转移过程中不会触发元素的拷贝或者移动。因此,调用splice函数之后,元素现有的引用和迭代器都不会失效。

下面是一个将listA中所有节点附加到listB的一个简单代码示例,转移的过程不会导致listA中元素的引用和迭代器失效:

 1// Note: c++17 required below. (For CTAD(Class template argument deducation))
 2std::list listA{1, 2, 3};
 3std::list listB{4,...

关于 shared_ptr

shared_ptr是一种共享所有权的智能指针,它允许我们安全地访问和管理对象的生命周期。shared_ptr的多个实例通过共享控制块结构来控制对象的生命周期。 控制块维护了引用计数(reference count),弱引用计数(weak count)和其他必要的信息,通过这些信息,控制块能够确定一个对象在内存中是否可以被安全销毁。

当使用原始指针构造或者初始化一个shared_ptr时,将会创建一个新的控制块。为了确保一个对象仅由一个共享的控制块管理,必须通过复制已存在的shared_ptr对象来创建一个新的shared_ptr实例,例如:

1void good()
2{
3  auto p{new...