11、二进制中1的个数
链接：https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8?answerType=1&f=discussion 来源：牛客网 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0， 原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1， 而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。 这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。 如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0. 那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
class Solution: def NumberOf1(self, n): count = 0 if n < 0: ''' 对于负数，最高位为1，而负数在计算机是以补码存在的，往右移，符号位不变，符号位1往右移， 最终可能会出现全1的情况，导致死循环。与0xffffffff相与(成为符数的补码形式)，就可以消除负数的影响 ''' n = n & 0xffffffff while n: count = count + 1 n = n & (n - 1) return count s = Solution() print(s.NumberOf1(5)) print(bin(5)) print(s.NumberOf1(-5)) print(bin(-5))
12、数值的整数次方
注意负数次方的处理即可
class Solution: def Power(self, base, exponent): # write code here mul = 1 if exponent == 0: return 1 if base == 0: return 0 else: if exponent > 0: for i in range(0, exponent): mul = mul * base return mul else: # print("指数为负数") for i in range(0, abs(exponent)): mul = mul * base # print(mul) return 1/mul s = Solution() b = 2.1 e = -3 r = s.Power(b, e) print(r)
13、调整数组顺序使奇数位于偶数前面
# -*- coding:utf-8 -*- class Solution1: # 开辟新数组 def reOrderArray(self, array): # write code here rst = [] for i in array: if i % 2 == 1: rst.append(i) for i in array: if i % 2 == 0: rst.append(i) return rst class Solution2: # 利用冒泡排序相对位置不变 def reOrderArray(self, array): l = len(array) flag = True while l and flag: flag = False for i in range(len(array) - 1): if array[i] % 2 == 0 and array[i + 1] % 2 == 1: t = array[i] array[i] = array[i + 1] array[i + 1] = t flag = True l -= 1 return array s = Solution2() t = [1, 2, 3, 4, 5, 6, 7, 8, 9] print(s.reOrderArray(t))
14、链表中倒数第k个节点
利用快慢节点就可以找到倒数第k个节点
# -*- coding:utf-8 -*- class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def FindKthToTail(self, head, k): # write code here t = head for i in range(k): if not t: # print("越界") return None t = t.next h = head while t: t = t.next h = h.next return h head = ListNode(1) t1 = ListNode(2) head.next = t1 t2 = ListNode(3) t1.next = t2 t3 = ListNode(4) t2.next = t3 t4 = ListNode(5) t3.next = t4 s = Solution() r = s.FindKthToTail(head, 6) print(r.val)
15、反转列表
# -*- coding:utf-8 -*- class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here if not pHead or not pHead.next: return pHead h = pHead p = pHead.next q = pHead.next.next while q: p.next = h h = p p = q q = q.next p.next = h pHead.next = None return p head = ListNode(1) head.next =None # t1 = ListNode(2) # head.next = t1 # t2 = ListNode(3) # t1.next = t2 # t3 = ListNode(4) # t2.next = t3 # t4 = ListNode(5) # t3.next = t4 # t4.next = None s = Solution() h = s.ReverseList(head) print(h.val)