Skip to content

Commit 1ee8433

Browse files
DuHouAnDuHouAn
committed
Java
1 parent b301653 commit 1ee8433

File tree

9 files changed

+451
-34
lines changed

9 files changed

+451
-34
lines changed

‎docs/AimForOffer/11_贪心.md‎

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,23 @@ public int FindGreatestSumOfSubArray(int[] array) {
3535
[Leetcode](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/)
3636

3737
```java
38-
38+
//思路：
39+
// 贪心策略
40+
// 假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。
41+
public int maxProfit(int[] prices) {
42+
int n = prices.length;
43+
if(n==0 || n==1){
44+
return 0;
45+
}
46+
int minValue = prices[0];
47+
//初始时，不进行交易，当然收益为0
48+
int maxProfit = 0 ;
49+
for(int i=1;i<n;i++){
50+
minValue = Math.min(minValue,prices[i]); //在 i 轮卖出前，以最低价格买入
51+
maxProfit = Math.max(maxProfit,prices[i]-minValue); //贪心策略：每轮都买出
52+
}
53+
return maxProfit;
54+
}
3955
```
4056

4157

‎docs/AimForOffer/12_数学运算.md‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -191,3 +191,27 @@ public int Sum_Solution(int n) {
191191
}
192192
```
193193

194+
195+
196+
## *7、从 1 到 n 整数中 1 出现的次数
197+
198+
[从 1 到 n 整数中 1 出现的次数](https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
199+
200+
```java
201+
202+
```
203+
204+
> [Leetcode : 233. Number of Digit One](https://leetcode.com/problems/number-of-digit-one/discuss/64381/4+-lines-O(log-n)-C++JavaPython)
205+
206+
207+
208+
## 8、数字序列中的某一位数字
209+
210+
数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。
211+
212+
```java
213+
214+
```
215+
216+
217+

‎docs/AimForOffer/13_排序.md‎

Lines changed: 209 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -63,14 +63,6 @@ private void swap(int[] arr,int i,int j){
6363
arr[i] = arr[j];
6464
arr[j] = tmp;
6565
}
66-
67-
@Test
68-
public void test(){
69-
int[] a={3,5,2,4,1,0,-3};
70-
PrintArr.printArray(a);
71-
sort(a);
72-
PrintArr.printArray(a);
73-
}
7466
```
7567

7668
添加一个状态变量对冒泡排序进行优化：
@@ -95,14 +87,6 @@ private void swap(int[] arr,int i,int j){
9587
arr[i] = arr[j];
9688
arr[j] = tmp;
9789
}
98-
99-
@Test
100-
public void test(){
101-
int[] a={3,5,2,4,1,0,-3};
102-
PrintArr.printArray(a);
103-
sort(a);
104-
PrintArr.printArray(a);
105-
}
10690
```
10791

10892
冒泡排序是稳定的排序算法，平均时间复杂度是 O(n^2)。
@@ -138,8 +122,37 @@ private void swap(int[] arr,int i,int j){
138122

139123
### IV、希尔排序
140124

125+
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。
126+
127+
希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
128+
129+
希尔排序思路：**希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。**
130+
141131
```java
132+
public void sort(int[] arr){
133+
int N = arr.length;
134+
135+
int h=1;
136+
while(h<N/3){
137+
h = 3*h+1;
138+
}
142139

140+
while(h>=1){
141+
for(int i=1;i<N;i++){
142+
for(int j=i;j>=h && arr[j-h]>arr[j];j-=h){
143+
swap(arr,j-h,j);
144+
}
145+
}
146+
h /=3;
147+
}
148+
//注意 h 的值最终会减为 1
149+
}
150+
151+
private void swap(int[] arr,int i,int j){
152+
int tmp = arr[i];
153+
arr[i] = arr[j];
154+
arr[j] = tmp;
155+
}
143156
```
144157

145158

@@ -148,27 +161,167 @@ private void swap(int[] arr,int i,int j){
148161

149162
### I、归并排序
150163

164+
归并排序的思想：**将数组分成两部分，分别进行排序，然后归并起来**。
165+
151166
```java
167+
public void sort(int[] arr){
168+
sort(arr,0,arr.length-1);
169+
}
170+
171+
private void sort(int[] arr,int l,int r){
172+
if(l>=r){
173+
return;
174+
}
175+
int mid = (r-l)/2+l;
176+
//对 [l,mid] 进行排序
177+
sort(arr,l,mid);
178+
//对 [mid+1,r] 进行排序
179+
sort(arr,mid+1,r);
180+
//合并这两个有序数组
181+
merge(arr,l,mid,r);
182+
}
183+
184+
//合并两个有序数组
185+
//[l,mid]
186+
//[mid+1,r]
187+
private void merge(int[] arr,int l,int mid,int r){
188+
int[] nums = new int[r-l+1];
189+
int index=0;
190+
int i=l;
191+
int j=mid+1;
192+
while(i<=mid && j<=r){
193+
if(arr[i]<arr[j]){
194+
nums[index++] = arr[i++];
195+
}else{
196+
nums[index++] = arr[j++];
197+
}
198+
}
199+
while(i<=mid){
200+
nums[index++]=arr[i++];
201+
}
202+
while(j<=r){
203+
nums[index++]=arr[j++];
204+
}
152205

206+
index=0;
207+
for(int k=l;k<=r;k++){
208+
arr[k] = nums[index++];
209+
}
210+
}
153211
```
154212

155213

156214

157215
### II、快速排序
158216

217+
快速排序思路：**快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。**
218+
159219
```java
220+
public void sort(int[] arr){
221+
sort(arr,0,arr.length-1);
222+
}
223+
224+
private void sort(int[] arr,int l,int r){
225+
if(l>=r){
226+
return;
227+
}
228+
int p = partition(arr,l,r);
229+
sort(arr,l,p-1);
230+
sort(arr,p+1,r);
231+
}
160232

233+
private int partition(int[] arr,int l,int r){
234+
int pivot = arr[l];
235+
while(l<r){
236+
while(l<r && arr[r]>=pivot){
237+
r--;
238+
}
239+
arr[l] = arr[r];
240+
while(l<r && arr[l]<=pivot){
241+
l++;
242+
}
243+
arr[r] = arr[l];
244+
}
245+
arr[l]=pivot;
246+
return l;
247+
}
161248
```
162249

163250

164251

165-
## 3、堆排序
252+
## 3、堆
253+
254+
255+
256+
257+
258+
## 4、堆排序
259+
260+
261+
262+
263+
264+
265+
266+
## 5、数组中的逆序对
267+
268+
[数组中的逆序对](https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
269+
270+
```java
271+
//思路：利用归并排序算法
272+
//在合并两个有序数组中，
273+
//[l,mid]
274+
//[mid+1,r]
275+
//如果 arr[i] > arr[j]
276+
//则 arr[i] 后面的元素都会大于 arr[j],即 [i,mid] 的长度就是逆序对数
277+
278+
private long P; //逆序对数
279+
280+
public int InversePairs(int [] array) {
281+
sort(array,0,array.length-1);
282+
return (int)(P%1000000007);
283+
}
166284

285+
private void sort(int[] arr,int l,int r){
286+
if(l>=r){
287+
return;
288+
}
289+
int m=(r-l)/2+l;
290+
sort(arr,l,m);
291+
sort(arr,m+1,r);
292+
merge(arr,l,m,r);
293+
}
167294

295+
//合并 [l,m] 和 [m+1,r] 两个有序数组
296+
private void merge(int[] arr,int l,int m,int r){
297+
int[] newArr = new int[r-l+1];
298+
int index =0;
299+
int i=l;
300+
int j=m+1;
301+
while(i<=m && j<=r){
302+
if(arr[i]<=arr[j]){
303+
newArr[index++]=arr[i++];
304+
}else{ //arr[i]>arr[j]，arr[i]后面的元素都会大于 arr[j]
305+
P+=(m-i+1);
306+
newArr[index++]=arr[j++];
307+
}
308+
}
309+
while(i<=m){
310+
newArr[index++]=arr[i++];
311+
}
312+
while(j<=r){
313+
newArr[index++]=arr[j++];
314+
}
315+
index=0;
316+
for(int k=l;k<=r;k++){
317+
arr[k]=newArr[index++];
318+
}
319+
}
320+
```
168321

169322

170323

171-
## 4、最小的 k 个数（44）
324+
## 6、最小的 k 个数（44）
172325

173326
[最小的 k 个数](https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
174327

@@ -223,4 +376,41 @@ private int partion(int[] nums,int start,int end){
223376
nums[start] = pivot;
224377
return start;
225378
}
226-
```
379+
```
380+
381+
382+
383+
## 7、颜色分类
384+
385+
[颜色分类](https://leetcode-cn.com/problems/sort-colors/)
386+
387+
```java
388+
//思路:
389+
//基于快速排序的 3 路快排思路
390+
391+
public void sortColors(int[] nums) {
392+
int zero = -1;
393+
int two = nums.length;
394+
395+
for(int i=0;i<two;){
396+
if(nums[i]==0){
397+
zero++;
398+
swap(nums,zero,i);
399+
i++;
400+
}else if(nums[i]==1){
401+
i++;
402+
}else{
403+
assert nums[i]==2;
404+
two--;
405+
swap(nums,two,i);
406+
}
407+
}
408+
}
409+
410+
private void swap(int[] nums,int i,int j){
411+
int tmp =nums[i];
412+
nums[i] = nums[j];
413+
nums[j] = tmp;
414+
}
415+
```
416+

‎docs/AimForOffer/16_补充.md‎

Lines changed: 0 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -10,13 +10,3 @@
1010

1111

1212

13-
## 2、求 1+2+3+...+n
14-
15-
[求 1+2+3+...+n](https://www.nowcoder.com/practice/7a0da8fc483247ff8800059e12d7caf1?tpId=13&tqId=11200&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
16-
17-
```java
18-
19-
```
20-
21-
22-

0 commit comments

Comments
 (0)