Day 44

第160题:

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

在节点 c1 开始相交。

1、可以暴力遍历B的每个节点是否有和A中地址相同的,有则返回结果。

  

2、还可以将A链表的所有节点地址都存入哈希表,然后遍历B内节点看是否节点地址再哈希表中存在,存在就返回地址。

  

 3、用两个指针p,q分别指向A和B的头节点,当p先到达A的结尾时,将p指向B的头部;

  同理当q到达B的结尾时,将q指向A的头部,这样循环遍历,当p和q指向同一地址时,这就时A和B的相交节点。

  

 第171题:

给定一个Excel表格中的列名称,返回其相应的列序号。(来自LeetCode)

 1、直接按照二十六进制累加每一位的和。

  

第172题:

给定一个整数 n,返回 n! 结果尾数中零的数量。(来自LeetCode)

1、可以直接暴力求出n的阶乘的解sum,然后用sum/10来判断尾数中0的个数;

  但是这样很容易溢出,且时间复杂度为O(n);

  那么只能从数学方面分析,每个数当它乘10(2*5)的时候它的尾数就会加一个0;

  那么计算尾数有多少个0,直接判断这个阶乘内有多少个可以相乘为10的数即可;

  像5!=1*2*3*4*5,其中只有2*5=10 ,说明尾数只有一个0;

  再比如10!=1*2*3*4*5*6*7*8*9*10=1*2*3*(2*2)*5*(2*3)*7*(2*4)*9*(2*5),从中可以得出每个阶乘中判断2和5的个数时2的个数一定大于5的个数;

  所以我们判断时就直接以5的个数来计算10 的个数;

  但是后面发现在5的幂数中会包含多个5,例如25=5*5,125=5*5*5……;

  写程序的话,如果直接按照上边的式子计算,分母可能会造成溢出。所以算 n / 25 的时候,我们先把 n 更新,n = n / 5,然后再计算 n / 5 即可。后边的同理。

  

原文地址:https://www.cnblogs.com/liang-yi-/p/13511076.html