双指针算法
-
普通双指针：两个指针往同一个方向移动
-
对撞双指针：两个指针面对面移动
- 快慢双指针：慢指针+快指针
141环形链表
给定一个链表，判断链表中是否有环。
public class Solution {//快慢指针 public boolean hasCycle(ListNode head) { if(head==null){ return false; } ListNode slow = head; ListNode fast = head; while(fast!=null && fast.next!=null){ fast = fast.next.next; slow = slow.next; if(slow ==fast){ return true; } } return false; } }
881救生艇
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
示例 1：
输入：people = [1,2], limit = 3 输出：1 解释：1 艘船载 (1, 2)
class Solution {//对撞指针 public int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int i=0; int j=people.length-1; int res=0; while(i<=j){ if(people[i]+people[j]<=limit){ i++; } j--; res++; } return res; } }
二分查找算法
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
class Solution { public int search(int[] nums, int target) { if(nums==null || nums.length==0){ return -1; } int left=0; int right=nums.length-1; while(left<=right){ int mid = left+(right-left)/2;//防止边界越界，超过int范围 if(nums[mid]==target){ return mid; }else if(nums[mid]>target){ right=mid-1; }else{ left=mid+1; } } return -1; } }
35搜索插入位置
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2
class Solution { public int searchInsert(int[] nums, int target) { if(nums==null ||nums.length==0){ return 0; } int left = 0; int right=nums.length-1; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]==target){ return mid; }else if(nums[mid]>target){ right=mid; }else{ left=mid+1; } } return nums[left]<target? left+1:left; } }
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。
class Solution { public int findPeakElement(int[] nums) { if(nums==null || nums.length==0){ return -1; } int l=0; int r=nums.length-1; while(l<r){ int mid = l+(r-l)/2; if(nums[mid]>nums[mid+1]){ r=mid; }else{ l=mid+1; } } return l; } }
74搜索二维矩阵
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix==null || matrix.length==0){ return false; } int row = matrix.length;//行 int col = matrix[0].length;//列 int l=0; int r=row*col-1; while(l<=r){ int mid = l+(r-l)/2; int element = matrix[mid/col][mid%col]; if(element==target){ return true; }else if(element>target){ r=mid-1; }else{ l=mid+1; } } return false; } }
滑动窗口
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
class Solution { public int minSubArrayLen(int target, int[] nums) { if(nums==null || nums.length==0){ return 0 ; } int i=0; int j=0; int result=nums.length+1; int total=0; while(j<nums.length){//窗口的最后一个 total+=nums[j]; j++; while(total>=target){ result=Math.min(result,j-i); total-=nums[i]; i++; } } return result==nums.length+1 ? 0:result; } }
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
示例 1：
输入：s = "abciiidef", k = 3 输出：3 解释：子字符串 "iii" 包含 3 个元音字母。
class Solution { public int maxVowels(String s, int k) { if(s==null || s.length()==0 || s.length()<k){ return 0; } HashSet<Character> set = new HashSet<>(); set.add('a'); set.add('e'); set.add('i'); set.add('o'); set.add('u'); int res=0; int count=0; for(int i=0;i<k;i++){//第一个窗口 char temp=s.charAt(i); if(set.contains(temp)){ count++; } } res=Math.max(res,count); for(int i=k;i<s.length();i++){ char out=s.charAt(i-k); char in = s.charAt(i); if(set.contains(out)){ count--; } if(set.contains(in)){ count++; } res=Math.max(res,count); } return res; } }