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，中间的元素通过前一行的值计算得到。

思路

1. 建立结构：构造一个二维数组，将其大小设置为 n 行，逐行填充杨辉三角的值。
2. 固定边界条件：每一行的首尾元素都是 1，可以直接赋值。
3. 动态填充中间元素：对于每行的中间元素，利用递推公式 triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]，计算当前行的每个位置值。
4. 输出结果：生成所需行数的杨辉三角，输出作为二维数组。

代码：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...// 第一个和最后一个是1vv[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 用于遍历整个数组。由于数组已排序，所以重复的元素必然是相邻的。通过逐个比较和移动指针，可以在不使用额外空间的情况下完成去重。

思路

1. 设置指针：初始化 src 和 dst 两个指针，均指向数组的起始位置。
2. 遍历数组：使用 src 指针遍历整个数组：
   • 如果 src 和 dst 指向的元素相同，则说明遇到重复元素，仅移动 src 指针。
   • 如果 src 和 dst 指向的元素不同，则说明遇到新的元素，将 src 的值赋给 dst + 1，然后同时移动 src 和 dst 指针。
3. 调整数组长度：在遍历结束后，将数组的长度调整为 dst + 1。
4. 返回长度：返回去重后的数组长度。

代码：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）方法，根据数字字符串中的每个数字，将其映射到对应的字母集合，通过递归逐步生成所有可能的组合。这种递归方法允许我们逐一生成不同长度的组合，当达到字符串的末尾时，将组合加入结果列表。

思路

1. 建立映射：初始化一个数组 numToStr，存储每个数字对应的字母字符串。例如，2 对应 "abc"，3 对应 "def"，依此类推。
2. 递归生成组合：定义一个递归函数 Combine，用于将当前数字对应的字母添加到组合字符串中：
   • 如果已经处理到数字字符串的末尾，将当前组合字符串加入结果列表。
   • 否则，获取当前数字对应的字母集合，对每个字母，递归调用 Combine 生成下一个字符的组合。
3. 边界处理：在递归开始前，判断输入是否为空字符串，如果为空则直接返回空列表。
4. 返回结果：递归结束后，返回存储所有组合的列表。

 

 代码：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;}
};