- 判断一个整数的因子数是奇数还是偶数
分析:
如果是非平方数,一定可以拆成若干对因子相乘,且每一对的因子都不同,比如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
- 判断两个链表是否相交
如果两个链表的终点一样,说明相交
网友评论