【优选算法题练习】day7-Toy模板网

这篇具有很好参考价值的文章主要介绍了【优选算法题练习】day7。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、35. 搜索插入位置

1.题目简介

35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
【优选算法题练习】day7,优选算法题练习,算法,leetcode

2.解题思路

3.代码

class Solution {
public:
    int searchInsert(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)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return left;
    }
};

4.运行结果

【优选算法题练习】day7,优选算法题练习,算法,leetcode

二、69. x 的平方根

1.题目简介

69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
【优选算法题练习】day7,优选算法题练习,算法,leetcode

2.解题思路

3.代码

class Solution {
public:
    int mySqrt(int x) {
        if(x < 1) return 0;
        int left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x)
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;
    }
};

4.运行结果

【优选算法题练习】day7,优选算法题练习,算法,leetcode

三、852. 山脉数组的峰顶索引

1.题目简介

852. 山脉数组的峰顶索引
符合下列属性的数组 arr 称为山脉数组：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
【优选算法题练习】day7,优选算法题练习,算法,leetcode

2.解题思路

3.代码

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1])//如果mid所处位置是上升的，则我们要在mid + 1~right区间寻找
            {
                left = mid;
            }
            else//如果mid所处位置是下降的，则我们要在left~mid-1区间寻找
            {
                right = mid - 1;
            }
        }
        return left;
    }
};

4.运行结果

【优选算法题练习】day7,优选算法题练习,算法,leetcode

总结

今天是算法练习的第7天。
只要功夫深，铁杵磨成针，继续加油！
题目来源：力扣（LeetCode），著作权归领扣网络所有。
如果本篇文章对你有所启发的话，希望可以多多支持作者，谢谢大家！文章来源地址https://www.toymoban.com/news/detail-577324.html

到了这里，关于【优选算法题练习】day7的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！