add

haoyang.shi · haoyang.shi · commit 7e44ce3d1b66 · 2019-05-05T10:29:10.000+08:00
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -132,7 +132,7 @@
 	- [二进制中1的个数](offer/number-of-one.md)
 	- [数值的整数次方](offer/power.md)
 	- [打印最大的 n 位数](offer/printn.md)
-	- [在O(1)的时间复杂度下删除节点](offer/o1DeleteNode.md)
+	- [在O(1)的时间复杂度下删除节点](offer/O1DeleteNode.md)
 	- [调整数组顺序使奇数位于偶数前面](offer/reOrderArray.md)
 	- [链表中倒数第k个结点](offer/FindKthToTail.md)
 	- [反转链表](offer/revert-link.md)
diff --git a/offer/O1DeleteNode.md b/offer/O1DeleteNode.md
@@ -1 +1,35 @@
 # 在O(1)的时间复杂度下删除节点
+
+## 题目
+
+给定单向链表的头指针以及待删除的指针，定义一个函数在 O(1) 的时间复杂度下删除
+
+## 解题思路
+
+  1. 待删除节点非尾节点，将后一个节点的值复制到当前节点，然后删除后一个节点
+  2. 待删除节点为尾节点，从头节点开始，找到待删除节点的前一个节点进行删除
+
+```
+public void O1DeleteNode(ListNode head, ListNode needDelete) {
+
+    if (needDelete.next != null) {
+        ListNode next = needDelete.next.next;
+        needDelete.val = needDelete.next.val;
+        needDelete.next = next;
+
+    } else {
+        ListNode cursor = head;
+
+        while (cursor != null) {
+            if (cursor.next == needDelete) break;
+
+            cursor = cursor.next;
+        }
+
+        if (cursor == null) return;
+
+        cursor.next = needDelete.next;
+    }
+
+}
+```
diff --git a/offer/SumOfNDice.md b/offer/SumOfNDice.md
@@ -1 +1,57 @@
 # n个骰子的点数
+
+## 题目
+
+把 n 个骰子扔在地上，所有骰子朝上一面的和为 s，输入 n，打印 s 所有可能值的概率
+
+## 解题思路
+
+  1. 首先考虑一个骰子的情况，那么有 1～6 出现的次数均为 1
+  2. 再增加一个骰子时，由于各个点数出现的概率一致。用 $f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)$
+  3. 使用两个数组循环求解
+  
+```
+public void SumOfNDice(int n) {
+    if (n < 1) {
+        return;
+    }
+
+    int[][] nums = new int[2][n * 6 + 1];
+
+    int flag = 0;
+
+    //初始化第一个骰子各总和出现的次数
+    int maxLen = nums[0].length;
+    for (int i = 1; i < maxLen; i++) {
+        nums[flag][i] = 1;
+    }
+
+    for (int i = 2; i <= n; i++) {
+        int newFlag = flag ^ 0x01;
+        Arrays.fill(nums[newFlag], 0);
+
+        for (int j = i; j < maxLen; j++) {
+            int sum = 0;
+
+            for (int k = 1; k <= 6 && (j - k >= 0); k++) {
+                sum += nums[flag][j - k];
+            }
+
+            nums[newFlag][j] = sum;
+        }
+        flag = newFlag;
+    }
+
+    //debug out
+    System.out.println(Arrays.toString(nums[flag]));
+
+    int sum = 0;
+    for (int i : nums[flag]) {
+        sum += i;
+    }
+
+    for (int i = 0; i < nums[flag].length; i++) {
+        System.out.println(i + ":" + nums[flag][i] * 1.0 / sum);
+    }
+}
+```
