Coder

题目：把 $n$ 个骰子扔在地上，所有骰子朝上一面的点数之和为 $s$。输入 $n$，打印出 $s$ 所有可能的值出现的概率。 一个骰子总共有 $6$ 面，所以总共有 $6^n$ 总情况，所以我们需要统计出所以 $s$ 可能出现的次数，然后除以 $6 ^ n$ 就可以得到所有值出现的概率。 现在的问题就是怎么统计 $s$ 点出现的次数，我们以 $f(i, s)$ 表示 $i$ 个骰子投出 $s$ 点的次数，因为第 $i$ 个骰子能够投出 $1, 2, 3, 4, 5, 6$ 点 $6$ 种情况，所以只要前 $i - 1$ 个骰子投出 $s-1, s-2, s-3, s-4, s-5, s-6$ 的点数，均可以使得 $i$ 个骰子投出 $s$ 点，所以我们可以得到这样的关系式$$f(i,s) = f(i-1, s-1) + f(i-1, s-2) + f(i-1, s-3) + f(i-1, s-4) + f(i-1, s-5)+ f(i-1, s-6)$$代码如下 public static double[] probability(int n) { if (n & ...

题目：输入两个链表，找出它们的第一个公共节点。链表节点定义如下： private static class ListNode { ListNode next; int value; public ListNode(int value) { this.value = value; this.next = null; }} 首先我们会考虑蛮力法，我们在遍历第一个链表时，每访问一个节点，我们都会去第二个链表查看是否有相同的节点，如果有说明它们重合，这个节点即是它们的公共节点。如果第一个链表的长度为 $m$，第二个链表的长度为 $n$，那么时间复杂度为 $O(mn)$。 如果我们能从链表的尾部开始遍历的话，那么最后一个相同的节点即是它们第一个公共节点。但是由于题目所给出的链表是单向链表，不能从尾部开始遍历。但是我们可以考虑使用栈，我们在遍历两个链表时将节点添加到栈中，接着从栈中取出元素，是不是就相当于从尾部开始遍历链表了。使用这种方法需要 $O(m+n)$ 的时间复杂度和 $O(m + n)$ ...

题目：给定一棵二叉搜索树，请找出其中第 $k$ 大的节点。例如，下图的二叉搜索树中，第 $3$ 大的节点是 $7$ 其实解决这道题的算法十分的简单，因为对于二叉搜索树来说，它的中序遍历是排好序的结果，我们要查找第 $k$ 大的节点，只要中序遍历到第 $k$ 个节点即可，这个节点即是第 $k$ 大的节点 public class GetKthNode { // 以全局变量表示还需遍历多少个节点 private static int count; private static class BinaryTreeNode { BinaryTreeNode left; BinaryTreeNode right; int value; public BinaryTreeNode(int value) { this.value = value; this.left = null; this.right = null; ...

题目：$0, 1, …, n-1$ 这 $n$ 个数字排成一个圈，从数字 $0$ 开始，每次从这个圆圈里删除第 $m$ 个数字。求出这个圆圈里剩下的最后一个数字。 这道题就是有名的约瑟夫环问题，下面介绍两种介绍，第一种是使用链表模拟该环，第二种方法是使用动态规划。 对于使用环形链表模拟环，可以很快的写出这样的代码 public static int lastRemaining(int n, int m) { List<Integer> list = new LinkedList<>(); // 将 0 ~ n-1 共 n 个数字添加到链表中 for (int i = 0; i < n; i++) { list.add(i); } // 要删除的元素的下标，因为是环形链表，我们要对链表的长度求余 int currentIndex = (m - 1) % list.size(); // 当链表中有一个以上的元素 while (list.size() > 1) ...

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如，输入字符串 abc，则打印出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。 我们要打印出字符串中字符的所有排列，就是要让字符能够出现在所有的位置上。我们的方法如下，首先将字符串分为两部分，第一部分只有首字符一个字符，第二部分是剩下的部分。接着我们分为两步出来 第一步让所有的字符都能够出现在首位，将首字符依次与后面的字符进行交换，这样能够保证首字符可以出现在后面的每个位置上，也可以保证后面的字符出现在第一个位置上 第二步我们固定第一个字符，接着处理第二部分，而第二部分的处理也是将第二部分也分为两部分，首字符与剩下的部分两部分，这是一个递归的过程，通过这样的处理，我们确保每个字符都能够出现在每个位置上 代码如下： public static void permutation(String string) { char[] str = string.toCharArray(); permutation(str, 0);}private sta ...

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如，输入一个长度为 $9$ 的数组 ${ 1, 2, 3, 2, 2, 2, 5, 4, 2 }$。由于数字 $2$ 在数组中出现了 $5$ 次，超过数组长度的一半，因此输出 $2$。 如果这个数组是排好序的数组，那么我们很容易就可以统计出每个数字出现的次数，但是题目并没有说明数组是排序的，如果我们使用排序算法进行排序，它的时间复杂度为 $O(n\log n)$，但是这并不是最快的方法，下面介绍两种更快的解法。 如果我们将数组排好序，由于有一个数字的次数超过数组长度的一般，那么中位数一定是该数，即排好序的数组的 $n/2$ 的位置处就是我们需要输出的数字，换句话说，我们需要查找数组中第 $n/2$ 大的数字，对于查找第 $k$ 大的数字，我们可以通过 $partition$ 算法。 $partition$ 是快速排序用到的算法，它将数组分为两部分，前半部分的数小于后半部分的数，返回前半部分和后半部分分界处的下标 $index$($index$ 是前半部分的最后一个数的下标)，如果该下标为 $n/2$，那么找到了我 ...

题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 $O(n)$。 我们假设使用 $f(i)$ 表示以第 $i$ 个数字结尾的子数组的最大和，那么 $f(i +1)$ 与 $f(i)$ 的关系为 $$ f(i) = \begin{cases} f(i - 1) + data[i], & f(i - 1) > 0 \\ data[i], & f(i) \leq 0 \end{cases} $$ 如果 $f(i - 1)$ 小于 $0$ 的话，那么 $f(i - 1) + data[i] < data[i]$，所以以第 $i$ 个数字结尾的数组最大和为 $data[i]$。我们最终的目标是寻找 $max [ f(i) ], i = 0, 1, …, n - 1$，所以代码如下 public static int findGreastSumOfSubArray(int[] data) { if (data == null || data.length == 0) { ...

题目：请实现函数 ComplexListNode Clone(ComplexListNode root)，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 sbling 指针指向链表中的任意节点或者 null。复杂链表的节点定义如下： private static class ComplexListNode { ComplexListNode next; ComplexListNode sibling; int value; public ComplexListNode(int value) { this.value = value; }} 一个复杂链表的示例如下所示 看到这个问题，很多人的解决方案是首先复制链表的每一个节点，并使用 next 指针连接起来，第二步再次遍历链表，并且逐次设置 sbling 指针。考虑该链表的长度为 N，那么在每次设置 sbling 节点时都要搜索整个链表，搜索的时间复杂度是 $O(N)$，对于每一个节点都有这个搜索过程，所 ...

Promise的使用回调地狱首先我们了解一下 Promise 出现的背景，假设有下面的程序 let name = getUserNameById(id);let score = getScoreByName(name);let scholarship = getScholarshipByScore(score);console.log(scholarship); 这个程序首先根据 id 去获取名字，接着根据拿到的名字取获得分数，最后根据分数去获取奖学金，最后打印出奖学金。但是这个程序真的能达到预期的效果吗? 答案是不能，因为 JavaScript 是异步的，对于一般的耗时操作并不会立即执行，而是将函数保存在一个队列中，直到代码执行完毕，才会拿出队列中的函数执行。所以上面的函数都不会被立即执行，所以当然没有返回值，所以上面的 name, score, scholarship 都是 undefined。 为了解决这种情况，我们一般会使用回调函数的形式，等我们根据 id 拿到 name 之后，将 name 传入回调函数，这样就可以保证”同步”的效果，所以我们将上面的代码修改如下 getUs ...

题目：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如下面的二叉树 依次打印出 8, 6, 10, 5, 7, 9, 11。二叉树节点的定义如下： private static class BinaryTreeNode { private BinaryTreeNode left; private BinaryTreeNode right; int value; public BinaryTreeNode(int value) { this.left = null; this.right = null; this.value = value; }} 这道题考察的是树的层序遍历，对于按层遍历的方法，我们使用队列来辅助遍历，具体方法如下，对于根节点，我们将它放入队列中，然后从队列中取出一个元素进行打印，然后将该节点的左右子节点放入队列中，接着从队列中取出一个元素，打印该元素，然后将该元素的左右子节点添加到队列中，重复上面的过程，直到队列为空，我们从下 ...