链表
1. 找出两个链表的交点
|
|
输出那个ListNode c1
思路：合并成一个相同链表考虑。
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
|
|
2. 链表反转
示例:
|
|
思路：递归/头插法
3. 归并两个有序的链表
示例：
|
|
思路：递归（递归出口不太好想）/迭代
4. 从有序链表中删除重复节点
示例 1:
|
|
示例 2:
|
|
思路：1直接法2（比较前后值）尾插法3递归（注意递归出口）
5. 删除链表的倒数第 n 个节点
示例：
|
|
进阶：
你能尝试使用一趟扫描实现吗？
思路：1两趟很容易想到2一趟用双指针（指针保持n距离往后移到null）
6. 交换链表中的相邻结点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
思路：就常规思路。
7. 链表求和
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
思路：1用到翻转2用栈做two sum 进位相加
8. 回文链表
请判断一个链表是否为回文链表。
示例 1:
|
|
示例 2:
|
|
思路：
切成两半【用fast slow 找出中间的节点】（如果不切，想把整个串反转再比较 不行 会破坏链表结构），把后半段反转，然后比较两半是否相等。
9. 分隔链表
|
|
思路：就运用链表，分成几份，把最后的next置成null
10. 链表元素按奇偶聚集
请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
Example 1:
|
|
Example 2:
|
|
思路：用链表，3个指针，注意while条件
总结：有不少题目可以用递归解体，但要注意出口条件（2,3,4）；题设参数给出的链表往往第一个节点就是值节点，我们编代码时可以加上一个头结点方便理解；尾插法会移动头结点位置，头插法不会，但是头插法需要记住上一个新增的节点位置；某些时候可以把新增一个链表作为思路（头/尾插法）；注意双指针，栈等数据结构使用
双指针
1. 有序数组的 Two Sum
|
|
题目描述：在有序数组中找出两个数，使它们的和为 target。
思路：双指针，一头一尾。
2. 两数平方和
|
|
题目描述：判断一个数是否为两个数的平方和。
思路：双指针，一头一尾（尾指向开方位置即可）。
3. 反转字符串中的元音字符
|
|
思路：双指针，一头一尾，注意if 分支书写。
4. 回文字符串
示例 1:
输入: “aba”
输出: True
示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
思路：首尾指针，首尾端字母不等式，选其中一端删除字母后比较剩余字符串是否为回文串（思路比较自然，好想）
5. 归并两个有序数组
|
|
题目描述：把归并结果存到第一个数组上。
思路：双指针（均指向尾部），从尾向头可以省去额外空间，注意if分支；
6. 判断链表是否存在环
示例 1：
|
|
思路：
使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。
7. 最长子序列
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
输入:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]
输出:
“apple”
思路：双指针首先还是比较好想到，但在循环中更巧妙地筛选出字典序和长度条件不符的字符串 不太好想
数组与矩阵
1. 把数组中的 0 移到末尾
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
思路：1o(n)解法2o(n方)解法（我用的交换）。
2. 改变矩阵维度
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
|
|
思路：循环遍历。
3. 找出数组中最长的连续 1
给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
思路：正常想。
4. 有序矩阵查找
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 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]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路：1递归（我的解法）2正常循环遍历（GitHub解法）row=0,col=列数-1，target小row++,target大col–;
5. 有序矩阵的 Kth Element
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
思路：1二分查找（GitHub解法）2堆解法：a.小顶堆里面放n*n个元素，删除k-1个元素，剩下来的堆顶元素即为所找。（GitHub解法）b.往小顶堆中不断追加matrix里的元素，追加过程中维护堆的大小保证为matrix.length+1-k，追加完成后，堆顶元素即为所找。（我的解法）
小顶堆Java定义写法
|
|
6. 一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
给定数组的长度范围是 [2, 10000]。
给定的数组是无序的。
思路：1.排序后找到（时：o(logN)）2用一个数组记录数字出现一次还是2次还是0次（时：o(N);空：o(Log(N))）【我的解法】3.利用交换实现时：o(N),空间o(1)
6.1寻找所有丢失的元素
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
思路：同上面的交换解法
6.2寻找所有重复的元素(同上思路)
7. 找出数组中重复的数，数组值在 [1, n] 之间
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
思路：1二分2双指针快慢（类似于有环链表中找出环的入口）参考LeetCode官方解法以及下方评论
8. 数组相邻差值的个数
给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：
① 如果这个数组是 [a1, a2, a3, … , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] 中应该有且仅有 k 个不同整数；.
② 如果存在多种答案，你只需实现并返回其中任意一种.
示例 1:
输入: n = 3, k = 1
输出: [1, 2, 3]
解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1
示例 2:
输入: n = 3, k = 2
输出: [1, 3, 2]
解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2
思路：让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 … k/2 k/2+1.
9. 数组的度
给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.
示例 2:
输入: [1,2,2,3,1,4,2]
输出: 6
思路：1一步一步做（我的解法）2GitHub解法代码更简洁
10. 对角元素相等的矩阵
如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。
给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。
|
|
思路：1自己思路ac 不了2GitHub思路：用一个递归的check方法，递归出口–超出边界—返回true
11. 嵌套数组
索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到并返回最大的集合S，S[i] = {A[i], A[A[i]], A[A[A[i]]], … }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]… 以此类推，不断添加直到S出现重复的元素。
输入: A = [5,4,0,3,1,6,2]
输出: 4
解释:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
思路：1我的思路有点类似递归加记忆化搜索2GitHub解法用2层循环，第二层循环访问过就标记-1，当再次遇到-1即形成环此时退出循环。
12. 分隔数组
数组arr是[0, 1, …, arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
|
|
思路：1我的解法：设置两个sum分别累加索引和值，2个sum相等时，cnt++同时2个sum归0；2github解法：找到当前段最大值right，right==索引 cnt才++。
总结：对于矩阵可以想到递归解决（10），对于特殊矩阵注意遍历顺序（4）；数组如要找出重复数或丢失数可考虑用到交换（6,7）；注意一些类似递归搜索的想法（11）；注意arr[i]和i的关系（12）
字符串
1. 字符串循环移位包含
|
|
给定两个字符串 s1 和 s2，要求判定 s2 是否能够被 s1 做循环移位得到的字符串包含。
s1 进行循环移位的结果是 s1s1 的子字符串，因此只要判断 s2 是否是 s1s1 的子字符串即可。
2. 字符串循环移位
|
|
将字符串向右循环移动 k 位。
将 abcd123 中的 abcd 和 123 单独翻转，得到 dcba321，然后对整个字符串进行翻转，得到 123abcd。
3. 字符串中单词的翻转
|
|
将每个单词翻转，然后将整个字符串翻转。
4. 两个字符串包含的字符是否完全相同
|
|
思路：用一个空间；桶（需要统计每个字母出现次数）
5. 计算一组字符集合可以组成的回文字符串的最大长度
|
|
思路：GitHub解法用 (cnt/2)*2；桶（需要统计每个字母出现次数）
6. 字符串同构
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
|
|
思路：（标记一下 ）
记录一个字符上次出现的位置，如果两个字符串中的字符上次出现的位置一样，那么就属于同构。
7. 回文子字符串个数
|
|
思路：中心扩展。（标记一下，容易忘）
8. 判断一个整数是否是回文数
要求不能使用额外空间，也就不能将整数转换为字符串进行判断。
思路：GitHub解法（将整数分成左右两部分，右边那部分需要转置，然后判断这两部分是否相等）
9. 统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数
给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。
|
|
思路：标记一下
First, I count the number of 1 or 0 grouped consecutively.
For example “0110001111” will be [1, 2, 3, 4].
Second, for any possible substrings with 1 and 0 grouped consecutively, the number of valid substring will be the minimum number of 0 and 1.
For example “0001111”, will be min(3, 4) = 3, ("01", "0011", "000111")
|
|
哈希表
1. 数组中两个数的和为给定值
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路：1暴力2两遍哈希表3一遍哈希表
2. 判断数组是否含有重复元素
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:
输入: [1,2,3,1]
输出: true
思路：1hashmap 2hashset（巧妙利用长度比较）
3. 最长和谐序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。
示例 1:
输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
思路：hash表，遍历时只需要找有没有大一的就好，小一的不用考虑；因为后续遍历过程中还是能访问到。
4. 最长连续序列
没做出来
（今天用排序方法做出来）
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路：1 排序后再找（我的解法）2hashset 只找比当前数大一的不找小一的；
哈希表这种空间换时间的算法有时候不太好想；桶排序；通常对调k v 去建立哈希表；hashmap,hashset;遍历过程往往只需找大一，小一的情况在后遍历过程中还是能访问到，不会出现考虑不全面的问题。
栈和队列
1. 用栈实现队列
思路：
栈的顺序为后进先出，而队列的顺序为先进先出。使用两个栈实现队列，一个元素需要经过两个栈才能出队列，在经过第一个栈时元素顺序被反转，经过第二个栈时再次被反转，此时就是先进先出顺序。
2. 用队列实现栈
思路：
在将一个元素 x 插入队列时，为了维护原来的后进先出顺序，需要让 x 插入队列首部。而队列的默认插入顺序是队列尾部，因此在将 x 插入队列尾部之后，需要让除了 x 之外的所有元素出队列，再入队列。【这个容易忘】
3. 最小值栈
思路：维护一个data栈，和一个最小值栈（且data栈push时它也push，data栈pop时它也pop）；
对于实现最小值队列问题，可以先将队列使用栈来实现，然后就将问题转换为最小值栈，这个问题出现在 编程之美：3.7。（我的解法是用一个栈存data，在pop的时候花o(n)的时间去遍历得到最小值）
4.用栈实现括号匹配
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 3:
|
|
思路：判断是左括号时进栈，否则先出栈比较是否匹配，匹配则进栈，不匹配直接return false。
5. 数组中元素与下一个比它大的元素之间的距离
思路：
在遍历数组时用栈把数组中的数存起来，如果当前遍历的数比栈顶元素来的大，说明栈顶元素的下一个比它大的数就是当前元素。（巧妙地用数组的索引的差值来计算出距离，栈里面仅保存索引，值可以用数组获取到）（我的解法是走2层循环用双指针）
6. 循环数组中比当前元素大的下一个元素
思路：
与 上题不同的是，数组是循环数组，并且最后要求的不是距离而是下一个元素。（一样做）
用队列实现栈记得是push的时候把所有其他元素出队;最小值栈注意minstack长度使他和数据栈长度一样来处理；5，6记得栈里面存索引
排序
1. Kth Element
|
|
题目描述：找到倒数第 k 个的元素。
排序 ：时间复杂度 O(NlogN)，空间复杂度 O(1)
|
|
堆 ：时间复杂度 O(NlogK)，空间复杂度 O(K)。
|
|
快速选择 ：时间复杂度 O(N)，空间复杂度 O(1)
|
|
桶排序
1. 出现频率最多的 k 个元素
347. Top K Frequent Elements (Medium)
|
|
设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。
把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
2. 按照字符出现次数对字符串排序
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
“tree”
输出:
“eert”
解释:
‘e’出现两次，’r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。
示例 2:
输入:
“cccaaa”
输出:
“cccaaa”
解释:
‘c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。
注意”cacaca”是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
“Aabb”
输出:
“bbAa”
解释:
此外，”bbaA”也是一个有效的答案，但”Aabb”是不正确的。
注意’A’和’a’被认为是两种不同的字符。
荷兰国旗问题
荷兰国旗包含三种颜色：红、白、蓝。
有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。它其实是三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
思路：
我们用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。(容易忘)
|
|
二分查找
1. 求开方
|
|
一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。
对于 x = 8，它的开方是 2.82842…，最后应该返回 2 而不是 3。在循环条件为 l <= h 并且循环退出时，h 总是比 l 小 1，也就是说 h = 2，l = 3，因此最后的返回值应该为 h 而不是 l。
2. 大于给定元素的最小元素
给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。
数组里字母的顺序是循环的。举个例子，如果目标字母target = ‘z’ 并且有序数组为 letters = [‘a’, ‘b’]，则答案返回 ‘a’。
题目描述：给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符（这句话是转换题意）。
3. 有序数组的 Single Element
|
|
题目描述：一个有序数组只有一个数不出现两次，找出这个数。
要求以 O(logN) 时间复杂度进行求解，因此不能遍历数组并进行异或操作来求解，这么做的时间复杂度为 O(N)。
令 index 为 Single Element 在数组中的位置。在 index 之后，数组中原来存在的成对状态被改变。如果 m 为偶数，并且 m + 1 < index，那么 nums[m] == nums[m + 1]；m + 1 >= index，那么 nums[m] != nums[m + 1]。
从上面的规律可以知道，如果 nums[m] == nums[m + 1]，那么 index 所在的数组位置为 [m + 2, h]，此时令 l = m + 2；如果 nums[m] != nums[m + 1]，那么 index 所在的数组位置为 [l, m]，此时令 h = m。
因为 h 的赋值表达式为 h = m，那么循环条件也就只能使用 l < h 这种形式。
4. 第一个错误的版本
题目描述：给定一个元素 n 代表有 [1, 2, …, n] 版本，在第 x 位置开始出现错误版本，导致后面的版本都错误。可以调用 isBadVersion(int x) 知道某个版本是否错误，要求找到第一个错误的版本。
如果第 m 个版本出错，则表示第一个错误的版本在 [l, m] 之间，令 h = m；否则第一个错误的版本在 [m + 1, h] 之间，令 l = m + 1。
因为 h 的赋值表达式为 h = m，因此循环条件为 l < h。
5. 旋转数组的最小数字
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
|
|
思路：二分法 if (nums[m] <= nums[h]) { h = m; } l<h
6. 查找区间
不弄了，细节是魔鬼。。
二分查找，正常是l<=h 然后if 三段论，mid+1,mid-1;对于1其实是要向下取整的，所以应该返回l和h当中小的那个即为h；对于h=m的情况，循环条件就用l<h,如：3，4，5；对于5找旋转数组的最小数字的if条件【if (nums[m] <= nums[h]) {】比较巧妙；6看不懂，可以看个链接
数学
1. 生成素数序列
统计所有小于非负整数 n的质数的数量。
示例:
|
|
思路：
埃拉托斯特尼筛法在每次找到一个素数时，将能被素数整除的数排除掉。
2之后的2 2,2 3,2 4….都标记为不是素数，3之后的3 3,3 4,3 5都标记为不是素数…
2. 最大公约数
|
|
最小公倍数为两数的乘积除以最大公约数。(记一记)
进制转换
1. 7 进制
给定一个整数，将其转化为7进制，并以字符串形式输出。
思路： while (num > 0) { sb.append(num % 7); num /= 7; }。
Java 中 static String toString(int num, int radix) 可以将一个整数转换为 radix 进制表示的字符串。
|
|
2. 16 进制
思路：
负数要用它的补码形式。（记一记吧）
|
|
负数要用它的补码形式。
|
|
3. 26 进制
|
|
因为是从 1 开始计算的，而不是从 0 开始，因此需要对 n 执行 -1 操作。
|
|
阶乘
1. 统计阶乘尾部有多少个 0
给定一个整数 n，返回 n! 结果尾数中零的数量。
尾部的 0 由 2 * 5 得来，2 的数量明显多于 5 的数量，因此只要统计有多少个 5 即可。
对于一个数 N，它所包含 5 的个数为：N/5 + N/52 + N/53 + …，其中 N/5 表示不大于 N 的数中 5 的倍数贡献一个 5，N/52表示不大于 N 的数中 52 的倍数再贡献一个 5 …。
|
|
如果统计的是 N! 的二进制表示中最低位 1 的位置，只要统计有多少个 2 即可，该题目出自 编程之美：2.2 。和求解有多少个 5 一样，2 的个数为 N/2 + N/22 + N/23 + …
|
|
字符串加法减法
1. 二进制加法
思路：双指针， while (carry == 1 || i >= 0 || j >= 0) {；有点像链表7 ：链表求和。
2. 字符串加法
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
思路：双指针， while (carry == 1 || i >= 0 || j >= 0) {；更加像链表7 ：链表求和。
相遇问题
1. 改变数组元素使所有的数组元素都相等
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
|
|
这是个典型的相遇问题，移动距离最小的方式是所有元素都移动到中位数。
思路：1先排序，再（用首尾指针向中间移动）累加（O(NlogN)。2快速选择找到中位数（如果数组个数为偶数的话其实中间的那2个数都可以作为中位数）O(N)
多数投票问题
1. 数组中出现次数多于 n / 2 的元素
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
思路：1Boyer-Moore Majority Vote Algorithm （没看）2桶排序
其他
1. 平方数
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
思路：1平方序列：1,4,9,16,..间隔：3,5,7,…间隔为等差数列，2自然的思路：i*i = num return true.
2. 3 的 n 次方
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
|
|
https://tva4.sinaimg.cn/large/005R6Otmgy1g6xxe0qh26j30le0ab0ta.jpg
3. 乘积数组
|
|
给定一个数组，创建一个新数组，新数组的每个元素为原始数组中除了该位置上的元素之外所有元素的乘积。
要求时间复杂度为 O(N)，并且不能使用除法。
思路：从左向右一趟循环，从右向左一趟循环，各自得到左边的乘积和右边的乘积
4. 找出数组中的乘积最大的三个数
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
思路：我的解法：先排序，再根据正负数个数情况找出最大值；github解法没高兴看。
每一个数都可以分解成素数的乘积;素数筛法把2之后的2 2,2 3,2 4….都标记为不是素数，3之后的3 3,3 4,3 5都标记为不是素数…；最大公约数 return b == 0 ? a : gcd(b, a % b);最小公倍数为两数的乘积除以最大公约数。………例题都蛮典型的，不总结了。。。
位运算
1. 统计两个数的二进制表示有多少位不同
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
思路：int z = x ^ y;然后算出z中有几个1。算出几个1的算法有：1 while(z != 0){ if ((z & 1) == 1) cnt++; z = z >> 1};2 while (z != 0) { z &= (z - 1); cnt++; }；【n&(n-1) 去除 n 的位级表示中最低的那一位。】3Integer.bitCount(z);
2. 数组中唯一一个不重复的元素
异或
3. 找出数组中缺失的那个数
思路：示例：0,1,3和0,1,2,3异或就能取到2；
4. 数组中不重复的两个元素
异或基础上用diff &= -diff区分出两个元素第一个不同的位；然后for循环遍历^=;【n&(-n) 得到 n 的位级表示中最低的那一位。 其余位变成0】
5. 翻转一个数的比特位
颠倒给定的 32 位无符号整数的二进制位。
思路
- 将给定的二进制数,由低到高位逐个取出
- 然后通过位运算将其放置到反转后的位置.
- 将上述结果再次通过运算结合到一起
|
|
6. 不用额外变量交换两个整数
|
|
7. 判断一个数是不是 2 的 n 次方
思路：1二进制表示只有一个 1 存在。【 return n > 0 && Integer.bitCount(n) == 1;】2利用 1000 & 0111 == 0 这种性质【return n > 0 && (n & (n - 1)) == 0;】
8. 判断一个数是不是 4 的 n 次方
思路：1这种数在二进制表示中有且只有一个奇数位为 1，例如 16（10000）。【return num > 0 && (num & (num - 1)) == 0 && (num & 0b01010101010101010101010101010101) != 0;】2使用正则表达式进行匹配【return Integer.toString(num, 4).matches(“10*”);】
【public static String toString(int i, int radix)//radix 为进制】
9. 判断一个数的位级表示是否不会出现连续的 0 和 1
给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
示例 1:
输入: 5
输出: True
解释:
5的二进制数是: 101
思路：对于 1010 这种位级表示的数，把它向右移动 1 位得到 101，这两个数每个位都不同，因此异或得到的结果为 1111。
|
|
10. 求一个数的补码
给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
题目描述：不考虑二进制表示中的首 0 部分。
对于 00000101，要求补码可以将它与 00000111 进行异或操作。那么问题就转换为求掩码 00000111。
可以利用 Java 的 Integer.highestOneBit() 方法来获得含有首 1 的数。
|
|
11. 实现整数的加法
a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。
递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。
|
|
12. 字符串数组最大乘积
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
思路：1.暴力2.本题主要问题是判断两个字符串是否含相同字符，由于字符串只含有小写字符，总共 26 位，因此可以用一个 32 位的整数来存储每个字符是否出现过。【例如int[] val = new int[n];中val[0]=11的话就代表1011就代表a,b,d已经出现过了】
13. 统计从 0 ~ n 每个数的二进制表示中 1 的个数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
思路:1.Integer.bitCount;2对于数字 6(110)，它可以看成是 4(100) 再加一个 2(10)，因此 dp[i] = dp[i&(i-1)] + 1;
n&(n-1) 去除 n 的位级表示中最低的那一位。
n&(-n) 得到 n 的位级表示中最低的那一位。
n-n&(~n+1) 去除 n 的位级表示中最高的那一位。