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...// 第一个和最后一个是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
用于遍历整个数组。由于数组已排序,所以重复的元素必然是相邻的。通过逐个比较和移动指针,可以在不使用额外空间的情况下完成去重。
思路
- 设置指针:初始化
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;}
};