题目描述 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例1 输入: n = 3输出: 6 示例2 输入: n = 9输出: 45 解题思路 直接上公式。当 n 为偶数时，就是众所周知当 n 为奇数时，要在上面式子的基础上再加上中间的数，中间的数就是 (n + 1) / 2，即公式为对比上下两式，其实只要在最后面多出来的 (n + 1) 上加上一个系数 k，当 n 为奇数时 k = 1，当 n 为偶数时 k = 0。用与运算即可满足这个条件。 Java代码实现 class Solutio...

题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 解题思路 看完题目第一感觉就是计数排序，计数超过数组长度一般的立刻结束并返回这个元素。不过会有一个弊端。当数组中的元素一个数值非常大一个数值非常小，会导致数组长度超出并报错。 摩尔投票法：定义一个众数 num，最开始是数组第一个元素，一个得票数 votes。若当前遍历的数等于 num，那么 votes + 1，否则 votes - 1。如果得票数 votes 为 0，那么众数 nu...

题目描述 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例1 输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1] 示例2 输入：arr = [0,1,2,1], k = 1输出：[0] 解题思路 最简单的方法，先排序后选前 k 个元素。用选择排序，只选 k 个最小的就结束排序了。 最大堆方法，当堆的元素个数超过 k 时，将最大的值弹出，最后堆中只保留了 k 个最小值。 快速排序法，如果 pivot 刚好在第 k 个位置，那么 0 ~ k 的值是 k 个最小值。如...

题目描述 有 n 个字符串，每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字，不同字符映射为不同的数字。这样每个字符串就可以看做一个整数，唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大？ 输入描述 每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n ， 接下来有 n 行，每行一个长度不超过 12 且仅包含大写字母 A-J 的字符串。 n 不大于 50，且至少存在一个字符不是任何字符串的首字母。 输出描述 输出一个数，表示最大和是多少。 输入示例 2ABCBCA 输出示例 18...

题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 解题思路 二叉搜索树从小到大排列，一下子联想到 DFS，既然是D...

题目描述 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例1 输入 head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 返回值 [[7,null],[13,0],[11,4],[10,2],[1,0]] 示例2 输入 head = [[1,1],[2,1]] 返回值 [[1,1],[2,1]] 示例3 输入 head = [[3,null],[3,0],[3,null]] 返回值 [[3,...

题目描述 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 2 个节点是值为 4 的节点。 示例 输入 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回值 返回链表 4->5. 解题思路 用双指针，两个指针相隔距离为 k，两个指针同时向后移动，当后面的指针为 null 时，前面的指针就是想要的值。 Java代码实现 class Solution { public ...

问题描述 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 输入 head = [1,3,2] 返回值 [2,3,1] 解题思路 使用栈的特性FILO使输出顺序反转。 Java代码实现 class Solution { public int[] reversePrint(ListNode head) { Stack<ListNode> stack = new Stack<ListNode>(); while (head != null) { stack.push(head)...

题目描述 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 解题思路 用快慢指针解决问题，如上图，红色是慢指针走的路程，蓝色是快指针走的路程。快指针每次走两步，慢指针每次走一步。 当慢指针走到入口节点时，路程为X，因为快指针每次走慢指针的两倍，所以快指针路程为2X。 当他们相遇时，慢指针又走了Y，快指针则又走了2Y。 根据上图我们可以得知，当慢指针走到入口节点时，快指针与慢指针的短弧距离为 ，长弧距离为 。 当快慢指针相遇时，它们与入口节点的长弧距离为 ，也就是说只要让快指针回到起点，慢指针不动，然后它们每次只走 1 步，它们必定会在 X 步后相遇，这个位...

题目描述 输入两个链表，找出它们的第一个公共节点。如下面的两个链表：在节点 c1 开始相交。 解题思路 两个链表互相加上对方的长度，使它们的长度一致，用两个指针去分别检查两个链表，最终会找到公共节点。 Java代码实现 public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 == null || pHead2 == null) return null; ListNode ptr1 = pHead1...

解题思路 两种方法： MySQL 在 8.0 版本以下，使用通常方法解题。 首先我们不考虑 [1, 2, 2, 3] 这样并列时不跳数字的排列方式，而是考虑 [1, 2, 2, 4] 这种有并列时会跳数字的排列方式。这种情况下解题思路与《获取当前薪水第二多的员工的emp_no以及其对应的薪水salary》 以及《查找入职员工时间排名倒数第三的员工所有信息》 一致。可以用两个 salaries 表做笛卡尔积，COUNT() 函数计算比自己工资高的人数，如果自己的工资是最高的，即没有人比自己工资高，那么计算后结果为 0。如果自己是第二高，那么结果为 1。最后在结果上 + 1，就是上面所说的会...

解题思路 用 employees 表中的 emp_no 和 hire_date 去查找 salaries 表中该员工入职时的工资，然后再使用 emp_no 去查找 to_date = '9999-01-01' 的工资，两个相减，就是入职以来工资的涨幅。 代码实现 SELECT t1.emp_no, (t2.salary - t1.salary) growth FROM ( SELECT e.emp_no, s.salary FROM employees e LEFT JOIN salaries s ON e.emp_no = s.emp_no WHER...