当前位置：首页 > news >正文

leetcode-vector

news 来源：原创 2024/9/19 9:47:50

这些题的一些讲解我放在b站：普通Youngman

杨辉三角

118. 杨辉三角 - 力扣（LeetCode）https://leetcode.cn/problems/pascals-triangle/

class Solution {
public:vector<vector<int>> generate(int numRows) {// 先创建一个二维向量来存储每一行的数据vector<vector<int>> arr(numRows);// 设置每一行的大小，并将所有元素初始化为 1for (int i = 0; i < numRows; i++) {arr[i].resize(i + 1, 1); // resize 可以用来改变向量的大小，并且可以同时对新添加的元素进行初始化}// 对数据进行计算，形成杨辉三角for (int i = 2; i < numRows; i++) {for (int j = 1; j < i; j++) {// 计算每个非边缘元素的值，即为上一行对应位置两个元素之和arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];}}return arr; // 返回生成的杨辉三角}
};

定义类和方法：

定义了一个名为 Solution 的类，并在其中声明了一个公共成员函数 generate。

初始化二维向量：

创建一个名为 arr 的二维向量，其初始大小等于 numRows。这表示整个杨辉三角将有 numRows 行。

设置每一行的大小并初始化：

使用循环从第 0 行到第 numRows - 1 行，将每一行的大小设置为该行索引加 1，并且所有元素初始化为 1。
比如第一行有一个元素，第二行有两个元素，以此类推。

计算内部元素：

再次使用循环，从第 2 行开始（因为前两行都是 1），遍历每行的中间元素（除了首尾）。
每个中间元素的值等于上一行对应位置的两个元素之和。

返回结果：

最后返回这个包含杨辉三角的二维向量。

电话号码组合

17. 电话号码的字母组合 - 力扣（LeetCode）https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

class Solution {//哈希表string map[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//存储字符的组合string path;//把所有组合存储起来vector<string> ret;
public:vector<string> letterCombinations(string digits) {//digits--输入的字符集if(digits.empty()) return ret;//组合dbf(digits,0);return ret;}void  dbf(const string& digits,int pos){//pos -- 字符集的下标if(pos == digits.size()){//将组合数据存入ret中，返回进行下一次组合ret.push_back(path);return;}for(auto ch : map[digits[pos] - '0']){//[digits[pos] - '0' ->对应的下标//第一次递归path.push_back(ch);//递归到下一个字符集(pos+1)dbf(digits,pos + 1);//清除回溯的数据，进行下一次循环path.pop_back();}        }
};

定义哈希表：
1string map[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
这里定义了一个数组 map，它存储了每个数字对应的字母。例如，数字 2 映射到 "abc"，数字 3 映射到 "def" 等等。
存储字符组合：
1string path;
path 是一个字符串，用于存储当前的字母组合。
存储所有组合：
1vector<string> ret;
ret 是一个字符串向量，用于存储所有可能的字母组合。
公开接口：
1public:
2    vector<string> letterCombinations(string digits);
letterCombinations 函数接受一个字符串 digits，返回所有可能的字母组合。
主处理函数：
1vector<string> letterCombinations(string digits) {
2    if(digits.empty()) return ret;
3    dbf(digits, 0);
4    return ret;
5}
如果 digits 为空，则直接返回空结果；否则，调用辅助函数 dbf 开始深度优先搜索（DFS）。
辅助函数：
1void dbf(const string& digits, int pos) {
2    if(pos == digits.size()) {
3        ret.push_back(path);
4        return;
5    }
6    for(auto ch : map[digits[pos] - '0']) {
7        path.push_back(ch);
8        dbf(digits, pos + 1);
9        path.pop_back();
10    }
11}
这个函数使用递归来生成所有可能的组合。当 pos 达到 digits 的长度时，将当前的 path 添加到结果向量 ret 中。对于 digits 中的每个数字，它会遍历该数字映射的所有字母，并递归地对下一个数字进行同样的操作。递归结束后，会通过 path.pop_back() 清除最后一个字符，以便进行下一轮循环。
最终，letterCombinations 函数返回所有可能的字母组合。

删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.empty())return 0;int fast = 1, slow = 1, n = nums.size();while (fast != n) {if (nums[fast - 1] != nums[fast]) {nums[slow] = nums[fast];++slow;}++fast;}return slow;}
};

函数签名：

函数 removeDuplicates 接受一个整数向量 nums 的引用，并返回一个整数，代表去重后数组的新长度。

空数组检查：

如果输入的数组 nums 是空的，则直接返回 0。

变量初始化：

初始化两个指针 fast 和 slow，分别用于快速遍历数组和记录新数组的当前位置。
n 存储原始数组的长度。

双指针遍历：

while 循环中的条件判断 fast != n 确保 fast 指针没有超出数组边界。
在每次迭代中，如果 fast 指针所指向的元素与前一个元素不同，则将该元素复制到 slow 指针所指向的位置，并将 slow 指针向前移动一位。
无论元素是否相同，fast 指针都会向前移动一位。

返回值：

最终，slow 指针所在的位置即为去重后数组的新长度。

只出现一次的数字

136. 只出现一次的数字 - 力扣（LeetCode）https://leetcode.cn/problems/single-number/

