Leetcode刷题笔记14
136. 只出现一次的数字
136. 只出现一次的数字 - 力扣（LeetCode）
核心思想：按位异或运算
利用按位异或运算的性质来解决这个问题：
异或运算的性质：
a ^ a = 0：相同的数异或结果为0。
a ^ 0 = a：任意数与0异或结果为该数本身。
交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b。
由于数组中除了一个数只出现一次，其他数都出现两次，根据异或运算的性质，这些成对出现的数会互相抵消变成0，
最后剩下的就是那个只出现一次的数。
示例运行
假设 nums = [2, 2, 1]，我们来看看代码如何运行：
初始 value = 0。
遍历数组：
value ^= 2：value = 0 ^ 2 = 2
value ^= 2：value = 2 ^ 2 = 0
value ^= 1：value = 0 ^ 1 = 1
最终 value 的值为1，返回1。
这个结果符合预期，证明代码是正确的。
通过异或运算，可以在线性时间内（O(n)）找到唯一只出现一次的数字，
并且只使用常量级别的额外空间（O(1)）。这个方法既高效又简洁。
代码：C++
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(auto i: nums) ret^=i;
return ret;
}
};118. 杨辉三角
118. 杨辉三角 - 力扣（LeetCode）
杨辉三角的特点是每个数是它上方两个数之和。
核心思想
杨辉三角的特点是，每个位置的值等于其上方相邻两个元素之和。使用这种递归关系，从上往下逐行构造，每一行的首尾元素是固定的 1，中间的元素通过前一行的值计算得到。
思路
- 建立结构：构造一个二维数组，将其大小设置为
n行，逐行填充杨辉三角的值。 - 固定边界条件：每一行的首尾元素都是
1，可以直接赋值。 - 动态填充中间元素：对于每行的中间元素，利用递推公式
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]，计算当前行的每个位置值。 - 输出结果：生成所需行数的杨辉三角，输出作为二维数组。
代码：C++
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for(size_t i=0;i<vv.size();++i)
{
vv[i].resize(i+1, 0); // 第0行开一个0，第1行开2个0...
// 第一个和最后一个是1
vv[i].front() = 1;
vv[i].back() = 1;
}
for(size_t i=0;i<vv.size();++i)
{
for(size_t j=0; j<vv[i].size(); ++j)
{
if(vv[i][j]==0)
{
vv[i][j]=vv[i-1][j] + vv[i-1][j-1];
}
}
}
return vv;
}
};
//class Solution {
//public:
// vector<vector<int>> generate(int numRows) {
// vector<vector<int>> vv; // 声明一个二维向量vv，存储杨辉三角的每一行
// vv.resize(numRows); // 调整vv的大小为numRows行
// for (size_t i = 0; i < vv.size(); ++i) { // 遍历每一行
// vv[i].resize(i + 1, 0); // 每一行有i+1个元素，初始化为0
// vv[i].front() = 1; // 每一行的第一个元素为1
// vv[i].back() = 1; // 每一行的最后一个元素为1
// }
// for (size_t i = 0; i < vv.size(); ++i) { // 再次遍历每一行
// for (size_t j = 0; j < vv[i].size(); ++j) { // 遍历每一行的每个元素
// if (vv[i][j] == 0) { // 如果当前元素是0，表示它需要计算
// vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j]; // 当前元素是它左上和右上的元素之和
// }
// }
// }
// return vv; // 返回生成的杨辉三角
// }
//};26. 删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣（LeetCode）
核心思想
这道题的核心思想是利用双指针在排序数组中去除重复项。一个指针 dst 用于记录去重后的数组位置，另一个指针 src 用于遍历整个数组。由于数组已排序，所以重复的元素必然是相邻的。通过逐个比较和移动指针，可以在不使用额外空间的情况下完成去重。
思路
- 设置指针：初始化
src和dst两个指针，均指向数组的起始位置。 - 遍历数组：使用
src指针遍历整个数组：- 如果
src和dst指向的元素相同，则说明遇到重复元素，仅移动src指针。 - 如果
src和dst指向的元素不同，则说明遇到新的元素，将src的值赋给dst + 1，然后同时移动src和dst指针。
- 如果
- 调整数组长度：在遍历结束后，将数组的长度调整为
dst + 1。 - 返回长度：返回去重后的数组长度。
代码：C++
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int src=0;
int dst=0;
while(src < nums.size())
{
if(nums[src] == nums[dst]) // 如果 src 和 dst 指向的元素相同，说明是重复元素，移动 src 指针
{
++src;
}
else // 如果 src 和 dst 指向的元素不同，将 src 的值复制到 dst + 1 位置，同时移动 src 和 dst 指针
{
nums[++dst] = nums[src++];
}
}
nums.resize(dst+1);
return dst + 1;
}
};17. 电话号码的字母组合
17. 电话号码的字母组合 - 力扣（LeetCode）
核心思想
利用回溯（Backtracking）方法，根据数字字符串中的每个数字，将其映射到对应的字母集合，通过递归逐步生成所有可能的组合。这种递归方法允许我们逐一生成不同长度的组合，当达到字符串的末尾时，将组合加入结果列表。
思路
- 建立映射：初始化一个数组
numToStr，存储每个数字对应的字母字符串。例如，2对应 "abc"，3对应 "def"，依此类推。 - 递归生成组合：定义一个递归函数
Combine，用于将当前数字对应的字母添加到组合字符串中：- 如果已经处理到数字字符串的末尾，将当前组合字符串加入结果列表。
- 否则，获取当前数字对应的字母集合，对每个字母，递归调用
Combine生成下一个字符的组合。
- 边界处理：在递归开始前，判断输入是否为空字符串，如果为空则直接返回空列表。
- 返回结果：递归结束后，返回存储所有组合的列表。
代码：C++
class Solution {
char* numToStr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
// string numToStr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
void Combine(string digits, int di, vector<string>& retV, string combineStr)
{
if(di == digits.size())
{
retV.push_back(combineStr);
return;
}
// 递归
// 取数字字符映射的字符串
int num = digits[di] - '0';
string str = numToStr[num];
for(auto ch : str)
{
// di+1就会往下一层走
Combine(digits, di+1, retV, combineStr+ch);
}
}
vector<string> letterCombinations(string digits) {
vector<string> v;
if(digits.empty())
{
return v;
}
string str;
Combine(digits, 0, v, str);
return v;
}
};