Skip to content

Commit f6ab703

Browse files
JstarfishJstarfish
committed
:docs: search
1 parent 04cbbf3 commit f6ab703

File tree

63 files changed

+8252
-8072
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

63 files changed

+8252
-8072
lines changed

‎docs/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/data-structure-algorithms/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/data-structure-algorithms/Sort.md‎

Lines changed: 11 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,14 @@
1-
# 排序
2-
3-
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：**插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序**等。用一张图概括：
4-
5-
![十大经典排序算法 概览截图](http://qiniu.ikeguang.com/image/sortAlgo/sort.png)
1+
---
2+
title: 排序
3+
date: 2023-10-09
4+
tags:
5+
- Algorithm
6+
categories: Algorithm
7+
---
8+
9+
> 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：**插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序**等。用一张图概括：
10+
>
11+
> ![十大经典排序算法 概览截图](/Users/starfish/Desktop/sort.png)
612
713
**关于时间复杂度**：
814

‎docs/data-structure-algorithms/algorithm/Binary-Search.md‎

Lines changed: 110 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -75,55 +75,68 @@ int binarySearch(int[] nums, int target) {
7575

7676
> 比如说给你有序数组 `nums = [1,2,2,2,3]`，`target` 为 2，此算法返回的索引是 2，没错。但是如果我想得到 `target` 的左侧边界，即索引 1，或者我想得到 `target` 的右侧边界，即索引 3，这样的话此算法是无法处理的。
7777
>
78-
> 所以又有了下边两种左右边界的二分。
78+
> 所以又有了一些含有重复元素，带有边界问题的二分。
7979
8080
### 寻找左侧边界的二分搜索
8181

8282
```java
83-
public int getLeftNums(int[] nums,int target) {
84-
int left = 0, right = nums.length - 1;
85-
// 搜索区间为 [left, right]
83+
public static int leftBound(int[] nums, int target) {
84+
int left = 0;
85+
int right = nums.length - 1;
8686
while (left <= right) {
87-
int mid = left + (right - left) / 2;
88-
if (nums[mid] == target) {
89-
// 收缩右侧边界
90-
right = mid - 1;
91-
} else if (nums[mid] > target) {
92-
// 搜索区间变为 [left, mid-1]
87+
int mid = (right - left) / 2 + left;
88+
if (nums[mid] > target) {
9389
right = mid - 1;
9490
} else if (nums[mid] < target) {
95-
// 搜索区间变为 [mid+1, right]
9691
left = mid + 1;
92+
} else {
93+
//mid 是第一个元素，或者前一个元素不等于查找值，锁定
94+
if (mid == 0 || nums[mid - 1] != target) return mid;
95+
else right = mid - 1;
9796
}
9897
}
99-
// 判断 target 是否存在于 nums 中，防止数组越界
100-
// 此时 target 比所有数都大，返回 -1
101-
if (left == nums.length) return -1;
102-
// 判断一下 nums[left] 是不是 target
103-
return nums[left] == target ? left : -1;
98+
return -1;
10499
}
105100
```
106101

107-
> while 终止的条件是 `left == right`，所以返回 left 和 right 是一样的
108-
109102
### 寻找右侧边界的二分查找
110103

111104
```java
112-
public int getRightNums(int[] nums, int target) {
113-
int left = 0, right = nums.length - 1;
105+
public static int rightBound(int[] nums, int target){
106+
int left = 0;
107+
int right = nums.length - 1;
108+
while(left <= right){
109+
int mid = left + (right - left)/2;
110+
if(nums[mid] > target){
111+
right = mid - 1;
112+
}else if(nums[mid] < target){
113+
left = mid +1;
114+
}else{
115+
if(mid == nums.length - 1 || nums[mid +1] != target) return mid;
116+
else left = mid + 1;
117+
}
118+
}
119+
return -1;
120+
}
121+
```
122+
123+
### 查找第一个大于等于给定值的元素
124+
125+
```JAVA
126+
//查找第一个大于等于给定值的元素 1,3,5,7,9 找出第一个大于等于5的元素
127+
public int firstNum(int[] nums, int target) {
128+
int left = 0;
129+
int right = nums.length - 1;
114130
while (left <= right) {
115131
int mid = left + (right - left) / 2;
116-
if (nums[mid] == target) {
117-
// 别返回，增大「搜索区间」的左边界，收缩左侧边界，
132+
if (nums[mid] >= target) {
133+
if (mid == 0 || nums[mid - 1] < target) return mid;
134+
else right = mid - 1;
135+
} else {
118136
left = mid + 1;
119-
} else if (nums[mid] > target) {
120-
right = mid - 1;
121-
} else if (nums[mid] < target) {
122-
left = mid + 1;
123137
}
124138
}
125-
if (right < 0) return -1;
126-
return nums[right] == target ? right : -1;
139+
return -1;
127140
}
128141
```
129142

@@ -132,21 +145,20 @@ public int getRightNums(int[] nums, int target) {
132145
### [153. 寻找旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)
133146

134147
> 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
135-
> 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
136-
> 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
148+
> 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
137149
> 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
138-
>
139-
> 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
140-
>
141-
> 你必须设计一个时间复杂度为 $O(log n)$ 的算法解决此问题。
142-
>
143-
> ```
150+
>
151+
>给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
152+
>
153+
>你必须设计一个时间复杂度为 $O(log n)$ 的算法解决此问题。
154+
>
155+
>```
144156
> 输入：nums = [3,4,5,1,2]
145157
> 输出：1
146158
> 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
147159
> ```
148-
>
149-
> ```
160+
>
161+
>```
150162
> 输入：nums = [11,13,15,17]
151163
> 输出：11
152164
> 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
@@ -166,9 +178,7 @@ public int getRightNums(int[] nums, int target) {
166178
> - 如果有目标值 target，那么直接让 arr[mid] 和 target 比较即可。
167179
> - 如果没有目标值，一般可以考虑 **端点**
168180
169-
![fig1](https://assets.leetcode-cn.com/solution-static/153/1.png)
170-
171-
旋转数组，最小值右侧的元素肯定都小于数组中的最后一个元素 `nums[n-1]`，左侧元素都大于 `num[n-1]`
181+
旋转数组，最小值右侧的元素肯定都小于或等于数组中的最后一个元素 `nums[n-1]`，左侧元素都大于 `num[n-1]`
172182
173183
```java
174184
public static int findMin(int[] nums) {
@@ -624,6 +634,64 @@ public static boolean findNumberIn2DArray(int[][] matrix, int target) {
624634

625635
### [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/)
626636

637+
> 给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。
638+
>
639+
> **子序列** 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]`是数组 `[0,3,1,6,2,2,7]` 的子序列。
640+
>
641+
> ```
642+
> 输入：nums = [10,9,2,5,3,7,101,18]
643+
> 输出：4
644+
> 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。
645+
> ```
646+
647+
648+
649+
627650
651+
### [4. 寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/)
652+
653+
> 给定两个大小分别为 `m` 和 `n` 的正序（从小到大）数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的 **中位数** 。
654+
>
655+
> 算法的时间复杂度应该为 `O(log (m+n))` 。
656+
>
657+
> ```
658+
> 输入：nums1 = [1,3], nums2 = [2]
659+
> 输出：2.00000
660+
> 解释：合并数组 = [1,2,3] ，中位数 2
661+
> ```
662+
663+
664+
665+
666+
667+
### [35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/)
668+
669+
> 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 `O(log n)` 的算法。
670+
>
671+
> ```
672+
> 输入: nums = [1,3,5,6], target = 2
673+
> 输出: 1
674+
> ```
675+
676+
```java
677+
public int searchInsert(int[] nums, int target) {
678+
int left = 0;
679+
int right = nums.length - 1;
680+
//注意：特例处理
681+
if (nums[left] > target) return 0;
682+
if (nums[right] < target) return right + 1;
683+
while (left <= right) {
684+
int mid = left + (right - left) / 2;
685+
if (nums[mid] > target) {
686+
right = mid - 1;
687+
} else if (nums[mid] < target) {
688+
left = mid + 1;
689+
} else {
690+
return mid;
691+
}
692+
}
693+
//注意：这里如果没有查到，返回left,也就是需要插入的位置
694+
return left;
695+
}
696+
```
628697
629-
- https://labuladong.gitee.io/algo/2/22/61/

‎docs/data-structure-algorithms/algorithm/Dynamic-Programming.md‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,10 @@
1-
# 动态规划——刷题有套路
1+
---
2+
title: 动态规划——刷题有套路
3+
date: 2024-03-09
4+
tags:
5+
- Algorithm
6+
categories: Algorithm
7+
---
28

39
> 动态规划，简直就是刷题模板、套路届的典范
410
@@ -150,7 +156,7 @@ public int fib(int n) {
150156

151157
有了上一步「备忘录」的启发，**自顶向下**的递推，每次“缓存”之前的结果，那**自底向上**的推算不也可以吗？而且推算的时候，我们只需要存储之前的两个状态就行，还省了很多空间，我靠，真是个天才，这就是，**动态规划**的做法。
152158

153-
![](../../../picBed/img/20200922111558.png)
159+
![](https://img.starfish.ink/leetcode/down2up.png)
154160

155161
画个图就很好理解了，我们一层一层的往上计算，得到最后的结果。
156162

‎node_modules/@vuepress/core/.temp/app-enhancers/global-components-2.js‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎node_modules/@vuepress/core/.temp/app-enhancers/global-components-3.js‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎node_modules/@vuepress/core/.temp/app-enhancers/global-components-4.js‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎node_modules/@vuepress/core/.temp/app-enhancers/global-components-5.js‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎node_modules/@vuepress/core/.temp/app-enhancers/global-components-6.js‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

0 commit comments

Comments
 (0)