1.了解红黑树 学习完AVL树，开始了红黑树的学习，关于红黑树，和AVL树是类似的，都是会在我们进行插入操作或者删除操作以后会进行一些操作，来使得整个二叉树保持一个平衡。 红黑树和AVL树的区别在于一个是依照平衡因子来维持整个树，而红黑树是利用颜色来限定平衡。 自从红黑树出现以后，AVL树就慢慢消失了，原因，会在后面讲解。 另外，最为重要的是在STL当中，有很多都应用了红黑树，比如：set, multiset, map, multimap 2.理解红黑树的特点 红黑树为了维持平衡，提出了4个条件。 每个节点只有黑色和红色两种区别 根节点一定是黑色。 不能出现连续的红色 每条路径上黑色节点的数目是相同的。 -每个叶子节点是黑的（这里的叶子节点这里可以理解为NUL节点和叶子节点） 通过这4个条件，就可以维持一棵红黑树的平衡。 3.红黑树节点结构 红黑的节点可以参考AVL树的节点，在AVL中，利用平衡因子维持平衡，在红黑树中，我们要利用颜色，所以，我们在这里给一个颜色。这个颜色当然只能有红的或者是黑的，所以我们在这里利用枚举来保存这个颜色。 enum color {     BLACK,     RED }; //红黑树的节点结构  template<typename K, typename V> struct RBNode {     typedef RBNode<K, V> Node;     RBNode(const K& key,const V& value)         : _left(NULL)         , _right(NULL)         , _parent(NULL)         , _key(key)         , _value(value)         , _color(RED)     {}     Node* _left;     Node* _right;     Node* _parent;     K _key;     V _value;     int _color; }; 4.红黑树的插入算法 我们首先来看红黑树的插入算法，如果你看了我的前两篇文章，关于二叉搜索树的插入算法和AVL树的插入算法以后，我想你能很快有一个大致思路，红黑树，就是插入节点，然后进行调整颜色，调整颜色过程中有些会直接进行变化颜色，有些是要通过旋转变化颜色。 为了简化插入过程，我们需要考虑我们默认插入什么颜色的节点，在这里，你可以想一下，如果你默认插入黑色节点，是否能让每条路径上黑色的节点数目相同？所以，我们默认插入的节点应该是红色节点。 在这里，为了维持那几条规则，所以我们要维护的节点和parent节点，pparent节点和uncle节点。cur就是我们所插入的节点，或者因为插入所做出调整以后影响了上面节点的情况。 在这里，我给出红黑树插入所会遇到的大致几种情况： 下面我们所讨论的统一采用cur，parent，pparent，uncle这几种命名方式。另外，我们插入的cur节点或者向上回溯时的cur皆为红色。 插入根节点 插入节点为根节点的时候，根据第二条规则，我们的根节点为黑色，所以我们记得要对根节点设置为黑色。（注：为了方便其他情况，我们可以采用没种情况都对根节点设置为黑色。） parent节点颜色为红色，uncle节点为红色。（只做变色调整，需要向上回溯）。 这个时候cur的颜色和parent的颜色都为红色，会发生问题，这个时候我们需要进行变色的调整，此时我们来看uncle，uncle为红色。 parent节点为红色，uncle节点为黑色。（旋转调整） 当parent为红色，uncle为黑色的时候，这个时候我们就需要进行旋转调整。 旋转当然分为四种情形： 1.左单旋转：  代码实现： void _BRRolateL(Node *parent)     {         assert(parent);         Node *SubR = parent->_right;         Node *SubRL = SubR->_left;         parent->_right = SubRL;         if (SubRL)             SubRL->_parent = parent;         Node *ppnode = parent->_parent;         SubR->_left = parent;         parent->_parent = SubR;         if (ppnode == NULL)         {             _root = SubR;             SubR->_parent = NULL;         }         else         {             if (ppnode->_left == parent)             {                 ppnode->_left = SubR;             }             else             {                 ppnode->_right = SubR;             }             SubR->_parent = ppnode;         }     } 2.右单旋转： 代码实现： void _BRRolateR(Node *parent)     {         assert(parent);         Node* SubL = parent->_left;         Node* SubLR = SubL->_right;         parent->_left = SubLR;         if (SubLR)             SubLR->_parent = parent;         Node *pparent = parent->_parent;         SubL->_right = parent;         parent->_parent = SubL;         if (pparent == NULL)         {             _root = SubL;             SubL->_parent = NULL;         }         else         {             if (pparent->_left == parent)             {                 pparent->_left = SubL;                 SubL->_parent = pparent;             }             else             {                 pparent->_right = SubL;                 SubL->_parent = pparent;             }         }     } 左右双旋转 ：      _BRRolateL(parent);     std::swap(parent, cur);     _BRRolateR(pparent);     pparent->_color = RED;     parent->_color = BLACK; 右左双旋转 ：      _BRRolateR(parent);     std::swap(parent, cur);     _BRRolateL(pparent);     pparent->_color = RED;    parent->_color = BLACK; 双旋转我采用了单旋转实现所以需要交换parent和cur。 这就是所有的关于插入算法旋转调整的情形。 接下来是插入算法的思路，和AVL树以及二叉搜索树的思路是类似的，都是先进行寻找，找到你所要插入的位置，然后创建节点，插入就好了。这里就不多说了，如果有疑问，可以去看我的AVL树的插入算法讲解和搜索二叉树的插入算法实现讲解。 代码实现：     bool Insert(const K& key, const V& value)     {        if (_root == NULL)         {             _root = new Node(key, value);             _root->_color = BLACK;            return true;         }         Node *cur = _root;         Node *parent = NULL;        while (cur)         {            if (cur->_key < key)             {                parent = cur;                 cur = cur->_right;             }            else if (cur->_key>key)             {                parent = cur;                 cur = cur->_left;             }            else             {                return false;             }         }         cur = new Node(key, value);        if (parent->_key > key)         {            parent->_left = cur;         }        else         {            parent->_right = cur;         }         cur->_parent = parent;        //判断如果parent是根节点，那么直接结束         while (parent!=NULL)         {            //父亲是黑色，cur是红色，符合红黑树，退出             if (parent->_color == BLACK)             {                 break;             }            //父亲和cue都是红色的情况             Node* pparent = parent->_parent;             Node* uncle = NULL;            //考虑parent 是左边的情况             if (pparent->_left == parent)             {                 uncle = pparent->_right;                //考虑叔叔是红色的情况                 if (uncle&&uncle->_color == RED)                 {                     pparent->_color = RED;                     uncle->_color = parent->_color = BLACK;                     cur = pparent;                    parent = cur->_parent;                     continue;                 }                //考虑叔叔不存在或者叔叔是黑色的情况                 else if (uncle == NULL || uncle->_color == BLACK)                 {                    if (cur == parent->_left)                     {                         _BRRolateR(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                    else                     {                         _BRRolateL(parent);                         std::swap(parent, cur);                         _BRRolateR(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                     break;                 }             }            //考虑parent是右边的情况             else             {                 uncle = pparent->_left;                if (uncle&&uncle->_color == RED)                 {                     pparent->_color = RED;                     uncle->_color = parent->_color = BLACK;                     cur = pparent;                    parent = cur->_parent;                 }                else if (uncle == NULL || uncle->_color == BLACK)                 {                    if (cur == parent->_right)                     {                         _BRRolateL(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                    else                     {                        //_BRRolateRL(pparent);                         _BRRolateR(parent);                         std::swap(parent, cur);                         _BRRolateL(pparent);                         pparent->_color = RED;                        parent->_color = BLACK;                     }                 }                 break;             }         }         _root->_color = BLACK;        return true;     } 5.红黑树的查找算法 关于红黑树而言，他的查找算法和二叉搜索树和AVL树的也几乎一样。  进行通过key实现查找就好了。 bool Find(const K& key)     {        if (_root == NULL)            return false;         Node *cur = _root;        while(cur)         {            if (cur->_key < key)             {                 cur = cur->_right;             }            else if (cur->_key>key)             {                 cur = cur->_left;             }            else             {                return true;             }         }        return false;     } 6.判断是否是和法红黑树 对于判端一棵树是否是红黑树，其实思路很简单，就是判断红黑树以及它的子树是否满足上述红黑树的特点就好了。 所以，总结下来也就是： 根节点为黑色 没有连续红色节点 每条路径上有相同的黑色节点数 当满足这三个条件的时候，我们就可以认为这棵树是合法的红黑树。 第一个条件好判断，直接可以进行判断，第二个和第三个需要进行递归。 第二个没有连续的红色节点我们的思路就是当这个节点为红色的时候，我们判断它和它的父节点是否颜色相同，如果相同就不是红黑树。 第三个条件的思路就是，因为你需要进行判断红黑树的每条路径黑节点数相同，所以首先你需要给出一个参考，然后每一条路径的黑色节点数和这个参考值进行比对就好了。如果有不相同的，那么就代表这个树不是红黑树。因为我们需要知道每条路径的，所以当一条路径算完以后，另一条路径与它相同的依然可以使用，所以我们进行传值调用。一条路径的结束，也就是找寻到了叶子节点。 bool IsRBTree()     {         //当为空树的时候，是红黑树         if (_root == NULL)         {             return true;         }         //当根节点是红色的时候，直接可以确定不是红黑树         if (_root->_color == RED)         {             return false;         }         //给出一个参考的路径的黑色节点的数目         size_t count = 0;         Node* cur = _root;         while (cur)         {             if (cur->_color == BLACK)                 count++;             cur = cur->_left;         }         //k用来记录一条路径的黑色节点的数目，和count来进行比较         size_t k = 0;         return _IsRBTree(_root, count, k);     } //这里的k需要进行传值，因为这里你需要对每一条路径进行对比，所以在这里，你要找寻完一条路径以后，向上回溯，     bool _IsRBTree(Node* root, const size_t& count, size_t k)     {         if (root == NULL)         {             return true;         }         //当出现两个连续的红色节点的时候，可以确定不是红黑树         if (root->_parent&&root->_color == root->_parent->_color == RED)         {             return false;         }         //如果是黑色节点，k进行++         if (root->_color == BLACK)         {             k++;         }         //如果是叶子节点的话，进行判断k和count是否相等         if (root->_left == NULL&&root->_right == NULL)         {             //k和count不相等，那么就不是红黑树。             if (k == count)                 return true;             else                 return false;         }         //对节点的左右进行检查         return _IsRBTree(root->_left, count, k) && _IsRBTree(root->_right, count, k);     } 转自：http://my.csdn.net/qq_26768741

