算法

求两个链表相交的节点

解题思路:链表headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点,链表 headB 的不相交部分有 b 个节点,两个链表相交的部分有 c 个节点,则有 a+c=m,b+c=n。 当链表 headA 和 headB 都不为空时,创建两个指针 pA 和 pB,初始时分别指向两个链表的头节点headA 和 headB,然后将两个指针依次遍历两个链表的每… 阅读更多 »求两个链表相交的节点

判断是否是4的幂

解题思路: 先判断是否是2的幂,参考之前的代码 然后两种解法: 如果n是4的次方的数,其二进制位表示中有且仅有1个1,这是由是否是2的幂得到的,其次1只出现在偶数位置,比如1的二进制就是1,1出现在第0位,4的二进制是100,1出现在第二位等等,因此可以构造一个32位数,1010101010…进行与运算,其所有偶数位置都为0,奇数位置都为1,这样进行与运算的时候,如果n是4的幂,其有一… 阅读更多 »判断是否是4的幂

判断数是否为2的幂

解题思路:数大于0,并且数的二进制包含1个1 n&(n-1)去掉一个1之后==0即可判断 n & (-n)=n也可判断,因为-n的二进制是n 的二进制表示的每一位取反再加上 1 1<<30表示左移30位,相当于2的30次方(左移1位扩大1倍即乘以2),然后只要判断n是否为2^30的公约数,即模是否==0。 class Solution: def isPowerOfTwo… 阅读更多 »判断数是否为2的幂

和为目标值的子矩阵个数

给一个矩阵,求子矩阵的个数,子矩阵满足和=target 解题思路: 假设矩阵有M行,N列 先确定矩阵的上边界m,0<=m<=M 再确定矩阵的下边界n,m<=n<=M 最后求每列的和,这样就得到一个list,该list中存储了每列的和(具体由上下边界确定,比如可以得到前一行的每列和,前两行的每列和,前三行的每列和等等,或者第二行的每列和,第二行到第三行的每列和,第二行到第四行… 阅读更多 »和为目标值的子矩阵个数

汉明距离

汉明距离:两个数字对应二进制位不同的位置的数目。例如:x = 1, y = 4,x->2=(0,0,0,1),y->2=(0,1,0,0),汉明距离为2 解题思路: 求两个整数的异或,d=x^y,得到了一个十进制的整数; 然后求十进制数转为二进制后有多少个1(通过d&(d-1)可以消除1个1) class Solution(object): def hammingDistanc… 阅读更多 »汉明距离