leecode-69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1
2
3
4
5
6
7
8
9
10
示例 1:

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

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：sarizzm time:2021/1/6 0006
class Solution:
    def mySqrt(self, x):
        # if x ==0:
        #     return 0
        # length = len(str(x))//2
        # nums = 10**length
        # if nums * nums <= x:
        #     while nums * nums <= x:
        #         nums += 1
        #     return nums-1
        # else:
        #     while nums * nums > x:
        #         nums -= 1
        #     return nums

        l, r, ans = 0, x, -1

        while l<=r:
            mid = (r+l) //2
            print(l, r)
            if mid**2 <= x:
                ans = mid
                l = mid+1
            else:
                r = mid-1
        return ans




# print(Solution().mySqrt(5))
# print(Solution().mySqrt(4))
# print(Solution().mySqrt(9))
# print(Solution().mySqrt(10))
# print(Solution().mySqrt(100))
print(Solution().mySqrt(36))
# print(Solution().mySqrt(1000))


执行用时：2524 ms, 在所有 Python3 提交中击败了7.20%的用户

内存消耗：14.8 MB, 在所有 Python3 提交中击败了11.25%的用户

二分法模板1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1; // 注意
        while(left <= right) { // 注意
            int mid = (left + right) / 2; // 注意
            if(nums[mid] == target) { // 注意
                // 相关逻辑
            } else if(nums[mid] < target) {
                left = mid + 1; // 注意
            } else {
                right = mid - 1; // 注意
            }
        }
        // 相关返回值
        return 0;
    }
}

//作者：guanpengchn
//链接：https://leetcode-cn.com/problems/search-insert-position/solution/hua-jie-suan-fa-35-sou-suo-cha-ru-wei-zhi-by-guanp/

二分法模板1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length; // 注意
        while(left < right) { // 注意
            int mid = (left + right) / 2; // 注意
            if(nums[mid] == target) {
                // 相关逻辑
            } else if(nums[mid] < target) {
                left = mid + 1; // 注意
            } else {
                right = mid; // 注意
            }
        }
        // 相关返回值
        return 0;
    }
}

//作者：guanpengchn
//链接：https://leetcode-cn.com/problems/search-insert-position/solution/hua-jie-suan-fa-35-sou-suo-cha-ru-wei-zhi-by-guanp/