https://www.bilibili.com/video/BV1xt4y1e7q4?p=1
一、双指针算法 | Two Pointers
双指针算法是指利用两个指针遍历数组(链表),左右指针相向前进或同向前进,在遍历过程中根据某种限制条件进行筛选,通常可以把时间复杂度降低至O(n)。
- 普通双指针:两个指针同向移动
- 对撞双指针:两个指针面对面移动
- 快慢双指针:慢指针+快指针
1、快慢指针
141. 环形链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public boolean hasCycle(ListNode head) { //链表节点数为0,一定不是循环链表 if(head == null) return false; //初始化快慢指针 ListNode slow = head; ListNode fast = head; //条件成立说明链表是循环的 while(fast != null && fast.next != null){//快指针在慢指针前面,只需要判断快指针不为空即可 slow = slow.next; fast = fast.next.next; //快指针追上了慢指针,是循环链表 if(slow == fast) return true; } //循环条件不成立,默认不是循环链表 return false; }
2、对撞指针
881. 救生艇
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public int numRescueBoats(int[] people, int limit) { //处理边界值 if(people == null || people.length == 0) return 0; 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; }
二、二分查找法 | Binary Search
二分查找法,是在已经排好序的序列中,定义一个起始位置start(即序列第一个元素)和一个终止位置end(即序列最后一个元素),通过mid=(start+end)/2计算出中间位置,
通过待查找元素与mid中间位置的元素进行比较,如果待查找元素比中间位置mid对应的值小,那么将end = mid -1(即将end结束位置移动到mid中间左边一个位置),
如果比中间对应的值大,那么将start = mid + 1 (即将start的位置移动到mid右边一个位置),一直循环查找,直到start > end,证明没找到对应的元素,停止循环。
应用场景(适用条件)
至少满足以下两个条件:
- 已经排好序的序列
- 需要查找某个或者某多个值
例题1
704. 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public int search(int[] nums, int target) { //处理边界值 if(nums == null || nums.length==0) return -1; //初始化 int start = 0; int end = nums.length-1; while(start<=end){ int mid=(start+end)/2; if(nums[mid]==target) return mid; else if(nums[mid]<target) start = mid + 1; else end = mid - 1; } return -1; }
例题2
35. 搜索插入位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28//处理边界值 if(nums == null || nums.length == 0) return 0; //初始化 int start = 0; int end = nums.length -1; int mid = (start+end)/2; boolean falg = false;//目标值不存在于数组中 while(start<=end){ mid = (start+end)/2; if(nums[mid]==target){ falg = true;//目标值存在于数组中 return mid; } else if(nums[mid]<target) start=mid+1; else end=mid-1; } //如果目标值不存在于数组中 if(!falg && nums[mid] > target){ return mid; } if(!falg && nums[mid] < target){ return mid +1; } return 0;
例题3
162. 寻找峰值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public int findPeakElement(int[] nums) { //处理边界值 if(nums == null || nums.length == 0) return -1; //初始化 int start = 0; int end = nums.length-1; while(start<end) { int mid = (start+end)/2; if(nums[mid] < nums[mid+1])//mid<mid+1,递增,峰值在mid的右边 start = mid +1; else//mid>=mid+1,递减,峰值在mid左边或者就是mid end = mid; //最终start和end都在峰值,即start==end不符合循环条件 } return end; }
例题四
74. 搜索二维矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public boolean searchMatrix(int[][] matrix, int target) { //处理边界值 if(matrix == null || matrix.length == 0) return false; int m = matrix.length; //行数 int n = matrix[0].length; //列数 //二维数组转变成一维数组的样子,再进行二分查找。例如[0,0]-->0*n+0; [3,1]-->3*n+1 int start = 0*n + 0; int end = (m-1)*n + (n-1); while(start <= end) { int mid = (start+end)/2; int i = mid/n; int j = mid%n; if(matrix[i][j] == target) //找到了 return true; else if(matrix[i][j] > target) //目标在左边 end = mid -1; else //目标在右边 start = mid +1; } return false; }
三、滑动窗口 | Sliding Window
目的:减少while循环
例如a=[1,4,2,3,4,5,6],3个为一组,取最大的和。
3个为一组看不出来滑动窗口的优点,但是如果1w个为一组呢?
例题1
209. 长度最小的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public int minSubArrayLen(int target, int[] nums) { if(nums == null || nums.length == 0) return 0; int res = nums.length + 1; //最小长度 int total = 0;//连续子数组的和 int i = 0;//左指针 int j = 0;//右指针 while(j<nums.length){ total+=nums[j]; j++;//j右移 //连续子数组的和>=target,i右移 while(total>=target){ res = Math.min(res, j-i); total -= nums[i]; i++;//i右移 } } if(res == nums.length +1) return 0; else return res; }
1456. 定长子串中元音的最大数目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23//1、滑动窗口 public int maxVowels(String s, int k) { int left = 0; int right = 0; int max = 0;//最大 int count = 0; while(right<s.length()){ char cr = s.charAt(right); if(cr=='a'||cr=='e'||cr=='i'||cr=='o'||cr=='u') count++; right++; if(right-left==k){ max = Math.max(max, count); char cl = s.charAt(left); if(cl=='a'||cl=='e'||cl=='i'||cl=='o'||cl=='u') count--; left++; } } return max; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32//2、集合类 public int maxVowels(String s, int k) { if(s == null || s.length()==0 || s.length()<k) return 0; HashSet<Character> set = new HashSet<Character>(); set.add('a'); set.add('e'); set.add('i'); set.add('o'); set.add('u'); int count = 0;//每组内的元音字母数计数 int res = 0;//最大元音字母数 //左指针j = i-k; 右指针i = 0; //第一组 for(int i=0; i<k; i++) { if(set.contains(s.charAt(i))) //如果i是元音字母 count++; } res = Math.max(count, res); //其他组 for(int i=k; i<s.length(); i++) { if(set.contains(s.charAt(i))) //如果i是元音字母 count++; if(set.contains(s.charAt(i-k))) //如果i-k是元音字母 count--; res = Math.max(count, res); } return res; }
四、递归 | Recursion
四个要素
- 接受的参数
- 返回值
- 终止的条件
- 递归拆解,如何递归到下一层
时间复杂度o(n),空间复杂度o(n)
例题1
509. 斐波那契数
1
2
3
4
5
6
7public int fib(int n) { if(n==0) return 0; if(n==1) return 1; return fib(n-1)+fib(n-2); }
例题2
206. 反转链表
1
2
3
4
5
6
7
8public ListNode reverseList(ListNode head) { if(head==null || head.next==null) //链表为null或者指向链表最后一个元素时 return head; ListNode P = reverseList(head.next); head.next.next = head; head.next = null; return P; }
344. 反转字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//递归方式 public void reverseString(char[] s) { if(s == null || s.length == 0) return; int left = 0; int right = s.length-1; func(s, left, right); } public void func(char[] s, int left, int right){ if(left>=right) return; func(s,left+1,right-1); char temp = s[right]; s[right] = s[left]; s[left] = temp; return; }
1
2
3
4
5
6
7
8
9
10
11
12//双指针(简单,优化较好) public void reverseString(char[] s) { int i = 0; int j = s.length-1; while(i<=j){ char temp = s[j]; s[j] = s[i]; s[i] = temp; j--; i++; } }
五、分治法 | Divide And Conquer
- 大问题切割成一个个小问题
- 用到递归,自己调用自己
归并排序就是一个用分治法的经典例子:
- 归并排序首先把原问题拆分成2个规模更小的子问题。
- 递归地求解子问题,当子问题规模足够小时,可以一下子解决它。在这个例子中就是,当数组中的元素只有1个时,自然就有序了。
- 最后,把子问题的解(已排好序的子数组)合并成原问题的解。
例题1
169. 多数元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28public int majorityElement(int[] nums) { return getMajority(nums, 0, nums.length-1); } public int getMajority(int[] nums, int left, int right) { //终止条件 if(left==right) return nums[left];//只剩一个,返回多数元素 int mid = (left+right)/2; int leftMajority = getMajority(nums, left, mid);//左边多数元素 int rightMajority = getMajority(nums, mid+1, right);//右边多数元素 if(leftMajority==rightMajority)//如果左边多数元素=右边多数元素 return leftMajority; 如果左边多数元素和右边多数元素不一样,那么就要合并-->nums[left,right],遍历 int leftCount = 0; int rightCount = 0; for(int i=left; i<=right; i++) { if(nums[i] == leftMajority) leftCount++; if(nums[i] == rightMajority) rightCount++; } if(leftCount>rightCount) return leftMajority; else return rightMajority; }
例题2
53. 最大子序和
1
六、回溯法 | Backtracking
类似枚举,一层一层向下递归,尝试搜索答案
回溯算法=DFS+剪枝
找到答案:
- 尝试别的答案
- 返回答案
找不到答案:
- 返回上一层递归,尝试别的路径
例题1
22. 括号生成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<String>(); backtracking(n, result, 0, 0, ""); return result; } private void backtracking(int n, List<String> result, int left, int right, String str) { if(left < right)//不合格 return; if(left == right && right == n)//结果 result.add(str); if(left<n)//加左括号 backtracking(n, result, left+1, right, str+"("); if(right<left)//加右括号 backtracking(n, result, left, right+1, str+")"); }
例题2
78. 子集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); //结果集 result.add(new ArrayList<Integer>()); for(int i=1; i<=nums.length; i++)//长度0、1、2、3... backtracking(nums, result, i, 0, new ArrayList<Integer>()); return result; } //nums 整数数组; result 结果集; length 长度; index 索引; subset 子集 public void backtracking(int[] nums, List<List<Integer>> result, int length, int index, List<Integer> subset) { //如果当前子集长度==length,合格,填充到结果集result if(subset.size() == length) { List<Integer> temp = new ArrayList<Integer>(subset); result.add(temp); return; } //找子集 for(int i=index; i<nums.length; i++) { subset.add(nums[i]); backtracking(nums, result, length, i+1, subset); subset.remove(subset.size()-1); } }
七、深度优先搜索 DFS
例题1
938. 二叉搜索树的范围和
1
2
3
4
5
6
7
8
9
10
11
12//递归 public int rangeSumBST(TreeNode root, int low, int high) { if(root==null) return 0; int leftSum = rangeSumBST(root.left, low, high); int rightSum = rangeSumBST(root.right, low, high); int result = leftSum + rightSum; if(low <= root.val && root.val <= high) result += root.val; return result; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//BFS public int rangeSumBST(TreeNode root, int low, int high) { int result = 0; Queue<TreeNode> q = new LinkedList<>(); q.add(root);//创建一个队列,把根节点加进去 while(q.size() > 0){ int size = q.size(); while(size > 0){ TreeNode cur = q.poll();//取队尾 if(low <= cur.val && cur.val <= high) result += cur.val; if(cur.left != null) q.add(cur.left); if(cur.right != null) q.add(cur.right); size --; } } return result;
例题2
200. 岛屿数量
1
2
最后
以上就是寂寞世界最近收集整理的关于Leetcode力扣必备算法知识和练习题一、双指针算法 | Two Pointers二、二分查找法 | Binary Search三、滑动窗口 | Sliding Window四、递归 | Recursion五、分治法 | Divide And Conquer六、回溯法 | Backtracking七、深度优先搜索 DFS的全部内容,更多相关Leetcode力扣必备算法知识和练习题一、双指针算法内容请搜索靠谱客的其他文章。
发表评论 取消回复