算法 面试题练习 1️⃣

class Solution:
    def find_left(self, score: List[int], target: int) -> int:
        left, right = 0, len(score) - 1
        while left <= right:
            mid = (left + right) // 2
            if score[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left 
    def find_right(self, score: List[int], target: int) -> int:
        left, right = 0, len(score) - 1
        while left <= right:
            mid = (left + right) // 2
            if score[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right 
    
    def countTarget(self, scores: List[int], target: int) -> int:
        left = self.find_left(scores, target)
        right = self.find_right(scores, target)
        return right - left + 1 if left <= right else 0

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        min_len = float("inf")
        left = 0
        current_sum = 0
        for right in range(n):
            current_sum += nums[right]
            while current_sum >= target:
                min_len = min(min_len, right - left + 1)
                current_sum -= nums[left]
                left += 1
        
        return min_len if min_len != float("inf") else 0

class Solution:
    def expand(self, left, right, s):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1 
    
    def longestPalindrome(self, s: str) -> str:
        start = 0
        end = 0
        for i in range(len(s)):
            l1, r1 = self.expand(i, i, s)
            l2, r2 = self.expand(i, i+1, s)
            if r1 - l1 > end - start:
                start, end = l1, r1
            if r2 - l2 > end - start:
                start, end = l2, r2
        return s[start:end+1]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        cnt = defaultdict(int)
        left = 0
        for right, x in enumerate(s):
            cnt[x]+=1
            while cnt[x] > 1:
                cnt[s[left]]-=1
                left+=1
            ans = max(ans,right - left +1)
        return ans

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head 
        while fast and fast.next:
            slow = slow.next 
            fast = fast.next.next 
            if fast == slow:
                return True
        return False

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:  
                while slow is not head:  
                    slow = slow.next
                    head = head.next
                return slow
        return None

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idx = {}
        for i ,x in enumerate(nums):
            if target - x in idx:
                return [idx[target-x],i]
            idx[x] = i