蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Array Partition I, Number Complement

发表于 更新于 分类于 阅读次数： Valine：

Array Partition I

题目大意

给定一个长度为2n的整数数组，将数组分成n组，求每组数的最小值之和的最大值

##解题思路
偶数数组，排序后奇数位置所有相加就可以

代码

1
2
3
4
5
6
7
8
class Solution(object):

    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(sorted(nums)[::2])

我提交的

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        # print nums
        total = 0
        for i in range(0, len(nums), 2):
        	total += nums[i]
        return total

总结

可以看到答案使用了sorted（）以及切片，值得学习。尤其是切片，我平常不怎么用。

Number Complement

题目大意

给定一个正整数，输出其补数。
##解题思路
二进制位取反

代码

1
2
3
4
5
6
class Solution(object):
    def findComplement(self, num):
        i = 1
        while i <= num:
            i = i << 1
        return (i - 1) ^ num

我提交的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        list_num = []
        list_num = list(str(bin(num)))
        # print list_num
        for i in range(len(list_num)-2):
            if list_num[i+2] == '1':
                list_num[i+2] = '0'
            else:
                list_num[i+2] = '1'
        # print list_num
        num_str = ''.join(list_num)
        return int(num_str,2)

总结

我提交的

  1. 思路是int-bin-list-按位数1、0转换，最后list-str-int
  2. int(num_str,2),是将字符串以二进制转为整数
  3. num_str = ‘’.join(list_num) 将list转为拼接后的str。

    代码

    左移位，i从1开始，到2、4、8，假设输入还是5，那么到8之后，减1，得到7。
    7^num: 111^101=010=2
    简单来说就是用1，111，1111，11111去和实际num的二进制做异或运算，这样就能取到反。
    一来说明python取反的~并不能解决这道题目，而来说明压根没好好想啊