3. 数组中重复的数字 NowCoder 题目描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 复制代码 1 2 3 4 5 Input: {2, 3, 1, 0, 2, 5}   Output: 2 解题思路 要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。 对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。 以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复： 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public boolean duplicate(int[] nums, int length, int[] duplication) {     if (nums == null || length <= 0)         return false;     for (int i = 0; i < length; i++) {         while (nums[i] != i) {             if (nums[i] == nums[nums[i]]) {                 duplication[0] = nums[i];                 return true;             }             swap(nums, i, nums[i]);         }     }     return false; }   private void swap(int[] nums, int i, int j) {     int t = nums[i];     nums[i] = nums[j];     nums[j] = t; } 4. 二维数组中的查找 NowCoder 题目描述 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。 复制代码 1 2 3 4 5 6 7 8 9 10 11 Consider the following matrix: [   [1,   4,  7, 11, 15],   [2,   5,  8, 12, 19],   [3,   6,  9, 16, 22],   [10, 13, 14, 17, 24],   [18, 21, 23, 26, 30] ]   Given target = 5, return true. Given target = 20, return false. 解题思路 要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。 该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean Find(int target, int[][] matrix) {     if (matrix == null || matrix.length == 0 || matrix[0].length == 0)         return false;     int rows = matrix.length, cols = matrix[0].length;     int r = 0, c = cols - 1; // 从右上角开始     while (r <= rows - 1 && c >= 0) {         if (target == matrix[r][c])             return true;         else if (target > matrix[r][c])             r++;         else             c--;     }     return false; } 5. 替换空格 NowCoder 题目描述 将一个字符串中的空格替换成 "%20"。 复制代码 1 2 3 4 5 Input: "A B"   Output: "A%20B" 解题思路 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。 从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public String replaceSpace(StringBuffer str) {     int P1 = str.length() - 1;     for (int i = 0; i <= P1; i++)         if (str.charAt(i) == ' ')             str.append("  ");       int P2 = str.length() - 1;     while (P1 >= 0 && P2 > P1) {         char c = str.charAt(P1--);         if (c == ' ') {             str.setCharAt(P2--, '0');             str.setCharAt(P2--, '2');             str.setCharAt(P2--, '%');         } else {             str.setCharAt(P2--, c);         }     }     return str.toString(); } 本文转自个人博客：CyC2018/CS-Notes 6. 从尾到头打印链表 NowCoder 题目描述 从尾到头反过来打印出每个结点的值。 解题思路 使用递归 要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。 复制代码 1 2 3 4 5 6 7 8 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {     ArrayList<Integer> ret = new ArrayList<>();     if (listNode != null) {         ret.addAll(printListFromTailToHead(listNode.next));         ret.add(listNode.val);     }     return ret; } 使用头插法 使用头插法可以得到一个逆序的链表。 头结点和第一个节点的区别： 头结点是在头插法中使用的一个额外节点，这个节点不存储值； 第一个节点就是链表的第一个真正存储值的节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {     // 头插法构建逆序链表     ListNode head = new ListNode(-1);     while (listNode != null) {         ListNode memo = listNode.next;         listNode.next = head.next;         head.next = listNode;         listNode = memo;     }     // 构建 ArrayList     ArrayList<Integer> ret = new ArrayList<>();     head = head.next;     while (head != null) {         ret.add(head.val);         head = head.next;     }     return ret; } 使用栈 栈具有后进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {     Stack<Integer> stack = new Stack<>();     while (listNode != null) {         stack.add(listNode.val);         listNode = listNode.next;     }     ArrayList<Integer> ret = new ArrayList<>();     while (!stack.isEmpty())         ret.add(stack.pop());     return ret; } 7. 重建二叉树 NowCoder 题目描述 根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 解题思路 前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // 缓存中序遍历数组每个值对应的索引 private Map<Integer, Integer> indexForInOrders = new HashMap<>();   public TreeNode reConstructBinaryTree(int[] pre, int[] in) {     for (int i = 0; i < in.length; i++)         indexForInOrders.put(in[i], i);     return reConstructBinaryTree(pre, 0, pre.length - 1, 0); }   private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {     if (preL > preR)         return null;     TreeNode root = new TreeNode(pre[preL]);     int inIndex = indexForInOrders.get(root.val);     int leftTreeSize = inIndex - inL;     root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);     root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);     return root; } 8. 二叉树的下一个结点 NowCoder 题目描述 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public class TreeLinkNode {       int val;     TreeLinkNode left = null;     TreeLinkNode right = null;     TreeLinkNode next = null;       TreeLinkNode(int val) {         this.val = val;     } } 解题思路 ① 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点； ② 否则，向上找第一个左链接指向的树包含该节点的祖先节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public TreeLinkNode GetNext(TreeLinkNode pNode) {     if (pNode.right != null) {         TreeLinkNode node = pNode.right;         while (node.left != null)             node = node.left;         return node;     } else {         while (pNode.next != null) {             TreeLinkNode parent = pNode.next;             if (parent.left == pNode)                 return parent;             pNode = pNode.next;         }     }     return null; } 9. 用两个栈实现队列 NowCoder 题目描述 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 解题思路 in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Stack<Integer> in = new Stack<Integer>(); Stack<Integer> out = new Stack<Integer>();   public void push(int node) {     in.push(node); }   public int pop() throws Exception {     if (out.isEmpty())         while (!in.isEmpty())             out.push(in.pop());       if (out.isEmpty())         throw new Exception("queue is empty");       return out.pop(); } 10.1 斐波那契数列 NowCoder 题目描述 求斐波那契数列的第 n 项，n <= 39。 f(n)=\left\{\begin{array}{rcl}0&&{n=0}\\1&&{n=1}\\f(n-1)+f(n-2)&&{n>1}\end{array}\right. f(n)= ⎩ ⎨ ⎧ ​ 0 1 f(n−1)+f(n−2) ​ ​ n=0 n=1 n>1 ​ 解题思路 如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。 递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。 复制代码 1 2 3 4 5 6 7 8 9 public int Fibonacci(int n) {     if (n <= 1)         return n;     int[] fib = new int[n + 1];     fib[1] = 1;     for (int i = 2; i <= n; i++)         fib[i] = fib[i - 1] + fib[i - 2];     return fib[n]; } 考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int Fibonacci(int n) {     if (n <= 1)         return n;     int pre2 = 0, pre1 = 1;     int fib = 0;     for (int i = 2; i <= n; i++) {         fib = pre2 + pre1;         pre2 = pre1;         pre1 = fib;     }     return fib; } 由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution {       private int[] fib = new int[40];       public Solution() {         fib[1] = 1;         for (int i = 2; i < fib.length; i++)             fib[i] = fib[i - 1] + fib[i - 2];     }       public int Fibonacci(int n) {         return fib[n];     } } 10.2 矩形覆盖 NowCoder 题目描述 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？ 解题思路 当 n 为 1 时，只有一种覆盖方法： 当 n 为 2 时，有两种覆盖方法： 要覆盖 2*n 的大矩形，可以先覆盖 2*1 的矩形，再覆盖 2*(n-1) 的矩形；或者先覆盖 2*2 的矩形，再覆盖 2*(n-2) 的矩形。而覆盖 2*(n-1) 和 2*(n-2) 的矩形可以看成子问题。该问题的递推公式如下： f(n)=\left\{\begin{array}{rcl}1&&{n=1}\\2&&{n=2}\\f(n-1)+f(n-2)&&{n>1}\end{array}\right. f(n)= ⎩ ⎨ ⎧ ​ 1 2 f(n−1)+f(n−2) ​ ​ n=1 n=2 n>1 ​ 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int RectCover(int n) {     if (n <= 2)         return n;     int pre2 = 1, pre1 = 2;     int result = 0;     for (int i = 3; i <= n; i++) {         result = pre2 + pre1;         pre2 = pre1;         pre1 = result;     }     return result; } 10.3 跳台阶 NowCoder 题目描述 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 解题思路 当 n = 1 时，只有一种跳法： 当 n = 2 时，有两种跳法： 跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题，该问题的递推公式为： f(n)=\left\{\begin{array}{rcl}1&&{n=1}\\2&&{n=2}\\f(n-1)+f(n-2)&&{n>1}\end{array}\right. f(n)= ⎩ ⎨ ⎧ ​ 1 2 f(n−1)+f(n−2) ​ ​ n=1 n=2 n>1 ​ 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int JumpFloor(int n) {     if (n <= 2)         return n;     int pre2 = 1, pre1 = 2;     int result = 1;     for (int i = 2; i < n; i++) {         result = pre2 + pre1;         pre2 = pre1;         pre1 = result;     }     return result; } 10.4 变态跳台阶 NowCoder 题目描述 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 解题思路 动态规划 复制代码 1 2 3 4 5 6 7 8 public int JumpFloorII(int target) {     int[] dp = new int[target];     Arrays.fill(dp, 1);     for (int i = 1; i < target; i++)         for (int j = 0; j < i; j++)             dp[i] += dp[j];     return dp[target - 1]; } 数学推导 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么 复制代码 1 f(n-1) = f(n-2) + f(n-3) + ... + f(0) 同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去... ，那么 复制代码 1 f(n) = f(n-1) + f(n-2) + ... + f(0) 综上可得 复制代码 1 f(n) - f(n-1) = f(n-1) 即 复制代码 1 f(n) = 2*f(n-1) 所以 f(n) 是一个等比数列 复制代码 1 2 3 public int JumpFloorII(int target) {     return (int) Math.pow(2, target - 1); } 11. 旋转数组的最小数字 NowCoder 题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 解题思路 将旋转数组对半分可以得到一个包含最小元素的新旋转数组，以及一个非递减排序的数组。新的旋转数组的数组元素是原数组的一半，从而将问题规模减少了一半，这种折半性质的算法的时间复杂度为 O(logN)（为了方便，这里将 log₂N 写为 logN）。 此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组，哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。 通过修改二分查找算法进行求解（l 代表 low，m 代表 mid，h 代表 high）： 当 nums[m] <= nums[h] 时，表示 [m, h] 区间内的数组是非递减数组，[l, m] 区间内的数组是旋转数组，此时令 h = m； 否则 [m + 1, h] 区间内的数组是旋转数组，令 l = m + 1。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public int minNumberInRotateArray(int[] nums) {     if (nums.length == 0)         return 0;     int l = 0, h = nums.length - 1;     while (l < h) {         int m = l + (h - l) / 2;         if (nums[m] <= nums[h])             h = m;         else             l = m + 1;     }     return nums[l]; } 如果数组元素允许重复，会出现一个特殊的情况：nums[l] == nums[m] == nums[h]，此时无法确定解在哪个区间，需要切换到顺序查找。例如对于数组 {1,1,1,0,1}，l、m 和 h 指向的数都为 1，此时无法知道最小数字 0 在哪个区间。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int minNumberInRotateArray(int[] nums) {     if (nums.length == 0)         return 0;     int l = 0, h = nums.length - 1;     while (l < h) {         int m = l + (h - l) / 2;         if (nums[l] == nums[m] && nums[m] == nums[h])             return minNumber(nums, l, h);         else if (nums[m] <= nums[h])             h = m;         else             l = m + 1;     }     return nums[l]; }   private int minNumber(int[] nums, int l, int h) {     for (int i = l; i < h; i++)         if (nums[i] > nums[i + 1])             return nums[i + 1];     return nums[l]; } 12. 矩阵中的路径 NowCoder 题目描述 判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如下面的矩阵包含了一条 bfce 路径。 解题思路 使用回溯法（backtracking）进行求解，它是一种暴力搜索方法，通过搜索所有可能的结果来求解问题。回溯法在一次搜索结束时需要进行回溯（回退），将这一次搜索过程中设置的状态进行清除，从而开始一次新的搜索过程。例如下图示例中，从 f 开始，下一步有 4 种搜索可能，如果先搜索 b，需要将 b 标记为已经使用，防止重复使用。在这一次搜索结束之后，需要将 b 的已经使用状态清除，并搜索 c。 本题的输入是数组而不是矩阵（二维数组），因此需要先将数组转换成矩阵。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 private final static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; private int rows; private int cols;   public boolean hasPath(char[] array, int rows, int cols, char[] str) {     if (rows == 0 || cols == 0) return false;     this.rows = rows;     this.cols = cols;     boolean[][] marked = new boolean[rows][cols];     char[][] matrix = buildMatrix(array);     for (int i = 0; i < rows; i++)         for (int j = 0; j < cols; j++)             if (backtracking(matrix, str, marked, 0, i, j))                 return true;       return false; }   private boolean backtracking(char[][] matrix, char[] str,                              boolean[][] marked, int pathLen, int r, int c) {       if (pathLen == str.length) return true;     if (r < 0 || r >= rows || c < 0 || c >= cols             || matrix[r][c] != str[pathLen] || marked[r][c]) {           return false;     }     marked[r][c] = true;     for (int[] n : next)         if (backtracking(matrix, str, marked, pathLen + 1, r + n[0], c + n[1]))             return true;     marked[r][c] = false;     return false; }   private char[][] buildMatrix(char[] array) {     char[][] matrix = new char[rows][cols];     for (int r = 0, idx = 0; r < rows; r++)         for (int c = 0; c < cols; c++)             matrix[r][c] = array[idx++];     return matrix; } 13. 机器人的运动范围 NowCoder 题目描述 地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动，每一次只能向左右上下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 例如，当 k 为 18 时，机器人能够进入方格 (35,37)，因为 3+5+3+7=18。但是，它不能进入方格 (35,38)，因为 3+5+3+8=19。请问该机器人能够达到多少个格子？ 解题思路 使用深度优先搜索（Depth First Search，DFS）方法进行求解。回溯是深度优先搜索的一种特例，它在一次搜索过程中需要设置一些本次搜索过程的局部状态，并在本次搜索结束之后清除状态。而普通的深度优先搜索并不需要使用这些局部状态，虽然还是有可能设置一些全局状态。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; private int cnt = 0; private int rows; private int cols; private int threshold; private int[][] digitSum;   public int movingCount(int threshold, int rows, int cols) {     this.rows = rows;     this.cols = cols;     this.threshold = threshold;     initDigitSum();     boolean[][] marked = new boolean[rows][cols];     dfs(marked, 0, 0);     return cnt; }   private void dfs(boolean[][] marked, int r, int c) {     if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c])         return;     marked[r][c] = true;     if (this.digitSum[r][c] > this.threshold)         return;     cnt++;     for (int[] n : next)         dfs(marked, r + n[0], c + n[1]); }   private void initDigitSum() {     int[] digitSumOne = new int[Math.max(rows, cols)];     for (int i = 0; i < digitSumOne.length; i++) {         int n = i;         while (n > 0) {             digitSumOne[i] += n % 10;             n /= 10;         }     }     this.digitSum = new int[rows][cols];     for (int i = 0; i < this.rows; i++)         for (int j = 0; j < this.cols; j++)             this.digitSum[i][j] = digitSumOne[i] + digitSumOne[j]; } 14. 剪绳子 Leetcode 题目描述 把一根绳子剪成多段，并且使得每段的长度乘积最大。 复制代码 1 2 3 4 5 n = 2 return 1 (2 = 1 + 1)   n = 10 return 36 (10 = 3 + 3 + 4) 解题思路 贪心 尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。 证明：当 n >= 5 时，3(n - 3) - n = 2n - 9 > 0，且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下，将绳子剪成一段为 2 或者 3，得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0，所以剪成一段长度为 3 比长度为 2 得到的乘积更大。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public int integerBreak(int n) {     if (n < 2)         return 0;     if (n == 2)         return 1;     if (n == 3)         return 2;     int timesOf3 = n / 3;     if (n - timesOf3 * 3 == 1)         timesOf3--;     int timesOf2 = (n - timesOf3 * 3) / 2;     return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2)); } 动态规划 复制代码 1 2 3 4 5 6 7 8 public int integerBreak(int n) {     int[] dp = new int[n + 1];     dp[1] = 1;     for (int i = 2; i <= n; i++)         for (int j = 1; j < i; j++)             dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));     return dp[n]; } 15. 二进制中 1 的个数 NowCoder 题目描述 输入一个整数，输出该数二进制表示中 1 的个数。 n&(n-1) 该位运算去除 n 的位级表示中最低的那一位。 复制代码 1 2 3 n       : 10110100 n-1     : 10110011 n&(n-1) : 10110000 时间复杂度：O(M)，其中 M 表示 1 的个数。 复制代码 1 2 3 4 5 6 7 8 public int NumberOf1(int n) {     int cnt = 0;     while (n != 0) {         cnt++;         n &= (n - 1);     }     return cnt; } Integer.bitCount() 复制代码 1 2 3 public int NumberOf1(int n) {     return Integer.bitCount(n); } 16. 数值的整数次方 NowCoder 题目描述 给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent，求 base 的 exponent 次方。 解题思路 下面的讨论中 x 代表 base，n 代表 exponent。 x^n=\left\{\begin{array}{rcl}(x*x)^{n/2}&&{n\%2=0}\\x*(x*x)^{n/2}&&{n\%2=1}\end{array}\right. x n ={ (x∗x) n/2 x∗(x∗x) n/2 ​ ​ n%2=0 n%2=1 ​ 因为 (x*x)^n/2 可以通过递归求解，并且每次递归 n 都减小一半，因此整个算法的时间复杂度为 O(logN)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public double Power(double base, int exponent) {     if (exponent == 0)         return 1;     if (exponent == 1)         return base;     boolean isNegative = false;     if (exponent < 0) {         exponent = -exponent;         isNegative = true;     }     double pow = Power(base * base, exponent / 2);     if (exponent % 2 != 0)         pow = pow * base;     return isNegative ? 1 / pow : pow; } 17. 打印从 1 到最大的 n 位数 题目描述 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。 解题思路 由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 char 数组进行存储。 使用回溯法得到所有的数。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public void print1ToMaxOfNDigits(int n) {     if (n <= 0)         return;     char[] number = new char[n];     print1ToMaxOfNDigits(number, 0); }   private void print1ToMaxOfNDigits(char[] number, int digit) {     if (digit == number.length) {         printNumber(number);         return;     }     for (int i = 0; i < 10; i++) {         number[digit] = (char) (i + '0');         print1ToMaxOfNDigits(number, digit + 1);     } }   private void printNumber(char[] number) {     int index = 0;     while (index < number.length && number[index] == '0')         index++;     while (index < number.length)         System.out.print(number[index++]);     System.out.println(); } 18.1 在 O(1) 时间内删除链表节点 解题思路 ① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。 ② 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。 综上，如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public ListNode deleteNode(ListNode head, ListNode tobeDelete) {     if (head == null || tobeDelete == null)         return null;     if (tobeDelete.next != null) {         // 要删除的节点不是尾节点         ListNode next = tobeDelete.next;         tobeDelete.val = next.val;         tobeDelete.next = next.next;     } else {         if (head == tobeDelete)              // 只有一个节点             head = null;         else {             ListNode cur = head;             while (cur.next != tobeDelete)                 cur = cur.next;             cur.next = null;         }     }     return head; } 18.2 删除链表中重复的结点 NowCoder 题目描述 解题描述 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public ListNode deleteDuplication(ListNode pHead) {     if (pHead == null || pHead.next == null)         return pHead;     ListNode next = pHead.next;     if (pHead.val == next.val) {         while (next != null && pHead.val == next.val)             next = next.next;         return deleteDuplication(next);     } else {         pHead.next = deleteDuplication(pHead.next);         return pHead;     } } 19. 正则表达式匹配 NowCoder 题目描述 请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而 '*' 表示它前面的字符可以出现任意次（包含 0 次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，但是与 "aa.a" 和 "ab*a" 均不匹配。 解题思路 应该注意到，'.' 是用来当做一个任意字符，而 '*' 是用来重复前面的字符。这两个的作用不同，不能把 '.' 的作用和 '*' 进行类比，从而把它当成重复前面字符一次。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public boolean match(char[] str, char[] pattern) {       int m = str.length, n = pattern.length;     boolean[][] dp = new boolean[m + 1][n + 1];       dp[0][0] = true;     for (int i = 1; i <= n; i++)         if (pattern[i - 1] == '*')             dp[0][i] = dp[0][i - 2];       for (int i = 1; i <= m; i++)         for (int j = 1; j <= n; j++)             if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')                 dp[i][j] = dp[i - 1][j - 1];             else if (pattern[j - 1] == '*')                 if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {                     dp[i][j] |= dp[i][j - 1]; // a* counts as single a                     dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a                     dp[i][j] |= dp[i][j - 2]; // a* counts as empty                 } else                     dp[i][j] = dp[i][j - 2];   // a* only counts as empty       return dp[m][n]; } 20. 表示数值的字符串 NowCoder 题目描述 复制代码 1 2 3 4 5 6 7 true   "+100" "5e2" "-123" "3.1416" "-1E-16" 复制代码 1 2 3 4 5 6 7 false   "12e" "1a3.14" "1.2.3" "+-5" "12e+4.3" 解题思路 使用正则表达式进行匹配。 复制代码 1 2 3 4 5 6 7 8 []  ： 字符集合 ()  ： 分组 ?   ： 重复 0 ~ 1 次 +   ： 重复 1 ~ n 次 *   ： 重复 0 ~ n 次 .   ： 任意字符 \\. ： 转义后的 . \\d ： 数字 复制代码 1 2 3 4 5 public boolean isNumeric(char[] str) {     if (str == null || str.length == 0)         return false;     return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?"); } 21. 调整数组顺序使奇数位于偶数前面 NowCoder 题目描述 需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。 解题思路 方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public void reOrderArray(int[] nums) {     // 奇数个数     int oddCnt = 0;     for (int x : nums)         if (!isEven(x))             oddCnt++;     int[] copy = nums.clone();     int i = 0, j = oddCnt;     for (int num : copy) {         if (num % 2 == 1)             nums[i++] = num;         else             nums[j++] = num;     } }   private boolean isEven(int x) {     return x % 2 == 0; } 方法二：使用冒泡思想，每次都当前偶数上浮到当前最右边。时间复杂度 O(N²)，空间复杂度 O(1)，时间换空间。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public void reOrderArray(int[] nums) {     int N = nums.length;     for (int i = N - 1; i > 0; i--) {         for (int j = 0; j < i; j++) {             if (isEven(nums[j]) && !isEven(nums[j + 1])) {                 swap(nums, j, j + 1);             }         }     } }   private boolean isEven(int x) {     return x % 2 == 0; }   private void swap(int[] nums, int i, int j) {     int t = nums[i];     nums[i] = nums[j];     nums[j] = t; } 22. 链表中倒数第 K 个结点 NowCoder 解题思路 设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public ListNode FindKthToTail(ListNode head, int k) {     if (head == null)         return null;     ListNode P1 = head;     while (P1 != null && k-- > 0)         P1 = P1.next;     if (k > 0)         return null;     ListNode P2 = head;     while (P1 != null) {         P1 = P1.next;         P2 = P2.next;     }     return P2; } 23. 链表中环的入口结点 NowCoder 题目描述 一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。 解题思路 使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。假设相遇点在下图的 z1 位置，此时 fast 移动的节点数为 x+2y+z，slow 为 x+y，由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。 在相遇点，slow 要到环的入口点还需要移动 z 个节点，如果让 fast 重新从头开始移动，并且速度变为每次移动一个节点，那么它到环入口点还需要移动 x 个节点。在上面已经推导出 x=z，因此 fast 和 slow 将在环入口点相遇。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public ListNode EntryNodeOfLoop(ListNode pHead) {     if (pHead == null || pHead.next == null)         return null;     ListNode slow = pHead, fast = pHead;     do {         fast = fast.next.next;         slow = slow.next;     } while (slow != fast);     fast = pHead;     while (slow != fast) {         slow = slow.next;         fast = fast.next;     }     return slow; } 24. 反转链表 NowCoder 解题思路 递归 复制代码 1 2 3 4 5 6 7 8 9 public ListNode ReverseList(ListNode head) {     if (head == null || head.next == null)         return head;     ListNode next = head.next;     head.next = null;     ListNode newHead = ReverseList(next);     next.next = head;     return newHead; } 迭代 使用头插法。 复制代码 1 2 3 4 5 6 7 8 9 10 public ListNode ReverseList(ListNode head) {     ListNode newList = new ListNode(-1);     while (head != null) {         ListNode next = head.next;         head.next = newList.next;         newList.next = head;         head = next;     }     return newList.next; } 25. 合并两个排序的链表 NowCoder 题目描述 解题思路 递归 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public ListNode Merge(ListNode list1, ListNode list2) {     if (list1 == null)         return list2;     if (list2 == null)         return list1;     if (list1.val <= list2.val) {         list1.next = Merge(list1.next, list2);         return list1;     } else {         list2.next = Merge(list1, list2.next);         return list2;     } } 迭代 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public ListNode Merge(ListNode list1, ListNode list2) {     ListNode head = new ListNode(-1);     ListNode cur = head;     while (list1 != null && list2 != null) {         if (list1.val <= list2.val) {             cur.next = list1;             list1 = list1.next;         } else {             cur.next = list2;             list2 = list2.next;         }         cur = cur.next;     }     if (list1 != null)         cur.next = list1;     if (list2 != null)         cur.next = list2;     return head.next; } 26. 树的子结构 NowCoder 题目描述 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean HasSubtree(TreeNode root1, TreeNode root2) {     if (root1 == null || root2 == null)         return false;     return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); }   private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {     if (root2 == null)         return true;     if (root1 == null)         return false;     if (root1.val != root2.val)         return false;     return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right); } 27. 二叉树的镜像 NowCoder 题目描述 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public void Mirror(TreeNode root) {     if (root == null)         return;     swap(root);     Mirror(root.left);     Mirror(root.right); }   private void swap(TreeNode root) {     TreeNode t = root.left;     root.left = root.right;     root.right = t; } 28 对称的二叉树 NowCoder 题目描述 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 boolean isSymmetrical(TreeNode pRoot) {     if (pRoot == null)         return true;     return isSymmetrical(pRoot.left, pRoot.right); }   boolean isSymmetrical(TreeNode t1, TreeNode t2) {     if (t1 == null && t2 == null)         return true;     if (t1 == null || t2 == null)         return false;     if (t1.val != t2.val)         return false;     return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left); } 29. 顺时针打印矩阵 NowCoder 题目描述 下图的矩阵顺时针打印结果为：1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public ArrayList<Integer> printMatrix(int[][] matrix) {     ArrayList<Integer> ret = new ArrayList<>();     int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;     while (r1 <= r2 && c1 <= c2) {         for (int i = c1; i <= c2; i++)             ret.add(matrix[r1][i]);         for (int i = r1 + 1; i <= r2; i++)             ret.add(matrix[i][c2]);         if (r1 != r2)             for (int i = c2 - 1; i >= c1; i--)                 ret.add(matrix[r2][i]);         if (c1 != c2)             for (int i = r2 - 1; i > r1; i--)                 ret.add(matrix[i][c1]);         r1++; r2--; c1++; c2--;     }     return ret; } 30. 包含 min 函数的栈 NowCoder 题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的 min 函数。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private Stack<Integer> dataStack = new Stack<>(); private Stack<Integer> minStack = new Stack<>();   public void push(int node) {     dataStack.push(node);     minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node)); }   public void pop() {     dataStack.pop();     minStack.pop(); }   public int top() {     return dataStack.peek(); }   public int min() {     return minStack.peek(); } 31. 栈的压入、弹出序列 NowCoder 题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。 例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。 解题思路 使用一个栈来模拟压入弹出操作。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {     int n = pushSequence.length;     Stack<Integer> stack = new Stack<>();     for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {         stack.push(pushSequence[pushIndex]);         while (popIndex < n && !stack.isEmpty()                 && stack.peek() == popSequence[popIndex]) {             stack.pop();             popIndex++;         }     }     return stack.isEmpty(); } 32.1 从上往下打印二叉树 NowCoder 题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 例如，以下二叉树层次遍历的结果为：1,2,3,4,5,6,7 解题思路 使用队列来进行层次遍历。 不需要使用两个队列分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {     Queue<TreeNode> queue = new LinkedList<>();     ArrayList<Integer> ret = new ArrayList<>();     queue.add(root);     while (!queue.isEmpty()) {         int cnt = queue.size();         while (cnt-- > 0) {             TreeNode t = queue.poll();             if (t == null)                 continue;             ret.add(t.val);             queue.add(t.left);             queue.add(t.right);         }     }     return ret; } 32.2 把二叉树打印成多行 NowCoder 题目描述 和上题几乎一样。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {     ArrayList<ArrayList<Integer>> ret = new ArrayList<>();     Queue<TreeNode> queue = new LinkedList<>();     queue.add(pRoot);     while (!queue.isEmpty()) {         ArrayList<Integer> list = new ArrayList<>();         int cnt = queue.size();         while (cnt-- > 0) {             TreeNode node = queue.poll();             if (node == null)                 continue;             list.add(node.val);             queue.add(node.left);             queue.add(node.right);         }         if (list.size() != 0)             ret.add(list);     }     return ret; } 32.3 按之字形顺序打印二叉树 NowCoder 题目描述 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {     ArrayList<ArrayList<Integer>> ret = new ArrayList<>();     Queue<TreeNode> queue = new LinkedList<>();     queue.add(pRoot);     boolean reverse = false;     while (!queue.isEmpty()) {         ArrayList<Integer> list = new ArrayList<>();         int cnt = queue.size();         while (cnt-- > 0) {             TreeNode node = queue.poll();             if (node == null)                 continue;             list.add(node.val);             queue.add(node.left);             queue.add(node.right);         }         if (reverse)             Collections.reverse(list);         reverse = !reverse;         if (list.size() != 0)             ret.add(list);     }     return ret; } 33. 二叉搜索树的后序遍历序列 NowCoder 题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。 例如，下图是后序遍历序列 1,3,2 所对应的二叉搜索树。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public boolean VerifySquenceOfBST(int[] sequence) {     if (sequence == null || sequence.length == 0)         return false;     return verify(sequence, 0, sequence.length - 1); }   private boolean verify(int[] sequence, int first, int last) {     if (last - first <= 1)         return true;     int rootVal = sequence[last];     int cutIndex = first;     while (cutIndex < last && sequence[cutIndex] <= rootVal)         cutIndex++;     for (int i = cutIndex; i < last; i++)         if (sequence[i] < rootVal)             return false;     return verify(sequence, first, cutIndex - 1) && verify(sequence, cutIndex, last - 1); } 34. 二叉树中和为某一值的路径 NowCoder 题目描述 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 下图的二叉树有两条和为 22 的路径：10, 5, 7 和 10, 12 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();   public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {     backtracking(root, target, new ArrayList<>());     return ret; }   private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {     if (node == null)         return;     path.add(node.val);     target -= node.val;     if (target == 0 && node.left == null && node.right == null) {         ret.add(new ArrayList<>(path));     } else {         backtracking(node.left, target, path);         backtracking(node.right, target, path);     }     path.remove(path.size() - 1); } 35. 复杂链表的复制 NowCoder 题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。 复制代码 1 2 3 4 5 6 7 8 9 public class RandomListNode {     int label;     RandomListNode next = null;     RandomListNode random = null;       RandomListNode(int label) {         this.label = label;     } } 解题思路 第一步，在每个节点的后面插入复制的节点。 第二步，对复制节点的 random 链接进行赋值。 第三步，拆分。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public RandomListNode Clone(RandomListNode pHead) {     if (pHead == null)         return null;     // 插入新节点     RandomListNode cur = pHead;     while (cur != null) {         RandomListNode clone = new RandomListNode(cur.label);         clone.next = cur.next;         cur.next = clone;         cur = clone.next;     }     // 建立 random 链接     cur = pHead;     while (cur != null) {         RandomListNode clone = cur.next;         if (cur.random != null)             clone.random = cur.random.next;         cur = clone.next;     }     // 拆分     cur = pHead;     RandomListNode pCloneHead = pHead.next;     while (cur.next != null) {         RandomListNode next = cur.next;         cur.next = next.next;         cur = next;     }     return pCloneHead; } 36. 二叉搜索树与双向链表 NowCoder 题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private TreeNode pre = null; private TreeNode head = null;   public TreeNode Convert(TreeNode root) {     inOrder(root);     return head; }   private void inOrder(TreeNode node) {     if (node == null)         return;     inOrder(node.left);     node.left = pre;     if (pre != null)         pre.right = node;     pre = node;     if (head == null)         head = node;     inOrder(node.right); } 37. 序列化二叉树 NowCoder 题目描述 请实现两个函数，分别用来序列化和反序列化二叉树。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 private String deserializeStr;   public String Serialize(TreeNode root) {     if (root == null)         return "#";     return root.val + " " + Serialize(root.left) + " " + Serialize(root.right); }   public TreeNode Deserialize(String str) {     deserializeStr = str;     return Deserialize(); }   private TreeNode Deserialize() {     if (deserializeStr.length() == 0)         return null;     int index = deserializeStr.indexOf(" ");     String node = index == -1 ? deserializeStr : deserializeStr.substring(0, index);     deserializeStr = index == -1 ? "" : deserializeStr.substring(index + 1);     if (node.equals("#"))         return null;     int val = Integer.valueOf(node);     TreeNode t = new TreeNode(val);     t.left = Deserialize();     t.right = Deserialize();     return t; } 38. 字符串的排列 NowCoder 题目描述 输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 private ArrayList<String> ret = new ArrayList<>();   public ArrayList<String> Permutation(String str) {     if (str.length() == 0)         return ret;     char[] chars = str.toCharArray();     Arrays.sort(chars);     backtracking(chars, new boolean[chars.length], new StringBuilder());     return ret; }   private void backtracking(char[] chars, boolean[] hasUsed, StringBuilder s) {     if (s.length() == chars.length) {         ret.add(s.toString());         return;     }     for (int i = 0; i < chars.length; i++) {         if (hasUsed[i])             continue;         if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1]) /* 保证不重复 */             continue;         hasUsed[i] = true;         s.append(chars[i]);         backtracking(chars, hasUsed, s);         s.deleteCharAt(s.length() - 1);         hasUsed[i] = false;     } } 39. 数组中出现次数超过一半的数字 NowCoder 解题思路 多数投票问题，可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 O(N)。 使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素相等时，令 cnt++，否则令 cnt--。如果前面查找了 i 个元素，且 cnt == 0，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int MoreThanHalfNum_Solution(int[] nums) {     int majority = nums[0];     for (int i = 1, cnt = 1; i < nums.length; i++) {         cnt = nums[i] == majority ? cnt + 1 : cnt - 1;         if (cnt == 0) {             majority = nums[i];             cnt = 1;         }     }     int cnt = 0;     for (int val : nums)         if (val == majority)             cnt++;     return cnt > nums.length / 2 ? majority : 0; } 40. 最小的 K 个数 NowCoder 解题思路 快速选择 复杂度：O(N) + O(1) 只有当允许修改数组元素时才可以使用 快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素，这种找第 K 个元素的算法称为快速选择算法。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {     ArrayList<Integer> ret = new ArrayList<>();     if (k > nums.length || k <= 0)         return ret;     findKthSmallest(nums, k - 1);     /* findKthSmallest 会改变数组，使得前 k 个数都是最小的 k 个数 */     for (int i = 0; i < k; i++)         ret.add(nums[i]);     return ret; }   public void findKthSmallest(int[] nums, int k) {     int l = 0, h = nums.length - 1;     while (l < h) {         int j = partition(nums, l, h);         if (j == k)             break;         if (j > k)             h = j - 1;         else             l = j + 1;     } }   private int partition(int[] nums, int l, int h) {     int p = nums[l];     /* 切分元素 */     int i = l, j = h + 1;     while (true) {         while (i != h && nums[++i] < p) ;         while (j != l && nums[--j] > p) ;         if (i >= j)             break;         swap(nums, i, j);     }     swap(nums, l, j);     return j; }   private void swap(int[] nums, int i, int j) {     int t = nums[i];     nums[i] = nums[j];     nums[j] = t; } 大小为 K 的最小堆 复杂度：O(NlogK) + O(K) 特别适合处理海量数据 应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。 维护一个大小为 K 的最小堆过程如下：在添加一个元素之后，如果大顶堆的大小大于 K，那么需要将大顶堆的堆顶元素去除。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {     if (k > nums.length || k <= 0)         return new ArrayList<>();     PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);     for (int num : nums) {         maxHeap.add(num);         if (maxHeap.size() > k)             maxHeap.poll();     }     return new ArrayList<>(maxHeap); } 41.1 数据流中的中位数 NowCoder 题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 /* 大顶堆，存储左半边元素 */ private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1); /* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */ private PriorityQueue<Integer> right = new PriorityQueue<>(); /* 当前数据流读入的元素个数 */ private int N = 0;   public void Insert(Integer val) {     /* 插入要保证两个堆存于平衡状态 */     if (N % 2 == 0) {         /* N 为偶数的情况下插入到右半边。          * 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，          * 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */         left.add(val);         right.add(left.poll());     } else {         right.add(val);         left.add(right.poll());     }     N++; }   public Double GetMedian() {     if (N % 2 == 0)         return (left.peek() + right.peek()) / 2.0;     else         return (double) right.peek(); } 41.2 字符流中第一个不重复的字符 NowCoder 题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时，第一个只出现一次的字符是 "l"。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 private int[] cnts = new int[256]; private Queue<Character> queue = new LinkedList<>();   public void Insert(char ch) {     cnts[ch]++;     queue.add(ch);     while (!queue.isEmpty() && cnts[queue.peek()] > 1)         queue.poll(); }   public char FirstAppearingOnce() {     return queue.isEmpty() ? '#' : queue.peek(); } 42. 连续子数组的最大和 NowCoder 题目描述 {6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 public int FindGreatestSumOfSubArray(int[] nums) {     if (nums == null || nums.length == 0)         return 0;     int greatestSum = Integer.MIN_VALUE;     int sum = 0;     for (int val : nums) {         sum = sum <= 0 ? val : sum + val;         greatestSum = Math.max(greatestSum, sum);     }     return greatestSum; } 43. 从 1 到 n 整数中 1 出现的次数 NowCoder 解题思路 复制代码 1 2 3 4 5 6 7 8 public int NumberOf1Between1AndN_Solution(int n) {     int cnt = 0;     for (int m = 1; m <= n; m *= 10) {         int a = n / m, b = n % m;         cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);     }     return cnt; } Leetcode : 233. Number of Digit One 44. 数字序列中的某一位数字 题目描述 数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 public int getDigitAtIndex(int index) {     if (index < 0)         return -1;     int place = 1;  // 1 表示个位，2 表示 十位...     while (true) {         int amount = getAmountOfPlace(place);         int totalAmount = amount * place;         if (index < totalAmount)             return getDigitAtIndex(index, place);         index -= totalAmount;         place++;     } }   /**  * place 位数的数字组成的字符串长度  * 10, 90, 900, ...  */ private int getAmountOfPlace(int place) {     if (place == 1)         return 10;     return (int) Math.pow(10, place - 1) * 9; }   /**  * place 位数的起始数字  * 0, 10, 100, ...  */ private int getBeginNumberOfPlace(int place) {     if (place == 1)         return 0;     return (int) Math.pow(10, place - 1); }   /**  * 在 place 位数组成的字符串中，第 index 个数  */ private int getDigitAtIndex(int index, int place) {     int beginNumber = getBeginNumberOfPlace(place);     int shiftNumber = index / place;     String number = (beginNumber + shiftNumber) + "";     int count = index % place;     return number.charAt(count) - '0'; } 45. 把数组排成最小的数 NowCoder 题目描述 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 {3，32，321}，则打印出这三个数字能排成的最小数字为 321323。 解题思路 可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public String PrintMinNumber(int[] numbers) {     if (numbers == null || numbers.length == 0)         return "";     int n = numbers.length;     String[] nums = new String[n];     for (int i = 0; i < n; i++)         nums[i] = numbers[i] + "";     Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));     String ret = "";     for (String str : nums)         ret += str;     return ret; } 46. 把数字翻译成字符串 Leetcode 题目描述 给定一个数字，按照如下规则翻译成字符串：1 翻译成“a”，2 翻译成“b”... 26 翻译成“z”。一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 abbeh，lbeh，aveh，abyh，lyh。实现一个函数，用来计算一个数字有多少种不同的翻译方法。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int numDecodings(String s) {     if (s == null || s.length() == 0)         return 0;     int n = s.length();     int[] dp = new int[n + 1];     dp[0] = 1;     dp[1] = s.charAt(0) == '0' ? 0 : 1;     for (int i = 2; i <= n; i++) {         int one = Integer.valueOf(s.substring(i - 1, i));         if (one != 0)             dp[i] += dp[i - 1];         if (s.charAt(i - 2) == '0')             continue;         int two = Integer.valueOf(s.substring(i - 2, i));         if (two <= 26)             dp[i] += dp[i - 2];     }     return dp[n]; } 47. 礼物的最大价值 NowCoder 题目描述 在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘 复制代码 1 2 3 4 1    10   3    8 12   2    9    6 5    7    4    11 3    7    16   5 礼物的最大价值为 1+12+5+7+7+16+5=53。 解题思路 应该用动态规划求解，而不是深度优先搜索，深度优先搜索过于复杂，不是最优解。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public int getMost(int[][] values) {     if (values == null || values.length == 0 || values[0].length == 0)         return 0;     int n = values[0].length;     int[] dp = new int[n];     for (int[] value : values) {         dp[0] += value[0];         for (int i = 1; i < n; i++)             dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];     }     return dp[n - 1]; } 48. 最长不含重复字符的子字符串 题目描述 输入一个字符串（只包含 a~z 的字符），求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int longestSubStringWithoutDuplication(String str) {     int curLen = 0;     int maxLen = 0;     int[] preIndexs = new int[26];     Arrays.fill(preIndexs, -1);     for (int curI = 0; curI < str.length(); curI++) {         int c = str.charAt(curI) - 'a';         int preI = preIndexs[c];         if (preI == -1 || curI - preI > curLen) {             curLen++;         } else {             maxLen = Math.max(maxLen, curLen);             curLen = curI - preI;         }         preIndexs[c] = curI;     }     maxLen = Math.max(maxLen, curLen);     return maxLen; } 49. 丑数 NowCoder 题目描述 把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public int GetUglyNumber_Solution(int N) {     if (N <= 6)         return N;     int i2 = 0, i3 = 0, i5 = 0;     int[] dp = new int[N];     dp[0] = 1;     for (int i = 1; i < N; i++) {         int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;         dp[i] = Math.min(next2, Math.min(next3, next5));         if (dp[i] == next2)             i2++;         if (dp[i] == next3)             i3++;         if (dp[i] == next5)             i5++;     }     return dp[N - 1]; } 50. 第一个只出现一次的字符位置 NowCoder 题目描述 在一个字符串中找到第一个只出现一次的字符，并返回它的位置。 复制代码 1 2 Input: abacc Output: b 解题思路 最直观的解法是使用 HashMap 对出现次数进行统计，但是考虑到要统计的字符范围有限，因此可以使用整型数组代替 HashMap，从而将空间复杂度由 O(N) 降低为 O(1)。 复制代码 1 2 3 4 5 6 7 8 9 public int FirstNotRepeatingChar(String str) {     int[] cnts = new int[256];     for (int i = 0; i < str.length(); i++)         cnts[str.charAt(i)]++;     for (int i = 0; i < str.length(); i++)         if (cnts[str.charAt(i)] == 1)             return i;     return -1; } 以上实现的空间复杂度还不是最优的。考虑到只需要找到只出现一次的字符，那么需要统计的次数信息只有 0,1,更大，使用两个比特位就能存储这些信息。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int FirstNotRepeatingChar2(String str) {     BitSet bs1 = new BitSet(256);     BitSet bs2 = new BitSet(256);     for (char c : str.toCharArray()) {         if (!bs1.get(c) && !bs2.get(c))             bs1.set(c);     // 0 0 -> 0 1         else if (bs1.get(c) && !bs2.get(c))             bs2.set(c);     // 0 1 -> 1 1     }     for (int i = 0; i < str.length(); i++) {         char c = str.charAt(i);         if (bs1.get(c) && !bs2.get(c))  // 0 1             return i;     }     return -1; } 51. 数组中的逆序对 NowCoder 题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 private long cnt = 0; private int[] tmp;  // 在这里声明辅助数组，而不是在 merge() 递归函数中声明   public int InversePairs(int[] nums) {     tmp = new int[nums.length];     mergeSort(nums, 0, nums.length - 1);     return (int) (cnt % 1000000007); }   private void mergeSort(int[] nums, int l, int h) {     if (h - l < 1)         return;     int m = l + (h - l) / 2;     mergeSort(nums, l, m);     mergeSort(nums, m + 1, h);     merge(nums, l, m, h); }   private void merge(int[] nums, int l, int m, int h) {     int i = l, j = m + 1, k = l;     while (i <= m || j <= h) {         if (i > m)             tmp[k] = nums[j++];         else if (j > h)             tmp[k] = nums[i++];         else if (nums[i] <= nums[j])             tmp[k] = nums[i++];         else {             tmp[k] = nums[j++];             this.cnt += m - i + 1;  // nums[i] > nums[j]，说明 nums[i...mid] 都大于 nums[j]         }         k++;     }     for (k = l; k <= h; k++)         nums[k] = tmp[k]; } 52. 两个链表的第一个公共结点 NowCoder 题目描述 解题思路 设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。 当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。 复制代码 1 2 3 4 5 6 7 8 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {     ListNode l1 = pHead1, l2 = pHead2;     while (l1 != l2) {         l1 = (l1 == null) ? pHead2 : l1.next;         l2 = (l2 == null) ? pHead1 : l2.next;     }     return l1; } 53. 数字在排序数组中出现的次数 NowCoder 题目描述 复制代码 1 2 3 4 5 6 Input: nums = 1, 2, 3, 3, 3, 3, 4, 6 K = 3   Output: 4 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int GetNumberOfK(int[] nums, int K) {     int first = binarySearch(nums, K);     int last = binarySearch(nums, K + 1);     return (first == nums.length || nums[first] != K) ? 0 : last - first; }   private int binarySearch(int[] nums, int K) {     int l = 0, h = nums.length;     while (l < h) {         int m = l + (h - l) / 2;         if (nums[m] >= K)             h = m;         else             l = m + 1;     }     return l; } 54. 二叉查找树的第 K 个结点 NowCoder 解题思路 利用二叉查找树中序遍历有序的特点。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 private TreeNode ret; private int cnt = 0;   public TreeNode KthNode(TreeNode pRoot, int k) {     inOrder(pRoot, k);     return ret; }   private void inOrder(TreeNode root, int k) {     if (root == null || cnt >= k)         return;     inOrder(root.left, k);     cnt++;     if (cnt == k)         ret = root;     inOrder(root.right, k); } 55.1 二叉树的深度 NowCoder 题目描述 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 解题思路 复制代码 1 2 3 public int TreeDepth(TreeNode root) {     return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right)); } 55.2 平衡二叉树 NowCoder 题目描述 平衡二叉树左右子树高度差不超过 1。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 private boolean isBalanced = true;   public boolean IsBalanced_Solution(TreeNode root) {     height(root);     return isBalanced; }   private int height(TreeNode root) {     if (root == null || !isBalanced)         return 0;     int left = height(root.left);     int right = height(root.right);     if (Math.abs(left - right) > 1)         isBalanced = false;     return 1 + Math.max(left, right); } 56. 数组中只出现一次的数字 NowCoder 题目描述 一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。 解题思路 两个不相等的元素在位级表示上必定会有一位存在不同，将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。 diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 public void FindNumsAppearOnce(int[] nums, int num1[], int num2[]) {     int diff = 0;     for (int num : nums)         diff ^= num;     diff &= -diff;     for (int num : nums) {         if ((num & diff) == 0)             num1[0] ^= num;         else             num2[0] ^= num;     } } 57.1 和为 S 的两个数字 NowCoder 题目描述 输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是 S。如果有多对数字的和等于 S，输出两个数的乘积最小的。 解题思路 使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。 如果两个指针指向元素的和 sum == target，那么得到要求的结果； 如果 sum > target，移动较大的元素，使 sum 变小一些； 如果 sum < target，移动较小的元素，使 sum 变大一些。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {     int i = 0, j = array.length - 1;     while (i < j) {         int cur = array[i] + array[j];         if (cur == sum)             return new ArrayList<>(Arrays.asList(array[i], array[j]));         if (cur < sum)             i++;         else             j--;     }     return new ArrayList<>(); } 57.2 和为 S 的连续正数序列 NowCoder 题目描述 输出所有和为 S 的连续正数序列。 例如和为 100 的连续序列有： 复制代码 1 2 [9, 10, 11, 12, 13, 14, 15, 16] [18, 19, 20, 21, 22]。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {     ArrayList<ArrayList<Integer>> ret = new ArrayList<>();     int start = 1, end = 2;     int curSum = 3;     while (end < sum) {         if (curSum > sum) {             curSum -= start;             start++;         } else if (curSum < sum) {             end++;             curSum += end;         } else {             ArrayList<Integer> list = new ArrayList<>();             for (int i = start; i <= end; i++)                 list.add(i);             ret.add(list);             curSum -= start;             start++;             end++;             curSum += end;         }     }     return ret; } 58.1 翻转单词顺序列 NowCoder 题目描述 复制代码 1 2 3 4 5 Input: "I am a student."   Output: "student. a am I" 解题思路 题目应该有一个隐含条件，就是不能用额外的空间。虽然 Java 的题目输入参数为 String 类型，需要先创建一个字符数组使得空间复杂度为 O(N)，但是正确的参数类型应该和原书一样，为字符数组，并且只能使用该字符数组的空间。任何使用了额外空间的解法在面试时都会大打折扣，包括递归解法。 正确的解法应该是和书上一样，先旋转每个单词，再旋转整个字符串。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public String ReverseSentence(String str) {     int n = str.length();     char[] chars = str.toCharArray();     int i = 0, j = 0;     while (j <= n) {         if (j == n || chars[j] == ' ') {             reverse(chars, i, j - 1);             i = j + 1;         }         j++;     }     reverse(chars, 0, n - 1);     return new String(chars); }   private void reverse(char[] c, int i, int j) {     while (i < j)         swap(c, i++, j--); }   private void swap(char[] c, int i, int j) {     char t = c[i];     c[i] = c[j];     c[j] = t; } 58.2 左旋转字符串 NowCoder 题目描述 复制代码 1 2 3 4 5 6 Input: S="abcXYZdef" K=3   Output: "XYZdefabc" 解题思路 先将 "abc" 和 "XYZdef" 分别翻转，得到 "cbafedZYX"，然后再把整个字符串翻转得到 "XYZdefabc"。 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public String LeftRotateString(String str, int n) {     if (n >= str.length())         return str;     char[] chars = str.toCharArray();     reverse(chars, 0, n - 1);     reverse(chars, n, chars.length - 1);     reverse(chars, 0, chars.length - 1);     return new String(chars); }   private void reverse(char[] chars, int i, int j) {     while (i < j)         swap(chars, i++, j--); }   private void swap(char[] chars, int i, int j) {     char t = chars[i];     chars[i] = chars[j];     chars[j] = t; } 59. 滑动窗口的最大值 NowCoder 题目描述 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。 例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public ArrayList<Integer> maxInWindows(int[] num, int size) {     ArrayList<Integer> ret = new ArrayList<>();     if (size > num.length || size < 1)         return ret;     PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);  /* 大顶堆 */     for (int i = 0; i < size; i++)         heap.add(num[i]);     ret.add(heap.peek());     for (int i = 0, j = i + size; j < num.length; i++, j++) {            /* 维护一个大小为 size 的大顶堆 */         heap.remove(num[i]);         heap.add(num[j]);         ret.add(heap.peek());     }     return ret; } 60. n 个骰子的点数 Lintcode 题目描述 把 n 个骰子仍在地上，求点数和为 s 的概率。 解题思路 动态规划 使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。 空间复杂度：O(N²) 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public List<Map.Entry<Integer, Double>> dicesSum(int n) {     final int face = 6;     final int pointNum = face * n;     long[][] dp = new long[n + 1][pointNum + 1];       for (int i = 1; i <= face; i++)         dp[1][i] = 1;       for (int i = 2; i <= n; i++)         for (int j = i; j <= pointNum; j++)     /* 使用 i 个骰子最小点数为 i */             for (int k = 1; k <= face && k <= j; k++)                 dp[i][j] += dp[i - 1][j - k];       final double totalNum = Math.pow(6, n);     List<Map.Entry<Integer, Double>> ret = new ArrayList<>();     for (int i = n; i <= pointNum; i++)         ret.add(new AbstractMap.SimpleEntry<>(i, dp[n][i] / totalNum));       return ret; } 动态规划 + 旋转数组 空间复杂度：O(N) 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public List<Map.Entry<Integer, Double>> dicesSum(int n) {     final int face = 6;     final int pointNum = face * n;     long[][] dp = new long[2][pointNum + 1];       for (int i = 1; i <= face; i++)         dp[0][i] = 1;       int flag = 1;                                     /* 旋转标记 */     for (int i = 2; i <= n; i++, flag = 1 - flag) {         for (int j = 0; j <= pointNum; j++)             dp[flag][j] = 0;                          /* 旋转数组清零 */           for (int j = i; j <= pointNum; j++)             for (int k = 1; k <= face && k <= j; k++)                 dp[flag][j] += dp[1 - flag][j - k];     }       final double totalNum = Math.pow(6, n);     List<Map.Entry<Integer, Double>> ret = new ArrayList<>();     for (int i = n; i <= pointNum; i++)         ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));       return ret; } 61. 扑克牌顺子 NowCoder 题目描述 五张牌，其中大小鬼为癞子，牌面为 0。判断这五张牌是否能组成顺子。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public boolean isContinuous(int[] nums) {       if (nums.length < 5)         return false;       Arrays.sort(nums);       // 统计癞子数量     int cnt = 0;     for (int num : nums)         if (num == 0)             cnt++;       // 使用癞子去补全不连续的顺子     for (int i = cnt; i < nums.length - 1; i++) {         if (nums[i + 1] == nums[i])             return false;         cnt -= nums[i + 1] - nums[i] - 1;     }       return cnt >= 0; } 62. 圆圈中最后剩下的数 NowCoder 题目描述 让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0...m-1 报数 .... 这样下去 .... 直到剩下最后一个小朋友，可以不用表演。 解题思路 约瑟夫环，圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。 复制代码 1 2 3 4 5 6 7 public int LastRemaining_Solution(int n, int m) {     if (n == 0)     /* 特殊输入的处理 */         return -1;     if (n == 1)     /* 递归返回条件 */         return 0;     return (LastRemaining_Solution(n - 1, m) + m) % n; } 63. 股票的最大利润 Leetcode 题目描述 可以有一次买入和一次卖出，买入必须在前。求最大收益。 解题思路 使用贪心策略，假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。 复制代码 1 2 3 4 5 6 7 8 9 10 11 public int maxProfit(int[] prices) {     if (prices == null || prices.length == 0)         return 0;     int soFarMin = prices[0];     int maxProfit = 0;     for (int i = 1; i < prices.length; i++) {         soFarMin = Math.min(soFarMin, prices[i]);         maxProfit = Math.max(maxProfit, prices[i] - soFarMin);     }     return maxProfit; } 64. 求 1+2+3+...+n NowCoder 题目描述 要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 A ? B : C。 解题思路 使用递归解法最重要的是指定返回条件，但是本题无法直接使用 if 语句来指定返回条件。 条件与 && 具有短路原则，即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。利用这一特性，将递归的返回条件取非然后作为 && 的第一个条件语句，递归的主体转换为第二个条件语句，那么当递归的返回条件为 true 的情况下就不会执行递归的主体部分，递归返回。 本题的递归返回条件为 n <= 0，取非后就是 n > 0；递归的主体部分为 sum += Sum_Solution(n - 1)，转换为条件语句后就是 (sum += Sum_Solution(n - 1)) > 0。 复制代码 1 2 3 4 5 public int Sum_Solution(int n) {     int sum = n;     boolean b = (n > 0) && ((sum += Sum_Solution(n - 1)) > 0);     return sum; } 65. 不用加减乘除做加法 NowCoder 题目描述 写一个函数，求两个整数之和，要求不得使用 +、-、*、/ 四则运算符号。 解题思路 a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。 递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。 复制代码 1 2 3 public int Add(int a, int b) {     return b == 0 ? a : Add(a ^ b, (a & b) << 1); } 66. 构建乘积数组 NowCoder 题目描述 给定一个数组 A[0, 1,..., n-1]，请构建一个数组 B[0, 1,..., n-1]，其中 B 中的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。要求不能使用除法。 解题思路 复制代码 1 2 3 4 5 6 7 8 9 public int[] multiply(int[] A) {     int n = A.length;     int[] B = new int[n];     for (int i = 0, product = 1; i < n; product *= A[i], i++)       /* 从左往右累乘 */         B[i] = product;     for (int i = n - 1, product = 1; i >= 0; product *= A[i], i--)  /* 从右往左累乘 */         B[i] *= product;     return B; } 67. 把字符串转换成整数 NowCoder 题目描述 将一个字符串转换成一个整数，字符串不是一个合法的数值则返回 0，要求不能使用字符串转换整数的库函数。 复制代码 1 2 3 4 5 6 7 Iuput: +2147483647 1a33   Output: 2147483647 0 解题思路 复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int StrToInt(String str) {     if (str == null || str.length() == 0)         return 0;     boolean isNegative = str.charAt(0) == '-';     int ret = 0;     for (int i = 0; i < str.length(); i++) {         char c = str.charAt(i);         if (i == 0 && (c == '+' || c == '-'))  /* 符号判定 */             continue;         if (c < '0' || c > '9')                /* 非法输入 */             return 0;         ret = ret * 10 + (c - '0');     }     return isNegative ? -ret : ret; } 68. 树中两个节点的最低公共祖先 解题思路 二叉查找树 Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree 二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。 复制代码 1 2 3 4 5 6 7 8 9 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {     if (root == null)         return root;     if (root.val > p.val && root.val > q.val)         return lowestCommonAncestor(root.left, p, q);     if (root.val < p.val && root.val < q.val)         return lowestCommonAncestor(root.right, p, q);     return root; } 普通二叉树 Leetcode : 236. Lowest Common Ancestor of a Binary Tree 在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最低公共祖先。 复制代码 1 2 3 4 5 6 7 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {     if (root == null || root == p || root == q)         return root;     TreeNode left = lowestCommonAncestor(root.left, p, q);     TreeNode right = lowestCommonAncestor(root.right, p, q);     return left == null ? right : right == null ? left : root; }

Hello～近期在找新的机会吗？ 这个岗位考虑一下不？ 工作职责: 1、 价值观建立：在日常工作中，践行蔚来价值观，并向团队成员有效传导； 2、 团队工作计划：根据销售策略和团队目标，制定团队工作计划和目标分配，以确保完成销售、服务和交付等目标； 3、 销售达成：执行并确保团队完成用户发展和接待任务，将潜在用户转化为真正用户，完成销售并向客户交付车辆； 4、 用户关系管理：维护现有蔚来车主，定期跟进追踪会员，提供有关愉悦生活方式解决方案，增强现有车主品牌粘性； 5、 市场/用户开拓：开拓潜在客户，与市场同事合作，开展店外营销活动；不断创新、积极主动地吸引潜在用户； 6、 团队管理：监督、辅导团队成员（NIO specialist 和交付专员）的日常工作开展；开展绩效管理，提升并发展员工能力； 7、 开店支持：支持公司新店的开设，确保公司文化和价值观在新团队的传承。 任职要求: 1、 本科学历，热爱新能源汽车行业，3年以上零售、行业销售、大客户销售经验（中高端汽车优先），能够出色达成销售目标；
 2、 优秀的商业拓展能力和商务谈判能力； 3、 对销售数据敏感，优秀的数据分析能力和逻辑分析能力； 4、 认可蔚来汽车的创业公司文化，具备创业公司需要的心理素质； 5、 抗压能力强，能够适应在高速发展的环境中开展销售管理工作，达到公司业绩指标要求 6、 良好的自我管理能力及自我学习能力。 7、 接受零售业工作时间，根据工作安排排班，需要晚上和周末工作。 职位关键词：汽车零售 职位亮点：业务核心成长迅速扁平化管理 工作地点：深圳

1. 一面 面我的是腾讯视频所在部门的项目组长, 深圳,后台研发,自我介绍之后就开始问问题了,主要问题还是围绕我的第一个项目--网络编程相关的项目.项目使用的是TCP还是UDP? UDP的包头多长,具体包含哪些字段? sellect和epoll的区别. 描述一下多播协议,应用场景. TCP的快速重传机制. 进程通信的方式,讲到管道的时候,让我阐述了下,讲到共享内存的时候,让将了下加什么级别的锁.   问了一下GDB调试的东东:bt表示啥含义.如何切换函数调用栈,如何打印变量的二进制数据,如何调试core dump文件? makefile如何解决顶级依赖的问题(是这个问题嘛? 我也记不太清,囧). 问了HTTP 1.1和HTTP1.0的区别(我答了对理论不熟之后,他就没具体问了...) 问了下当学校论坛"linux/Unix"区版主的收获.  最后让写了一个代码:字符串中找到给定的字符串,然后替换成目标字符串. 尽可能考虑多的异常情况. 2. 二面 二面显示的是GM/EVP环节,回来搜了下发现是GeneralManager/ExecutiveVicePresident 应该就是总监面试(后面从HR那里了解到是所在部门的大BOSS)... 这个面试面的很轻松,完全没有具体技术问题(其它有同学,有让写程序写很多的情况)... 问了三个问题吧,一是项目涉及的知识点/掌握的技能, 二是对腾讯视频的产品的了解(楼主比较喜欢看NBA,就跟他聊了NBA的未来几年的独家直播权,他也比较开心,说以后来了腾讯视频就可以了解背后的运作),三是一道博弈的题目 楼主当时不知道是博弈的题目,不过答了个大概...  身边有个同学就挂在了二面环节... 3. HR面 这个就很easy了,基本不刷人的(除非人品有问题). 自我介绍,项目简单介绍, 个人爱好,同学评价,家庭情况,工作地要求,实习时间,为什么当"LINUX"区的版主,同学怎么评价你的,有神马问题想问他的... 整个流程问下来感觉还是挺轻松的...

哔哩哔哩三面结束，说是还有最后一个部门总负责人面试，许愿保佑！但愿能进最后一轮。 这个秋招，已经经历很多次打击了。听说超级简历里面许愿很灵，保佑保佑吧！

RT

答案是诚实的投其所好，这二者兼有，缺一不可。 如何理解？ 首先诚信是职场的基本原则，不要为了得到工作故意去欺骗，因为一个谎话要用另一个谎话去接住，很容易露陷，有经验的面试官基本也都自由一套办法，去验证你的真实程度。 所以最好不用选择欺骗的方法，诚信是底线。 但是我们还是要投其所好，有选择性的去回答，而不是对方问什么不经过思考的回答。 如何投其所好？ 面试一切问题回答的核心都要回答为什么你可以胜任这份工作来，一切回答最后的归结点都是你具备相应的能力，可以胜任这份工作。 经常遇到一些过于诚实的应聘者，问你觉得你最大的缺点是什么，然后回答n个和工作岗位直接冲突的点，给了面试官n个不选他的理由。 或者问你为什么来应聘这份工作，就诚实的回答就是刚好看到了来试一试吧… 我们鼓励真诚，但是我们要适当的去修饰你的真诚，既然选择了来求职，就要用你最诚恳的态度和准备，来告诉对方为什么要选择你。 如果自己都说服不了自己，如果你不拿出最大的诚意去争取，对方为什么要给你机会呢？

很多人在求职时，如果长时间收不到面试邀请的时候，会产生一种行为——海投简历。觉得投得越多，机会越多。所以不管岗位要求、行业类型、工资高低……先投它个500份再说。 这样确实省时省力，从概率学的角度来看，好像也会拿到更多的面试机会。如果说投15-20份简历能收获一份面试邀请，那投500份简历就能拿到25次面试机会。 然而事实真的是这样吗？答案是否定的。 为什么呢？ 01 不讲条件的概率算法，是耍流氓！ 投递简历应该是在仔细阅读JD，分析自己与JD中描述信息相符合的前提下投递，这样精准的投放，能够有更大概率获得面试机会。 而海投简历的行为，为了能够在短时间内对大量岗位进行投递，往往不会仔细阅读JD，甚至不阅读JD，那么岗位需求、工作职责等信息并不能够完全了解，无法做出判断自己是否适合该岗位工作，获得面试机会概率远小于精准投放。 除了转化率不高，海投还有很多其他方面的弊端，请接着往下看。 02 海投简历是无个人信息保护意识的表现 简历包含了详细的个人信息，已经不仅是电话号码这种个人信息，因此，我们需要更加注重个人信息的保护。 海投简历意味着可能你并不知道给哪家公司投了简历,这些公司都是干什么的？他们拿到你的信息会做什么？被不相关的公司掌握个人信息，且这些信息是你主动发给他的，是不是有点自投罗网的刺激感。 虽然你找工作必须要投递简历，虽然我们会对发布的职位信息进行审核，但防人之心不可无，个人信息的保护意识要加强，连什么公司在招人你都没认真了解就投递简历，未免有些显得过于儿戏。 03 接到面试岗位可能不符合个人要求 可以肯定的说,海投是能获得面试机会的，要不也不会有很多同学选择海投的方式，但海投得到的面试岗位一定符合你的个人要求吗？ 每个人对工作都有一定的预期：薪资、工作地点、公司规模、所属行业、岗位属性、发现前景、福利待遇等等。 而海投时，你可能真的不会认真去看JD上关于这些内容的介绍，但对于HR来说， 看到你投递的简历了，就认为你对该岗位有意向，认为该岗位符合你的基本需求，这样在你的条件符合用人单位的需求时，就会给与你联系进行面试。 这种情况下的面试，岗位可能很难符合你的个人要求。 04 可能错失心仪的公司和岗位 海投了那么简历，如果刚好有符合你预期的，又邀请你来面试，那也是一件皆大欢喜的事情。 可是还有一个现实问题，你海投了那么多份简历，真的能对投递的每个岗位都有个印象吗？如果没有，那么在因为这个而失去错失机会，是不是很可惜啊。 有些公司的HR会在电话邀约面试时，做一些基本信息的了解，其中可能包括“求职意向”的调查，想知道约你来面试你是否会放鸽子，以及如果一切顺利你的入职意向有多少。 通常的话术是： HR：小明你好，我是XX公司HR，看到你投递了我们公司的xx职位，想先对你做一些简单的了解。 小明：xx公司？ HR：xx公司，xx岗位， 小明：哦…… HR：看到你的简历之前不是从事我们公司相关行业的，想了解一下你对我们公司及行业了解多少。 …… 基本聊到这儿，有经验的HR就知道你是海投的，没有诚意、不稳定等这种标签就会马上被贴给你，礼貌寒暄几句，就没有然后了。 05 海投简历的求职者，面试时往往准备不充分 海投简历求职者在投递简历时，没有对岗位、行业、公司做一定的筛选，是无法保证所投递的岗位是自己擅长及知识结构所覆盖的，就算来到了面试环节，在面试准备上往往不能做到非常充分，降低了获取offer的可能性。 相对而言，精准投递简历求职者能够更好的做面试准备，了解掌握面试岗位所需要的背景知识及技能结构，甚至对公司情况做到非常了解，更容易获得offer。 求职，特别是想要找个好工作，一直以来都不是一个容易的事。现在竞争越发激烈的情况下，为了能获得一份工作而选择海投简历是可以理解的， 但还需希望求职者都能科学求职。认真阅读JD，精准投递简历，充分做好面试准备，每一步都踏踏实实的去做，相信找到一个理想的工作，也不是那么困难。 加油！祝每位求职者都前程无忧。

想知道一般这种公司薪资待遇和工作环境怎么样呢？

本硕北邮毕业五年，国企的同学大部分状态是这样的： 1、收入：一年少一点的20个左右，多一点的可能30-40个税后。 2、生活节奏：朝8点30-晚5点30，忙的时候不定到几点了，周末大概率不加班，特殊情况除外。一般情况下早上6点多起床，7点前要出门，晚上回到家7点左右。基本都已婚，有车有房有娃 基本上，毕业时候有想法的，三年内都跳走去互联网了，5年了还待在国企的，一般也不准备跳（跳不动了）。大部分男生都明显吃胖了。 互联网同学是这样的： 1、收入：大部分50-100，能干且运气好的100+，运气特别好财务自由的也有，极少。互联网和国企同学收入差距前两三年基本持平，第四和第五年开始甩开差距。 2、生活节奏：9点30左右-晚8点之后几点的都有，平均一周6天，并且是长期这个节奏。毕业前三年还好，可以吃老本，慢慢身体不好的熬不住了，自己能明显感觉身体变差，体检也支持自身感觉，内分泌失调、容易生病、生病不容易好等。能够在互联网公司继续往上走的，毫无例外都是业务水平好且为人靠谱+身体好（底子好）+运气（业务方向快速发展期，有坑等你填）。单身比例明显高于国企同学。 单身或者恋爱，互联网节奏快精神压力大无所谓。 一旦结婚有娃或者准备养娃，只能靠家人和另一半多付出，非常辛苦。以及你回来，娃已经睡了，第二天你又起床就走，（高质量）亲子时间是没有的，错过娃很多成长。 以上，一般家境还可以的/身体素质一般或者不好/业务水平一般的/自以为事业心很强的,统统建议国企公务员，不要因为同学去了互联网/拿到了的入门的互联网offer就去互联网，时间会告诉你，身体是1，身体不好，事业发展无从谈起，你的意志力撑不了多久，到头来当不了核心员工，收入不比国企多多少，还超级累。身体很好+很有想法或者很缺钱的+收到核心岗位offer的同学，在互联网会有很好发展，当然毕竟好几年过去了，现在好坑越来越少了。 总结：适合自己的就是最好的，不要神话和迷恋互联网。 如果再给我一次机会重读大学，我会这样度过： 1、尽早写简历，对照JD看看自己还需要什么技能，然后多去实习，看看自己适合什么样的行业企业、工作节奏、岗位内容，尽早找到职场工作的方法。 2、好好锻炼身体，不随意略过早饭、不节食减肥。身体健康健壮是最重要的。 3、不把自己最宝贵的精力浪费给不适合的另一半、还有无所谓的小情绪小纠结伤春悲秋上，不适合就赶紧分。情绪不重要，周围人的看法不重要，结果很重要。多给自己健康的兴趣爱好留点空间，比如羽毛球、游泳、篮球、绘画、读书、写作等等等等，做精，做强。说到底，能有时间和精力考虑这些有的没的，还是因为被家长保护的太好了，只是觉得按部就班“应该好好读书”，毕业到时候“应该好好找工作”，而没感觉到真实的生活压力。

RT