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 = 0
,nums[i] = 2
。- 查找
target - nums[i] = 9 - 2 = 7
在哈希表中不存在。 - 将
2
和索引0
存入哈希表:hmap[2] = 0
。
第二次迭代:
i = 1
,nums[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
等于revertedNumber
或x
等于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;
}