美文网首页
巧妙算法记录

巧妙算法记录

作者: 修行者12138 | 来源:发表于2020-06-21 22:24 被阅读0次
    • 判断一个整数的因子数是奇数还是偶数
      分析:
      如果是非平方数,一定可以拆成若干对因子相乘,且每一对的因子都不同,比如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
    • 判断两个链表是否相交
      如果两个链表的终点一样,说明相交

    相关文章

      网友评论

          本文标题:巧妙算法记录

          本文链接:https://www.haomeiwen.com/subject/krfqfktx.html