Leetcode刷题笔记14

news/2024/11/16 11:59:36/

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;}
};


http://www.ppmy.cn/news/1547441.html

相关文章

JWTUtil工具类

写一个Jwt工具类 导入如下pom.xml依赖 <!--fastjson依赖--><dependency><groupId>com.alibaba</groupId><artifactId>fastjson</artifactId><version>1.2.33</version></dependency><!--jwt依赖--><dependenc…

Electron 项目实现下载文件监听

Electron 项目实现下载文件监听 随着现代应用程序功能的不断扩展&#xff0c;用户对下载文件的需求也越来越高。特别是在 Electron 应用程序中&#xff0c;提供一个高效、可靠的下载管理功能是提升用户体验的 关键之一。本文将详细介绍如何在 Electron 项目中实现下载文件的监…

确保以管理员权限运行 Visual Studio 开发者命令提示符

文章目录 解决方法&#xff1a;1. 以管理员身份运行命令提示符2. 改变目录权限3. 改变项目目录位置4. 检查文件系统权限 总结&#xff1a; ********************************************************************** ** Visual Studio 2022 Developer Command Prompt v17.12.0 …

网关在能源物联网中扮演了什么角色?

随着通信、物联网、云平台等技术的飞速发展&#xff0c;越来越多能源用户希望借助先进的管理手段&#xff0c;对能源进行分布式监测、集中管理&#xff0c;构建能源物联网。准确的分布式监测和集中管理有助于制定更科学合理的节能减排计划。企业或能源使用单位可以依据能源物联…

论文 | The Capacity for Moral Self-Correction in LargeLanguage Models

概述 论文探讨了大规模语言模型是否具备“道德自我校正”的能力&#xff0c;即在收到相应指令时避免产生有害或偏见输出的能力。研究发现&#xff0c;当模型参数达到一定规模&#xff08;至少22B参数&#xff09;并经过人类反馈强化学习&#xff08;RLHF&#xff09;训练后&…

4.1 Android NDK 简介

原生开发套件&#xff08;NDK&#xff09;是一套工具&#xff0c;使您能够在 Android 应用中使用 C/C 代码&#xff0c;并提供众多平台库&#xff0c;您可以使用这些平台库管理原生 activity 和访问实体设备组件&#xff0c;例如传感器和触控输入。如果您需要实现以下一个或多个…

Essential Cell Biology--Fifth Edition--Chapter one (6)

1.1.4.4 Internal Membranes Create Intracellular Compartments with Different Functions [细胞膜形成具有不同功能的细胞内隔室] 细胞核、线粒体和叶绿体并不是真核细胞中唯一的膜包围细胞器。细胞质中含有大量的[ a profusion of]其他细胞器&#xff0c;这些细胞器被单层膜…

机器学习【激活函数】

笔记内容侵权联系删 激活函数的概念神经网络中的每个神经元节点接受上一层神经元的输出值作为本神经元的输入值&#xff0c;并将输入值传递给下一层&#xff0c;输入层神经元节点会将输入属性值直接传递给下一层(隐层或输出层)。在多层神经网络中&#xff0c;上层节点的输入在加…