leetcode 查找和排序 Python

二分法

69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。

class Solution:

    def mySqrt(self, x):
        if x < 0:
            raise Exception('不能输入负数')
        if x == 0:
            return 0
        # 起始的时候在 1 ，这可以比较随意设置
        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return int(cur)

922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

提示：
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        odd = []
        even = []
        for i in range(len(A)):
            if A[i]%2:
                odd.append(A[i])
            else:
                even.append(A[i])
        j = k = 0
        for i in range(len(A)):
            if i%2:
                A[i] = odd[j]
                j += 1
            else:
                A[i] = even[k]
                k += 1
        return A
        

class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        new_arry = []
        Ou_num = [A[i] for i in range(len(A)) if A[i] % 2 == 0]
        Ji_num = [A[i] for i in range(len(A)) if A[i] % 2 != 0]
        for i in range(len(A)):
            if i % 2 == 0:
                new_arry.append(Ou_num.pop())  #注意这里不能用new_arry[i] = Ou_num.pop()
            elif i % 2 != 0:
                new_arry.append(Ji_num.pop())  # #注意这里不能用new_arry[i] = Ou_num.pop()
        return new_arry

    def sortArrayByParityII(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        ji = [i for i in A if i % 2]
        ou = [i for i in A if not i % 2]
        return [i for n in zip(ji, ou) for i in n]