Leetcode with dani - Telegram 频道 @leetcodeq 的统计与分析

1 257

I earned over $ 50 OI. Net from this Airdrop after I joined🎁 It will be listed on Binance on 11th June. Click the link below to join the Airdrop and claim your free IO Tokens into your wallet💯 https://t.me/Ionet_airdrop_bot?start=r0073312635 Join now and thank me later💪

1 257

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums)-1
        while(left<=right):
            mid = (left+right)//2
            if nums[mid] <= nums[mid-1]:
                return nums[mid]
            elif nums[mid] >= nums[left] and nums[left] >nums[left-1]:
                left = mid + 1
            else:
                right = mid -1

1 257

153. Find Minimum in Rotated Sorted Array #leet_code_Q10 #Medium #binary_search #Q_153 Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time. Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. Example 3: Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

1 257

Which topic should we cover next?

Anonymous voting

1 257

In python, What does the join () method do ?

Anonymous voting

1 257

Here is the Python implementation of the above approach:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        left, right = 2, x // 2
        ans = 0
        
        while left <= right:
            mid = (left + right) // 2
            num = mid * mid
            
            if num > x:
                right = mid - 1
            else:
                ans = mid
                left = mid + 1
        
        return ans

### Complexity Analysis Time complexity: O(log x) - This is due to the binary search algorithm, which cuts the search space in half with each iteration. Space complexity: O(1) - We are using a constant amount of space regardless of the input size. Only a few integer variables are used. This solution efficiently finds the square root of a non-negative integer x rounded down to the nearest integer using binary search.

1 257

Here is the Python implementation of the above approach:

```python class Solution: def mySqrt(self, x: int) -> int: if x < 2: return x left, right = 2, x // 2 ans = 0 while left <= right: mid = (left + right) // 2 num = mid * mid if num > x: right = mid - 1 else: ans = mid left = mid + 1 return ans ```

### Complexity Analysis Time complexity: O(log x) - This is due to the binary search algorithm, which cuts the search space in half with each iteration. Space complexity: O(1) - We are using a constant amount of space regardless of the input size. Only a few integer variables are used. This solution efficiently finds the square root of a non-negative integer x rounded down to the nearest integer using binary search.

1 257

👋 Hey Everyone, here's the solution to yesterday's question. 69. Sqrt(x) Overview Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. Approach: Binary Search Intuition To find the integer square root of a number x efficiently, we can use the binary search algorithm. The idea is to narrow down the range [0, x] by comparing the mid-point's square with x. This helps us zero in on the integer part of the square root without having to check every number. Binary search is efficient because it repeatedly divides the search interval in half, making it a logarithmic time complexity algorithm. Algorithm 1. If x is less than 2, return x because the square root of 0 is 0, and the square root of 1 is 1. 2. Initialize two pointers, left and right, to 2 and x // 2, respectively. We start from 2 because any number less than 2 is already handled by the first step. 3. Perform a binary search: - Calculate the mid-point: mid = (left + right) // 2. - Compute the square of mid. - If mid^2 is greater than x, adjust the right pointer to mid - 1 to search the left half. - If mid^2 is less than or equal to x, adjust the left pointer to mid + 1 to search the right half. Also, update the variable ans to mid because mid might be the answer. 4. When the loop ends, ans will hold the largest integer whose square is less than or equal to x. 5. Return ans.

1 257

jknkjn

Anonymous voting

1 257

Hey there! How did you do on the sqrt problem?

Anonymous voting

1 257

dont use built-in function 😅

1 257

69. Sqrt(x) #binary_search #Easy #leet_code_Q9 Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python. Example 1: Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2. Example 2: Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned

1 257

1 257

In python, what does the enumerate() function do?

Anonymous voting

1 257

I will be posting python question's daily beside leetcode question

1 257

new comers hands up 🙌

1 257

Approach 2: using Binary Search :

class Solution: def arrangeCoins(self, n: int) -> int: left = 1 right = n while (left <= right): mid = (left + right) // 2 total =( (mid) * (mid + 1) )/ 2 if total == n: return mid if total >n: right = mid - 1 else: left = mid + 1 return left - 1

1 257

Approach 1 : using Brute Force Method Answer :

 class Solution:
    def arrangeCoins(self, n: int) -> int:
        while (True):
            i =  1
            total =( (i) * (i + 1) )/ 2
            if total > n:
                return i-1:
           else:  i+=1