刷题
【leetcode】一次解决三道《只出现一次的数字》
👧只出现一次的数字
给你一个非空整数数组nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 :
输入:nums = [2,2,1]
输出:1
示例 2 :
输入:nums = [4,1,2,1,2]
输出:4
示例 3 :
输入:nums = [1]
输出:1
链接:https://leetcode.cn/problems/single-number/description/
思路:要解决这个问题,我们可以使用异或运算。异或运算具有以下特性:
对于任何整数 a,a ^ a = 0
对于任何整数 a,a ^ 0 = a
异或运算满足交换律和结合律,即 a ^ b ^ a = b ^ a ^ a = b ^ (a ^ a) = b ^ 0 = b
根据题目要求,数组中只有一个元素出现一次,其余元素都出现两次。我们可以将数组中的所有元素进行异或运算,得到的结果就是剩下的那个只出现一次的元素。
12345678910class Solution { ...
数据结构与算法
【数据结构】二叉搜索树
♈概念
二叉搜索树(Binary Search Tree,BST)是一种二叉树数据结构,它具备以下的几种特性:
有序性: 对于树中的任意节点,左子树中的所有节点值都小于等于该节点的值,而右子树中的所有节点值都大于等于该节点的值。这也就意味着可以高效地进行搜索、插入和删除操作。相比于华而不实的二分查找,二叉搜索树更适用于实际一些,至少我是这么认为的。
左右子树也是BST: 二叉搜索树的左子树和右子树也都是二叉搜索树。
中序遍历有序: 对BST进行中序遍历,将会得到一个有序的节点值序列。
12345678 8 / \ 3 10 / \ \1 6 14 / \ / 4 7 13
这是一个二叉搜索树。对于节点上的数字来说,左子树的所有节点值都小于等于该节点,而右子树的所有节点值都大于等于该节点。
因为二叉搜索树具备有序性,可以高效地进行搜索操作。从根节点开始,比较目标值与当前节点的值:
若目标值等于当前节点的值,直接找到了目标节点;
若目标值小于当前节点的值,则在左子树中继续搜索;
若目标值大于当前节点的值,则在右子树中继续搜索 ...
c/c++
【c++】关于继承和多态的一些理解
学到了cpp的继承和多态这块,感觉知识点还是很细碎繁杂的,所以就写了一篇博客先记录在继承这一块遇到的一些容易搞错的问题。
🐓三种继承
cpp的三种继承:public(公有继承)、protected(保护继承)和private(私有继承)。
🐇Public继承
公有继承是最常见的继承方式,基类的公有成员在派生类中仍然是公有的,保护成员在派生类中变为保护的,私有成员在派生类中是不可访问的。
使用public关键字来表示公有继承。
123456789101112131415161718192021222324252627282930313233#include <iostream>// 基类class Base {public: int publicVar; void publicFunc() { std::cout << "Base::publicFunc()" << std::endl; }protected: int protectedVar;priv ...
数据结构与算法
【数据结构】优先级队列的简单模拟
🐶概念
在 C++ 中,std::priority_queue 是一个优先级队列的实现,它提供了按照优先级进行元素存储和访问的功能。与 Python 中的 PriorityQueue 类似,C++ 的 std::priority_queue 使用堆数据结构来实现。
创建一个优先级队列:
123#include <queue>std::priority_queue<int> pq; // 创建一个存储 int 类型的优先级队列
添加元素到队列:
123pq.push(5); // 添加 5 到队列pq.push(3); // 添加 3 到队列pq.push(8); // 添加 8 到队列
获取并移除最高优先级的元素:
12int topElement = pq.top(); // 获取最高优先级的元素(不移除)pq.pop(); // 移除最高优先级的元素
检查队列是否为空:
1bool isEmpty = pq.empty(); // 检查队列是否为空
返回队列中元素的个数:
1int size = pq.size(); // 返回队列中元素 ...
数据结构与算法
【数据结构】list的简单模拟
👿介绍list
list指的是标准模板库(STL)中的双向链表容器。list是一种动态数组的替代品,它可以在运行时调整大小,并且支持高效的插入和删除操作。
要使用list需要包含头文件。
12345678910111213141516171819202122232425262728293031#include <iostream>#include <list>int main() { // 创建一个空的list std::list<int> myList; // 在list的末尾添加元素 myList.push_back(1); myList.push_back(2); myList.push_back(3); // 在list的开头添加元素 myList.push_front(4); // 使用迭代器遍历list并打印元素 for (std::list<int>::iterator it = myList.begin(); it != myList.end(); + ...
数据结构与算法
【数据结构】vector的简单模拟
😄什么是vector?
在C++中,vector是一个非常有用的容器类,用于存储一组元素,类似于数组。它提供了动态大小的数组功能,使得在运行时可以轻松地添加、删除和访问元素。vector是C++标准模板库(STL)的一部分,因此只需包含头文件<vector>即可使用。
vector主要有以下几种作用:
动态大小: vector可以根据需要动态增长或缩小其大小。这意味着不需要在创建时指定其大小,而是可以在运行时根据需要添加或删除元素。
随机访问: 类似于数组可以使用索引来直接访问vector中的元素。
自动内存管理: vector会自动进行内存管理,这意味着不用担心内存分配和释放的细节。
元素操作: vector提供了许多用于操作元素的函数,例如在尾部添加元素(push_back())、删除尾部元素(pop_back())、插入元素(insert())、删除指定位置元素(erase())等等。
与算法的集成: 由于vector是STL的一部分,它可以与STL的其他容器和算法无缝集成,使得数据处理变得非常方便。
下面是一个使用vector的简单示例:
...
数据结构与算法
【数据结构】string的简单模拟
最近学到了string的相关的库,于是为了加深对函数的理解便打算模拟实现一下常用的string库函数,也顺便补习了一些之前不太理解的语法或概念。
☀️引入
这是一个简单的string类的用法。
12345678910#include <string>#include <iostream>int main() { std::string str = "Hello, world!"; std::cout << "The length of the string is: " << str.size() << std::endl; return 0;}
由上可见,string类是C++标准库中的一个类,它定义在std命名空间中。因此,当使用string类时,需要指定其命名空间为std,以便编译器可以找到正确的定义。如果没有指定命名空间,编译器可能会认为string是一个未定义的标识符,导致编译错误。
std是C++标准库中定义的命名空间,它包含了许多C ...
linux
【linux】初识进程
操作系统
在了解进程前,还得介绍一下操作系统。
概念
操作系统是计算机系统中的一种重要软件,它是计算机硬件和软件之间的桥梁,负责管理计算机系统的各种资源,如CPU、内存、输入输出设备等。操作系统可以被看作是计算机系统的管理者,它控制和协调计算机系统中各个部件的工作,使得应用程序能够正确地运行。
操作系统通常包括以下几个组成部分:
内存管理:负责管理计算机系统的内存资源,包括内存的分配、释放和保护等。
进程管理:负责管理计算机系统中的进程,包括进程的创建、调度、同步和通信等。
文件系统:负责管理计算机系统中的文件和目录,包括文件的读写、创建、删除和保护等。
输入输出管理:负责管理计算机系统中的输入输出设备,包括输入输出的缓存、设备的分配和释放等。
维基百科这样总结操作系统:操作系统(Operating System,缩写:OS)是一组主管并控制计算机操作、运用和运行硬件、软件资源和提供公共服务来组织用户交互的相互关联的系统软件程序,同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系 ...
c/c++
【c】简单的进度条程序
实现一个简单的进度条程序。主要的思路就是利用一个字符数组,不断的改变其内容实现进度条的动画效果。
💚processbar.h
1234567#pragma once#include <stdio.h>#define NUM 102#define TOP 100#define BODY '='#define RIGHT '>'void processbar(int rate);
以上则是进度条的头文件,有如下说明:
TOP是字符数组的容量大小,NUM是TOP+2,为何这样设置在源文件处解释。
BODY与RIGHT是组成进度条的两个字符。
processbar则是主要的函数,用于接收目前的读取或下载进度(int,大小0-100)。
<unistd.h>头文件是POSIX标准定义的头文件,主要用于UNIX/Linux系统中。如果你在Windows系统上使用Visual Studio编译C程序,可以使用Windows API提供的Sleep()函数来实现类似于sleep()函数的功能。Sleep()函数的头文件是& ...
linux
【linux】makefile——高效的构建工具
🏡简介
今天学习linux,第一次遇到了Makefile,写下这篇文章记录一些学到的知识。
Makefile是一种常用的构建工具,用于自动化编译、链接和部署程序。它最初是为Unix系统开发的,但现在已经广泛用于各种操作系统和编程语言中。Makefile的核心思想是基于依赖关系自动化构建,它会根据文件的修改时间和依赖关系来确定哪些文件需要重新编译和链接。
这也正是makefile的主要功能。
一个特别大的项目,一般来说会有很多的源文件,被分门别类的放在不同的目录中,有时候也会在一个目录里存放了多个程序的源代码。这时,如何对这些代码的编译就成了个问题。Makefle就是为这个问题而生的,它定义了一套规则,决定了哪些文件要先编译,哪些文件后编译,哪些文件要重新编译。
不过在了解makefile之前,还得先补习一点关于程序编译的知识点。
🏫linux与gcc/g++
在Linux系统中,gcc/g++是一款非常常用的编译器。它可以将C/C++的源代码编译、汇编、链接,生成可执行文件或库文件。
在编译过程中,一个代码文件需要经过预处理、编译、汇编、连接等步骤才能转化为可执行的程序。
预处 ...