网站建设收费价目表,建设银行网站官网网址,廊坊网站制作官网,网站申请要多少钱136. 只出现一次的数字
136. 只出现一次的数字 - 力扣#xff08;LeetCode#xff09; 核心思想#xff1a;按位异或运算
利用按位异或运算的性质来解决这个问题#xff1a;
异或运算的性质#xff1a; a ^ a 0#xff1a;相同的数异或结果为0。 a ^ 0 a#xff1a…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 ^ 2value 0 ^ 2 2 value ^ 2value 2 ^ 2 0 value ^ 1value 0 ^ 1 1 最终 value 的值为1返回1。 这个结果符合预期证明代码是正确的。
通过异或运算可以在线性时间内O(n)找到唯一只出现一次的数字 并且只使用常量级别的额外空间O(1)。这个方法既高效又简洁。
代码C
class Solution {
public:int singleNumber(vectorint nums) {int ret0;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:vectorvectorint generate(int numRows) {vectorvectorint vv;vv.resize(numRows);for(size_t i0;ivv.size();i){vv[i].resize(i1, 0); // 第0行开一个0第1行开2个0...// 第一个和最后一个是1vv[i].front() 1;vv[i].back() 1;}for(size_t i0;ivv.size();i){for(size_t j0; jvv[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:
// vectorvectorint generate(int numRows) {
// vectorvectorint vv; // 声明一个二维向量vv存储杨辉三角的每一行
// vv.resize(numRows); // 调整vv的大小为numRows行
// for (size_t i 0; i vv.size(); i) { // 遍历每一行
// vv[i].resize(i 1, 0); // 每一行有i1个元素初始化为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(vectorint nums) {int src0;int dst0;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(dst1);return dst 1;}
};
17. 电话号码的字母组合
17. 电话号码的字母组合 - 力扣LeetCode 核心思想
利用回溯Backtracking方法根据数字字符串中的每个数字将其映射到对应的字母集合通过递归逐步生成所有可能的组合。这种递归方法允许我们逐一生成不同长度的组合当达到字符串的末尾时将组合加入结果列表。
思路
建立映射初始化一个数组 numToStr存储每个数字对应的字母字符串。例如2 对应 abc3 对应 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, vectorstring 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){// di1就会往下一层走Combine(digits, di1, retV, combineStrch);}}vectorstring letterCombinations(string digits) {vectorstring v;if(digits.empty()){return v;}string str;Combine(digits, 0, v, str);return v;}
};
