很久不刷题了,再次刷题手太生了,痛定思痛,还是继续刷吧,立帖为证,天天坚持
217. 存在重复元素
给定一个整数数组,判断是否存在重复元素。
如果存在一值在数组中出现至少两次,函数返回 true
。如果数组中每个元素都不相同,则返回 false
。
解题思路;
1.排序,则若有重复会出现在相邻位置,扫描数组,比较相邻位置元素是否相等
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin() , nums.end());
int n = nums.size();
for(int i = 0; i < n -1; i++){
if(nums[i] == nums[i+1])return true;
}
return false;
}
};
2.哈希,建立哈希表,若该元素未出现则插入,若出现过则返回true
- set自带去重
- 可以用find(X)找到X的位置
- 插入用insert
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> num1;
int n = nums.size();
for(int i = 0; i < n; i++){
if(num1.find(nums[i]) != num1.end()){
return true;
}
else
num1.insert(nums[i]);
}
return false;
}
};
53. 最大子序和 - 力扣(LeetCode) (leetcode-cn.com)
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
解题思路:
1.动态规划
扫描数组,每次求当前位置的最大和,以dp[i]表示以nums[i]结尾的最大子序列和,也就是dp[i] = max(dp[i] + dp[i-1], dp[i]),dp[0] = nums[0]
- vector<int> dp(n)定义长度为n的数组
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if(n < 2)return nums[0];
vector<int> dp(n);
dp[0] = nums[0];
int result = dp[0];
for(int i = 1; i < n; i++){
dp[i] = max(nums[i] + dp[i-1], nums[i]);
result = max(result, dp[i]);
}return result;
}
};
2.贪心
从左向右迭代,一个一个加计算sum和,如果sum和小于0,那么重新开始加,因为若sum<0,那么加sum无意义,重新计算sum
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0;
int n = nums.size();
if (n < 2)return nums[0];
int result = INT_MIN;
for(int i = 0; i < n; i++){
sum += nums[i];
result = max(sum, result);
if(sum < 0)sum = 0;
}return result;
}
};