力扣打卡第一天

2023-12-27 13:27:31

153.?寻找旋转排序数组中的最小值

提示

中等

已知一个长度为?n?的数组,预先按照升序排列,经由?1?到?n?次?旋转?后,得到输入数组。例如,原数组?nums = [0,1,2,4,5,6,7]?在变化后可能得到:

  • 若旋转?4?次,则可以得到?[4,5,6,7,0,1,2]
  • 若旋转?7?次,则可以得到?[0,1,2,4,5,6,7]

注意,数组?[a[0], a[1], a[2], ..., a[n-1]]?旋转一次?的结果为数组?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

给你一个元素值?互不相同?的数组?nums?,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的?最小元素?。

你必须设计一个时间复杂度为?O(log n)?的算法解决此问题。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums?中的所有整数?互不相同
  • nums?原来是一个升序排序的数组,并进行了?1?至?n?次旋转

思路:利用一个二分查找即可完成

题解:

int findMin(int* nums, int numsSize) {
    int left,right;
    right=numsSize-1,left=0;
    while(left<right){
        int mid=(left+right)/2;
        if(nums[mid]<nums[right])right=mid;
        else
        left=mid+1;
    }
    return nums[left];
}

485.?最大连续 1 的个数

提示

简单

给定一个二进制数组?nums?, 计算其中最大连续?1?的个数。

示例 1:

输入:nums = [1,1,0,1,1,1]
输出:3
解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3.

示例 2:

输入:nums = [1,0,1,1,0,1]
输出:2

提示:

  • 1 <= nums.length <= 105
  • nums[i]?不是?0?就是?1.

思路:题目其实很简单,我们只需要使用一个循环,每当为1时采用计数+1,当计数>max时把计数值赋值给max,当数组元素为0时计数清楚,重新计数

题解:

int findMaxConsecutiveOnes(int* nums, int numsSize) {
    int a[100];
    int k=0,j=0,max=0;
    for(int i=0;i<numsSize;i++){
       if(nums[i]==1){
           k++;
           if(k>max)max=k;
       }
       else if(nums[i]==0)k=0;
    }

    return max;
}

1464.?数组中两元素的最大乘积

提示

简单

给你一个整数数组?nums,请你选择数组的两个不同下标?i?和?j使?(nums[i]-1)*(nums[j]-1)?取得最大值。

请你计算并返回该式的最大值。

示例 1:

输入:nums = [3,4,5,2]
输出:12 
解释:如果选择下标 i=1 和 j=2(下标从 0 开始),则可以获得最大值,(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。 

示例 2:

输入:nums = [1,5,4,5]
输出:16
解释:选择下标 i=1 和 j=3(下标从 0 开始),则可以获得最大值 (5-1)*(5-1) = 16 。

示例 3:

输入:nums = [3,7]
输出:12

提示:

  • 2 <= nums.length <= 500
  • 1 <= nums[i] <= 10^3

思路:简单题一个,暴力直接解决

题解:

int maxProduct(int* nums, int numsSize) {
    int max=0;
    for(int i=0;i<numsSize;i++){
        for(int j=i+1;j<numsSize;j++){
            if(((nums[i]-1)*(nums[j]-1))>max)max=(nums[i]-1)*(nums[j]-1);
        }
    }
    return max;
}

文章来源:https://blog.csdn.net/xxx_jsu/article/details/135231395
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。