Leetcode刷题笔记9

ops/2024/9/25 15:22:24/

1. 两数之和

1. 两数之和 - 力扣(LeetCode)

解法一:暴力枚举

没什么好说的,直接使用两个for循环,i从第一个元素开始,j从第二个元素开始遍历并寻找

时间复杂度:O(N^2)

空间复杂度:O(1)

代码:C++

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for(int i=0; i<n; i++){for(int j=i+1; j<n; j++){if(nums[i]+nums[j]==target){return {i,j};}}}return {};}};

 解法二:哈希表 - 空间换时间

哈希表是一种用于高效地存储和查找数据的数据结构。它基于哈希函数将键映射到表中的位置,通常称为桶。

例如:

nums = [2, 7, 11, 15]target = 9

第一次迭代

  • i = 0nums[i] = 2
  • 查找 target - nums[i] = 9 - 2 = 7 在哈希表中不存在。
  • 2 和索引 0 存入哈希表:hmap[2] = 0

第二次迭代

  • i = 1nums[i] = 7
  • 查找 target - nums[i] = 9 - 7 = 2 在哈希表中存在,索引为 0
  • 找到目标值,返回索引 [0, 1]

通过使用额外的空间(哈希表),将时间复杂度从暴力解法的 O(n^2) 降低到 O(n)

时间复杂度:O(N)

空间复杂度:O(N)

代码:C++

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hmap; // 定义一个哈希表for (int i = 0; i < nums.size(); ++i) { // 遍历数组中的每一个元素auto it = hmap.find(target - nums[i]); // 在哈希表中查找是否存在使得和为 target 的元素if (it != hmap.end()) { // 如果找到return {it->second, i}; // 返回对应的索引}hmap[nums[i]] = i; // 将当前元素及其索引存入哈希表}return {};}};

9. 回文数

9. 回文数 - 力扣(LeetCode)

判断一个整数是否是回文数的核心思路是:将该整数的一半反转,然后与原整数的另一半进行比较。如果两部分相等,那么这个整数就是回文数。

解法一:暴力解法

  • 将整数转换为字符串。
  • 反转字符串。
  • 检查原字符串和反转后的字符串是否相等。
bool isPalindrome(int x) {if (x < 0) return false;std::string str = std::to_string(x);std::string rev_str = std::string(str.rbegin(), str.rend());return str == rev_str;
}

缺点:

  • 空间复杂度高:需要额外的空间来存储字符串和反转后的字符串。
  • 效率较低:字符串操作和反转可能会比较耗时。

优化:因为回文数是前后对应的,所以只需要反转一半的数字就可以知道它是不是回文数

解法二:优化

首先排除里面带0的组合,比如x<0,或者x以0结尾但不等于0

然后反转数字的一半:

  • x 大于 revertedNumber 时,进入循环。
  • 在每次循环中,将 x 的最后一位数字加到 revertedNumber 的末尾。
  • 然后将 x 去掉最后一位数字(通过整除 10)

 最后判断:

  • x 的长度是偶数时,x 应该等于 revertedNumber
  • x 的长度是奇数时,revertedNumber 会多一位,因此我们可以通过 revertedNumber / 10 去掉中间的数字再比较。
  • 最终,如果 x 等于 revertedNumberx 等于 revertedNumber 去掉最后一位的结果,那么 x 是回文数,返回 true;否则返回 false

代码:C++

