力扣刷题(数组篇)

简介: 力扣刷题(数组篇)

1.二分查找

力扣题目链接:704. 二分查找 - 力扣(LeetCode) (leetcode-cn.com)

3.题目描述8a73a711e92b483b99cab5201321862c.png

解题思路

1. 这道题给的要求很明显 一个有序的数组,我们还可以发现这个数组中的元素是不重复的

2.因为二分查找的话返回的元素下标可能不是唯一的,这些都是用二分的前提条件

3.我们定义target在左闭右开的区间里 也就是 题目的[left,right] 当while(left<=right)的时候

因为left=right是有意义的


源码附上:

class Solution {
    public int search(int[] nums, int target) {
            int left=0;
            int right=nums.length-1;
            while(left<=right){
                int mid=left+(right-left)/2; //这里防止溢出 等同于(left+right)/2
                if(target>nums[mid]){ //这里target在右区间 所以left=mid+1
                    left=mid+1;
                }
                else if(target<nums[mid]){ //这里target在左区间 所以right=mid-1
                    right=mid-1;
                }
                else if(target==nums[mid]){ //target ==nums[mid]的时候也就是找到目标值的时候返回下标
                    return mid;
                }
            }
            return -1; //否则返回-1
    }
}

2.反转字符串

题目链接  344. 反转字符串 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

1e42afafc1a84c6f8378fc880a6f6fc8.png

解题思路:

本题是一道经典的双指针 题目

用left指向字符数组首元素

用right指向字符数组尾元素

跑一个交换一个 直到跑到中间为止


代码附上:

class Solution {
    public void reverseString(char[] s) {
            int left=0;
            int right=s.length-1;
            while(left<right){ //左边元素小于右边元素时 ,交换俩俩元素
                char tmp=s[left];
                s[left]=s[right];
                s[right]=tmp;
                left++;  // 左边元素往右边走
                right--; //右边元素往左边走
            }
    }
}

3.长度最小的子数组

题目链接:209. 长度最小的子数组 - 力扣(LeetCode) (leetcode-cn.com)

题目描述 :

a20313b891e84ffb8a4a9c8e315dd6b7.png

解题思路:

这道题 可以用暴力解法 两个for循环,然后不断的寻找符合条件的连续子数组 但是时间复杂度为O(n^2)


小王同学 想到了滑动窗口的解法 :

我们先定义两个指针 left 和right,将区间看成[left,right]看成一个滑动窗口,left表示窗口开始

的位置 right表示窗口结束的位置,同时我们在初始化一个sum变量来保存区间的和

然后枚举整个数组 每次向右滑动窗口 注意在滑动窗口的同时也要收缩窗口

最后收缩的窗口区间依旧满足


代码实现:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
            int sum=0; 
            int left=0;//窗口开始的位置
            int res=Integer.MAX_VALUE;//最大值
            for(int right=0;right<nums.length;right++){ //枚举整个区间
                sum+=nums[right]; //向右扩展窗口
                while(sum>=target){ 
                    res=Math.min(res,right-left+1);//区间更新
                    sum-=nums[left++]; 向左收缩窗口
                }
            }
            return res==Integer.MAX_VALUE?0:res; //按条件返回 
    }
}

以上就是我给友友们带来的几道 数组类的题 希望对大家有所帮助

相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
22天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
3月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
3月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
17天前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
17 4
|
17天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
12 0
Leetcode第三十三题(搜索旋转排序数组)
|
17天前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
43 0