Leetcode array 704 27 189 121 380 238 134 13

这篇具有很好参考价值的文章主要介绍了Leetcode array 704 27 189 121 380 238 134 13。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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()];

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Day1 LeetCode 704.二分查找 27.移除元素

    704.二分查找 题目链接: 力扣 文章讲解: 代码随想录 视频讲解: 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili 看完随想录之后的想法 两种情况1.左闭右闭  [ ]  2.左闭右开 [ )  当定义时为左闭右闭时,while中if的条件可以

    2024年02月15日
    浏览(41)
  • 代码随想录Day1 | 数组01- leetcode 704、27

    题目链接:二分查找 关键问题:         - 边界(left、right)、当前查找值(middle)                 - target大于当前查找值 -- 当前查找区域的右边,更改区间left                 - target小于当前查找值 -- 当前查找区域的左边,更改区间right                 - middle的计

    2024年02月16日
    浏览(48)
  • LeetCode 189.轮转数组

    题目链接👉LeetCode 189.轮转数组👈 给定一个整数数组 nums ,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 假如我们要把数组 [1,2,3,4,5,6,7] ,向右旋转 3 次 👇图解👇 第1步:定义一个临时变量 tmp ,用来存放数组最后的元素 7 第2步:把数组前 n-1 个值往后挪 第3步:把

    2023年04月17日
    浏览(42)
  • LeetCode189.轮转数组

     这道题我先用最简单的方法做了一遍,就是先把后面的k个数放到一个数组先存起来,然后从数组的后面开始把前面的第k个数放过来,nums[i]=nums[i-k];然后前k个数就直接拿那个存的数组复制过来,然后就是注意如果knums.length,要把模上nums.length;这个还是比较简单的,时间复杂

    2024年02月10日
    浏览(30)
  • 【LeetCode】189. 轮转数组

    题目链接: https://leetcode.cn/problems/rotate-array/ 📕题目要求: 给定一个整数数组  nums ,将数组中的元素向右轮转  k   个位置,其中  k   是非负数。 尽可能想出更多的解决方案,至少有  三种  不同的方法可以解决这个问题。 你可以使用空间复杂度为  O(1)  的  原地  算法

    2023年04月27日
    浏览(34)
  • leetcode189. 轮转数组

    题目: 给定一个整数数组  nums ,将数组中的元素向右轮转  k   个位置,其中  k   是非负数。 示例: 示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2: 输入:nums = [-1,-100

    2024年02月11日
    浏览(38)
  • Leetcode:【189. 轮转数组】

    给定一个整数数组  nums ,将数组中的元素向右轮转  k   个位置,其中  k   是非负数 难度:中等 题目链接:189. 轮转数组 示例 2: 提示: 1 = nums.length = 10^5 -2^31 = nums[i] = 2^31 - 1 0 = k = 10^5 核心思想 : 逆置数组 先逆置全部数组 再把右旋过去的数组逆置一下 最后把剩下部分数

    2024年02月07日
    浏览(30)
  • leetcode238:除自身以外数组的乘积

    在leetcode上刷到了这一题,一开始并没有想到好的解题思路,写篇博客再来梳理一下吧。 题目要求: 不使用除法 在O(n)时间复杂度内 该方法分以下几步: 先遍历数组,求数组所有元素的乘积sum 再遍历一遍数组,使用sum除以该下标对应的元素,将结果放在answer数组中 相较于第

    2024年01月16日
    浏览(47)
  • 【Leetcode】238.除自身以外数组的乘积

    给你一个整数数组 nums ,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法 ,且在 O(n) 时间复杂度内完成此题。 示例1: 示例2: 提示:

    2024年01月22日
    浏览(40)
  • 【LeetCode-中等题】189. 轮转数组

    思路:通过,开辟数组 取模运算寻找新位置------ 位置(i+k)mod n =新位置 思路: 1、先全部翻转 2、在根据k 的值 对k-1 的两边区域进行翻转 3、注意 k如果 数组长度 就会出现下标越界,所以需要开始就k对数组长度取模 k %=n

    2024年02月11日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包