class Solution {
public:bool isPalindrome(int x) {// 如果 x 小于 0,或者 x 是以 0 结尾但不等于 0,那么 x 不是回文数。// 负数肯定不是回文数,因为它们的倒序数不是负数。// 以 0 结尾的数(但不是 0 本身)也不是回文数,因为倒序会多出一个 0。if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}// 定义变量 revertedNumber 来存储反转后的数字int revertedNumber = 0;// 当 x 大于 revertedNumber 时继续循环while (x > revertedNumber) {//在每次循环中,将 x 的最后一位数字加到 revertedNumber 的末尾。//然后将 x 去掉最后一位数字(通过整除 10)。revertedNumber = revertedNumber * 10 + x % 10;// 去掉 x 的最后一位数字x /= 10;}// 当 x 的长度是偶数时,x 应该等于 revertedNumber。// 当 x 的长度是奇数时,revertedNumber 会多一位,因此我们可以通过 revertedNumber / 10 去掉中间的数字再比较。// 最终,如果 x 等于 revertedNumber 或 x 等于 revertedNumber 去掉最后一位的结果,那么 x 是回文数,返回 true;否则返回 false。return x == revertedNumber || x == revertedNumber / 10;}
};

DP34 【模板】前缀和

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

从a1开始访问的,所以数组大小得是n+1

例子:
arr: [1,4,7,2,5,8,3,6,9]

i:   [1,2,3,4,5,6,7,8,9]

解法一:暴力解法 -> 模拟

时间复杂度:O(N*q) -> 有多少次查询就要遍历数组多少次(q次查询)
超时

解法二:前缀和 -> 快速求出数组中某一个连续区间的和

时间复杂度:O(q) + O(N)

第一步:预处理出来一个前缀和数组(dp)
arr: [1,4,7,2,5,8,3,6,9]

dp:  [1,5,12,14,19,27,30,36,45]

i:   [1,2,3,4,5,6,7,8,9]

dp[i]:表示[1,i]区间内所有元素的和
比如dp[3]表示原始数组1+4+7

dp[i] = dp[i-1] + arr[i]


第二步:使用前缀和数组

想求出l到r之间的和时可以直接减去就行:
[l,r] = dp[r] - dp[l-1]

dp:  [1,5,12,14,19,27,30,36,45]
               l          r

细节问题:为什么下标要从1开始计数?
比如如果想算[0,2],那l就要访问-1,-1这个位置访问不了,所以要处理边界问题

从1开始就可以处理边界情况
比如算[1,2] -> dp[2] - dp[0],可以把dp[0] = 0

代码:C++

#include <iostream>
#include <vector>
using namespace std;int main() 
{// 1. 读入数据int n, q;cin >> n >> q;vector<int> arr(n+1);for(int i = 1; i <= n; i++) cin >> arr[i];// 2. 预处理出来一个前缀和数组vector<long long> dp(n+1); // 防止溢出for(int i = 1; i <= n; i++) dp[i] = dp[i-1] + arr[i];// 3.使用前缀和数组int l = 0, r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] << endl;}return 0;
}


http://www.ppmy.cn/ops/48882.html

相关文章

Vue按键修饰符

1.常用按键别名 .enter.tab.delete (捕获“Delete”和“Backspace”两个按键).esc.space.up.down.left.right 2.使用方法 <!-- 仅在 key 为 Enter 时调用 submit --> <input keyup.enter"submit" /> 其他按键同理&#xff0c;如果想要添加的按键不在…

【设计模式深度剖析】【8】【行为型】【备忘录模式】| 以后悔药为例加深理解

&#x1f448;️上一篇:观察者模式 设计模式-专栏&#x1f448;️ 文章目录 备忘录模式定义英文原话直译如何理解呢&#xff1f; 3个角色1. Memento&#xff08;备忘录&#xff09;2. Originator&#xff08;原发器&#xff09;3. Caretaker&#xff08;负责人&#xff09;类…

mysql和postgreSQL的区别

mysql 1、mysql多表连接查询方式支支持nest loop&#xff0c;不支持hash join和sort merge join。pg支持多种连接查询方式。 2、mysql子查询性能比pg低。 3、mysql的复制是异步的&#xff0c;即无法通过主从架构做到数据零丢失。一些第三方公司也有改造mysql源代码实现同步复制…

Spring-boot-logback-spring.xml文件Appender标签下的属性

在logback-spring.xml文件中&#xff0c;标签是通过set方法设置的值&#xff0c;例如下面的代码&#xff0c;属性hrName的值为TYC&#xff0c;当服务启动的时候&#xff0c;控制台会一直打印TYC三个字母 首先&#xff0c;我们自定义一个Appender&#xff0c;然后里面有一个属性…

wordpress主题开发

科普一&#xff1a;wordpress 是一套用 php 这个语言写的CMS后台管理系统&#xff0c;即我们大家的 wordpress 网站后台是一样的&#xff0c;能体现我们网站外观不同的地方就在于wordpress主题&#xff08;即皮肤&#xff09;&#xff0c;而这个主题的基本构成是 htmlcssjavasc…

小程序中的事件处理

事件处理 一个应用仅仅只有界面展示是不够的&#xff0c;还需要和用户做交互&#xff0c;例如&#xff1a;响应用户的点击、获取用户输入的值等等&#xff0c;在小程序里边&#xff0c;我们就通过编写 JS 脚本文件来处理用户的操作 1. 事件绑定和事件对象 小程序中绑定事件与…

AI数字人的开源解决方案

目前&#xff0c;国内外已经涌现出一些优秀的数字人开源解决方案&#xff0c;这些解决方案为开发者提供了构建数字人应用的工具和基础设施。以下是一些比较知名的数字人开源解决方案。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1…

Web前端网页设计模板:创新设计与高效开发的完美融合

Web前端网页设计模板&#xff1a;创新设计与高效开发的完美融合 在当今数字化时代&#xff0c;Web前端网页设计模板已经成为构建美观且功能强大的网页应用的重要工具。它不仅能够简化开发过程&#xff0c;提升工作效率&#xff0c;还能够确保网页在各种设备上都能够呈现出令人…