Leetcode 136：只出现一次的数字 题目描述 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 示例 输入: [2,2,1] 输出: 1 解题思路 这里我们可以利用异或的原理，我们发现在异或中： a⊕0=a；a⊕a=0。a⊕b⊕a=(a⊕a)⊕b=0⊕b=b 所以我们只需要将所有的数进行 XOR 操作，得到那个唯一的数字。 代码实现 int singleNumber(vector&…

Leetcode 142：环形链表2 题目描述 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 题目解析 《剑指offer》中也有此题，所以直接复制过来予以说明。 其实我的思路是把每个访问过的结点做标记，然后不断往下走后，遇到的第一个标记过的点，就是还的入口结点，如果没有遇到，则就不存在环，返回null。但是这…

Leetcode 148：排序链表 题目描述 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5 解题思路 由于题目要求复杂度为O(nlogn)且空间复杂度为常数级，我们可以想到的是堆排序，但是实际上，由于是链表，其不需要借助额外的数组来存储内容，只需要通过链表直接的链接调整即可，所以对于链表来说，归并排序的空间复杂度也是O(1…

Leetcode 155：最小栈 题目描述 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。 示例 MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); -…

Leetcode 169：求众数 题目描述 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。 示例 示例1： 输入: [3,2,3] 输出: 3 示例2： 输入: [2,2,1,1,1,2,2] 输出: 2 解题思路1 由于众数是出现次数大于n/2的数字，所以第n/2个数字已经是众数。故可以采用快速排序方法。 代码实现1 int partition(vector<int>& nums, int …

Leetcode 207：课程表 题目描述 现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1] 给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？ 解题思路 这个题目是一个图的问题，所给的示例是用边缘列表来表示的图。也即假如边缘列表表示如下 序号 节点1 节点2 1 0 1 2 1 2 3 2 0 所表示的图为 可以发现上图就是一个无法实现课程的图，这类的特点是它是一个有向…

Leetcode 215：数组中的第K个最大元素 题目描述 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2： 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 解题思路 偷了个懒，就是利用求第k个小的数字改的。因为求第k个大的数字和求第m个小的数字有以下关系（假设数组长度为len）：m=len-k+1，所以直接进行转换即可…