Java

DuHouAn · DuHouAn · commit a93189e8987a · 2019-08-07T20:01:37.000+08:00
diff --git a/docs/AimForOffer/13_排序.md b/docs/AimForOffer/13_排序.md
@@ -251,15 +251,72 @@ private int partition(int[] arr,int l,int r){
 
 ## 3、堆
 
+使用数组存储二叉堆，下标从0开始：
+
+<div align="center"><img src="https://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/heap//heap_4.png" width="600px"/></div>
+
 
 
 
 
 ## 4、堆排序
 
+堆排序思路：**把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。**
+
+```java
+public void sort(int[] arr){
+    int N = arr.length;
+    //构建大根堆
+    for(int i=parent(N-1);i>=0;i--){ //从中间位置开始下沉
+        sink(arr,i,N);
+    }
+
+    //大根堆的根节点就是最大值
+    while(N>0){
+        swap(arr,0,N-1);
+        //每次交换堆的最后一个元素和堆的一个元素，每次获取的最大值
+        N--; // 相当于删除堆的第一个元素
+        sink(arr,0,N); //每次再从 0 位置开始下沉，维护长度为 (N-1) 的大根堆
+    }
+}
+
+// 从 i 位置开始下沉
+// N 是堆中元素，可以动态变化
+private void sink(int[] num,int i,int N){
+    while (leftChild(i)<N){
+        int j = leftChild(i);
+        if(j+1<N && num[j]<num[j+1]){
+            j = rightChild(i);
+        }
+        if(num[i]>=num[j]){
+            break;
+        }
+        swap(num,i,j); // i 位置和 j 位置元素交换
+        i=j; // i 元素已经下沉，需要继续下沉
+    }
+}
+
+private int parent(int i){
+    if(i==0){
+        throw new IllegalArgumentException("index=0 时，不存在父节点");
+    }
+    return (i-1)/2;
+}
 
+private int leftChild(int i){
+    return 2*i+1;
+}
 
+private int rightChild(int i){
+    return 2*i+2;
+}
 
+private void swap(int[] arr,int i,int j){
+    int tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+}
+```
 
 
 
diff --git a/docs/AimForOffer/1_数组.md b/docs/AimForOffer/1_数组.md
@@ -389,29 +389,31 @@ public int MoreThanHalfNum_Solution(int [] array) {
 [扑克牌顺子](https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
 
 ```java
+//思路：使用大小王来补充中间差的牌
+
+//为了方便统计大小王，先进行排序。
 public boolean isContinuous(int [] numbers) {
-    if(numbers.length<5){
+    if(numbers==null || numbers.length!=5){
+        //必须是5张牌，形成顺子
         return false;
     }
-
-    //统计这些牌中大小王数
-    int cnt=0;
     Arrays.sort(numbers);
-    for(int num : numbers){
-        if(num==0){
+    int n =numbers.length;
+
+    int cnt=0; //统计大小王数量
+    for(int i=0;i<n;i++){
+        if(numbers[i]==0){
             cnt++;
         }else{
             break;
         }
     }
-
-    //使用大小王补全相邻数字中间的间隙
-    for(int i=cnt;i<numbers.length-1;i++){ // i 从 cnt 开始，cnt 位置之前都是 0
-        if(numbers[i]==numbers[i+1]){
+    for(int i=cnt;i<n-1;i++){
+        if(numbers[i]==numbers[i+1]){ //牌相等，不可能形成顺子
             return false;
         }
-        //需要在 [numbers[i],numbers[i+1]] 之间插入 (numbers[i+1]-numbers[i]-1) 个元素
-        cnt -= (numbers[i+1]-numbers[i]-1);
+        int diff = numbers[i+1]-numbers[i]-1;
+        cnt -= diff;
     }
     return cnt>=0;
 }
diff --git a/docs/AimForOffer/9_回溯.md b/docs/AimForOffer/9_回溯.md
@@ -176,4 +176,54 @@ public int movingCount(int threshold, int rows, int cols) {
     visited = new boolean[m][n];
     return walk(threshold,0,0);
 }
+```
+
+
+
+## 4、全排列
+
+[全排列](https://leetcode-cn.com/problems/permutations/)
+
+```java
+
+```
+
+
+
+## 5、全排列 II
+
+[全排列 II](https://leetcode-cn.com/problems/permutations-ii/)
+
+```java
+
+```
+
+
+
+## 6、字母大小写全排列
+
+[字母大小写全排列](https://leetcode-cn.com/problems/letter-case-permutation/)
+
+```java
+
+```
+
+
+
+## 7、电话号码的字母组合
+
+[电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
+
+```java
+
+```
+
+
+
+## 8、组合
+
+[组合](https://leetcode-cn.com/problems/combinations/)
+
+```java
+
 ```
