review:
704. Binary Search
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[mid] == target) return mid;
else if(nums[mid] > target){
right = mid-1;
}else{
left = mid+1;
}
}
return -1;
}
};
二分搜索:
判断条件是left 和 right
这里就要注意区间开闭的问题
27. Remove Element
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0, fast = 0;
while(fast < nums.size()){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
189. Rotate Array
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k%n);
reverse(nums.begin()+k%n, nums.end());
}
};
121. Best Time to Buy and Sell Stock
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2));
//0表示未持有, 1表示持有
dp[0][0] = 0;
dp[0][1] = -prices[0];
int maxVal = 0;
for(int i=1; i<prices.size(); i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], -prices[i]);
}
return dp[prices.size()-1][0];
}
};
New:
380. Insert Delete GetRandom O(1)
class RandomizedSet {
private:
vector<int> nums;
unordered_map<int, int> valToIndex;//nums中每个元素在nums的下表
public:
RandomizedSet() {
}
bool insert(int val) {
if(valToIndex.find(val) != valToIndex.end()){
return false;
}
valToIndex[val] = nums.size();
nums.push_back(val);
return true;
}
bool remove(int val) {
if(valToIndex.find(val) == valToIndex.end()) return false;
int lastNum = nums.back();
int index = valToIndex[val];
valToIndex[lastNum] = index;
swap(nums[index], nums.back());
nums.pop_back();
valToIndex.erase(val);
return true;
}
int getRandom() {
if(nums.size() == 0) return false;
return nums[rand() % nums.size()];
}
};
因为需要运行时间时O(1),所以要加上map
删除的时候要把需要删除的变到最后,再直接pop掉
rand用法:
1.rand()
2. nums[rand() % nums.size()];文章来源:https://www.toymoban.com/news/detail-699909.html
3. left+rand() % (right-left)文章来源地址https://www.toymoban.com/news/detail-699909.html
238. Product of Array Except Self
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> presuf(n, nums[0]);
for(int i=1; i<nums.size(); i++){
presuf[i] = presuf[i-1] * nums[i];
}
vector<int> postsuf(n, nums[n-1]);
for(int i=n-2; i>=0; i--){
postsuf[i] = postsuf[i+1] * nums[i];
}
vector<int> res(n);
res[0] = postsuf[1];
res[n-1] = presuf[n-2];
for(int i=1; i<n-1; i++){
res[i] = presuf[i-1] * postsuf[i+1];
}
return res;
}
};
134. Gas Station
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int sum = 0, minSum = 0;
int start = 0;
for(int i=0; i<gas.size(); i++){
sum += gas[i] - cost[i];
if(sum < minSum){
minSum = sum;
start = i+1;
}
}
if(sum < 0) return -1;
return start == gas.size() ? 0 : start;
}
};
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int sum = 0;
int start = 0;
for(int i=0; i<gas.size(); i++){
sum += gas[i] - cost[i];
}
if(sum < 0) return -1;
int tank = 0;
for(int i=0; i<gas.size(); i++){
tank += gas[i] - cost[i];
if(tank < 0){
start = i+1;
tank = 0;
}
}
return start == gas.size() ? 0 : start;
}
};
13. Roman to Integer
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> map;
map['I'] = 1;
map['V'] = 5;
map['X'] = 10;
map['L'] = 50;
map['C'] = 100;
map['D'] = 500;
map['M'] = 1000;
int sum = 0;
for(int i = 0; i<s.size(); i++){
int x = map[s[i+1]];
if(map[s[i]] < map[s[i+1]]){
sum -= map[s[i]];
}else{
sum += map[s[i]];
}
}
return sum;
}
};
到了这里,关于Leetcode array 704 27 189 121 380 238 134 13的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!