巧妙算法记录
2020-06-21 本文已影响0人
修行者12138
- 判断一个整数的因子数是奇数还是偶数
分析：
如果是非平方数，一定可以拆成若干对因子相乘，且每一对的因子都不同，比如6可以拆分为1 * 6和2 * 3，共4个因子，因此非平方数的因子数一定是偶数。
如果是平方数，一定有一对因子是相同的，比如4可以拆分为1 * 4和2 * 2，共3个因子，因此平方数的因子数一定是奇数。
- 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素（leetcode 多数元素）
分析：
思路一
先对数组排序，排序之后，下标为n/2的元素，一定就是多数元素。
思路二
摩尔投票法
- 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串，所有输入均为小写字母（leetcode 字母异位词分组）
分析：
定义一个Map<String, List<String>> map，key为同一组字母异位词的标识，value为可以组成字母异位词的字符串的集合，关键在于怎么定义key，即怎么标识一组字符串是字母异位词。
思路一：
对字符串按字典序排序，排序结果相同即为字母异位词，快排时间复杂度O(nlogn)
思路二：
题目给定了字符串的范围是纯小写字母，所以可以拼接出这样的一个字符串作为map的key: #A#B#C#....#Z，A/B/C...Z分别表示字符串中a/b/c...z字母出现的次数，时间复杂度O(n)，优于思路一
思路三：
取前26个质数组成一个质数数组，以字符串abc和cba为例，求每个字母对应的质数的和，即可作为map的key，时间复杂度也是O(n)，但数字相加的开销优于字符串拼接的开销，因此优于思路二
- 如果两个整数相等，异或结果为0，也就是可以用异或来比较两个整数是否相等。
- 组合公式
C(n, 0) + C(n, 1) + C(n, 2) + ... + C(n, n) = 2n
证明：
有一个大小为n，不含重复元素的集合，公式的两边都可以表示这个集合的子集的数量（即这个集合有多少个不同的子集，只要元素相同就算同一个子集，即使顺序不同），前者是枚举所有可能（取0个，取1个，取2个...），后者是每个元素都有取或不取两种可能，所以是2n
- 判断两个链表是否相交
如果两个链表的终点一样，说明相交
