我是靠谱客的博主 寂寞世界,这篇文章主要介绍Leetcode力扣必备算法知识和练习题一、双指针算法 | Two Pointers二、二分查找法 | Binary Search三、滑动窗口 | Sliding Window四、递归 | Recursion五、分治法 | Divide And Conquer六、回溯法 | Backtracking七、深度优先搜索 DFS,现在分享给大家,希望可以做个参考。

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
18
public 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
19
public 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. 已经排好序的序列
  2. 需要查找某个或者某多个值

例题1

704. 二分查找

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public 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
18
public 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
24
public 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
23
public 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
7
public 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
8
public 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

  • 大问题切割成一个个小问题
  • 用到递归,自己调用自己

归并排序就是一个用分治法的经典例子:

  1. 归并排序首先把原问题拆分成2个规模更小的子问题。
  2. 递归地求解子问题,当子问题规模足够小时,可以一下子解决它。在这个例子中就是,当数组中的元素只有1个时,自然就有序了。
  3. 最后,把子问题的解(已排好序的子数组)合并成原问题的解。

例题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
28
public 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
18
public 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
23
public 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力扣必备算法知识和练习题一、双指针算法内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(85)

评论列表共有 0 条评论

立即
投稿
返回
顶部