class Solution {
public:int singleNumber(vector<int>& nums) {int key = 0;//利用异或的方式找哪一个数，因为相同的异或会变成0，一直异或就会找到单生狗for(auto ch : nums){key ^= ch;}return key;}
};

函数签名：

函数 singleNumber 接受一个整数向量 nums 的引用，并返回一个整数，代表数组中只出现一次的数字。

变量初始化：

初始化一个整数变量 key 并将其赋值为 0。这个变量将用于存储异或的结果。

异或遍历：

使用范围 for 循环遍历整个数组 nums。
对于数组中的每一个元素 ch，执行 key ^= ch。这是异或运算，它的特性是任何数与 0 异或都等于它本身，而任何数与自己异或都等于 0。因此，所有成对出现的数字经过异或运算后都会相互抵消，最后 key 的值就是那个只出现一次的数字。

返回值：

最终返回 key，即只出现一次的数字。

只出现一次的数字||

137. 只出现一次的数字 II - 力扣（LeetCode）https://leetcode.cn/problems/single-number-ii/description/

class Solution {
public:int singleNumber(vector<int>& nums) {int ans = 0;//0000//int类型32个比特位for(int i = 0;i < 32 ; i++ ){int count = 0;//存储每一位的个数(每一轮初始化为0)for(auto ch : nums){count += (ch >> i) & 1;}if(count % 3)ans |= (1 << i);}return ans;}
};

函数签名：

函数 singleNumber 接受一个整数向量 nums 的引用，并返回一个整数，代表数组中只出现一次的数字。

变量初始化：

初始化一个整数变量 ans 并将其赋值为 0。这个变量将用于存储最终结果。

比特位遍历：

使用外层 for 循环遍历 int 类型的 32 个比特位。
对于每一个比特位，初始化一个计数器 count 为 0。

元素遍历：

使用内层 for 循环遍历数组 nums。
对于数组中的每一个元素 ch，使用 (ch >> i) & 1 来获取当前比特位上 1 的个数，并累加到 count 上。

确定比特位：

如果 count 不能被 3 整除，说明该比特位上的 1 属于只出现一次的数字。
使用 ans |= (1 << i) 来设置 ans 的第 i 位为 1。

返回值：

最终返回 ans，即只出现一次的数字。

只出现一次的数字|||

260. 只出现一次的数字 III - 力扣（LeetCode）https://leetcode.cn/problems/single-number-iii/submissions/553137996/

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {if(nums.size() == 0){return nums;}int Xor = 0;for(auto num : nums){Xor ^= num;//得出两个不同数异或的结果}//将异或结构分离//找第一个有效位，来进行分类(当我们找到这个数的第一个有效位，就可以找到他们的不同，然后就可以把nums的数字按照该位置的有效位是否为（0/1）进项分成两类)int val = (Xor == INT_MIN ? Xor : Xor & (-Xor));//INT_MIN取反+1还是INT_MINvector<int> ret(2,0);//初始一个vector//通过这个有效位分别找开始分别找单身狗for(auto num : nums){if(num & val){//如果该数的该位置的有效位是1的开始异或ret[0] ^= num;}else{//如果该数的该位置的有效位是0的开始异或ret[1] ^= num;}}return ret;}
};

函数签名：

函数 singleNumber 接受一个整数向量 nums 的引用，并返回一个包含两个整数的向量，这两个整数只在数组中各出现一次。

空数组检查：

如果输入的数组 nums 是空的，则直接返回空数组。

初始化变量：

初始化一个整数变量 Xor 并将其赋值为 0。这个变量将用于存储异或的结果。

计算异或结果：

使用范围 for 循环遍历整个数组 nums。
对于数组中的每一个元素 num，执行 Xor ^= num。这是异或运算，它的特性是任何数与 0 异或都等于它本身，而任何数与自己异或都等于 0。因此，所有成对出现的数字经过异或运算后都会相互抵消，最后 Xor 的值是两个只出现一次的数字的异或结果。

找到第一个不为 0 的比特位：

使用 val = (Xor == INT_MIN ? Xor : Xor & (-Xor)) 来找到 Xor 结果中第一个不为 0 的比特位。
如果 Xor 等于 INT_MIN（即 -2147483648），则直接使用 Xor 作为 val。
否则，使用 Xor 和其取反后的按位与运算来找到第一个不为 0 的比特位。

分组并计算异或结果：

初始化一个包含两个元素的向量 ret，每个元素初始值为 0。
再次遍历数组 nums，根据 val 中的比特位将数组分为两组，并分别计算这两组的异或结果。

返回值：

最终返回 ret，即包含两个只出现一次的数字的向量。

数组中次数超过一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

#include <algorithm> // 包含算法头文件，用于 sort 函数class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {// 判空if (numbers.empty()) {return 0;}// 排序sort(numbers.begin(), numbers.end()); // 使用 std::sort 函数对数组进行排序// 中间值int mid = numbers[numbers.size() / 2]; // 取中间位置的值作为候选值// 计数int count = 0;// 统计中间值出现的次数for (auto it : numbers) {if (it == mid) {++count;}}// 比较if (count > numbers.size() / 2) {return mid;} else {return 0;}}
};

包含头文件：

包含 <algorithm> 头文件，以便使用 std::sort 函数对数组进行排序。

函数签名：

函数 MoreThanHalfNum_Solution 接受一个整数向量 numbers 的引用，并返回一个整数，代表数组中超过一半的数字。

空数组检查：

如果输入的数组 numbers 是空的，则直接返回 0。

排序：

使用 std::sort 函数对数组 numbers 进行排序。

选择中间值：

选取数组中间位置的值作为候选值 mid。

计数：

使用范围 for 循环遍历整个数组 numbers。
对于数组中的每一个元素 it，如果它等于候选值 mid，则将计数器 count 加一。

比较：

如果 count 大于数组长度的一半，则返回候选值 mid。
否则，返回 0。