Ctrl+K

编程基础01-刷题

Table of Contents

编程基础01-刷题#

二分查找#

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution(object):
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            middle = (left + right) // 2
            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1

nums = [1, 2, 3, 3, 6]
s = Solution()
print("index: {}".format(s.search(nums, 2)))
print("index: {}".format(s.search(nums, 3)))
print("index: {}".format(s.search(nums, 8)))

index: 1
index: 2
index: -1

移除元素#

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路：快慢指针，通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

class Solution(object):
    def remove_element(self, nums, val):
        """remove element"""
        fast = 0
        slow = 0
        size = len(nums)
        
        while fast < size:
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
            
        # 返回长度
        return slow

nums = [1, 1, 2, 2, 3]
s = Solution()
print("移除指定元素后，新数组的长度为：{}".format(s.remove_element(nums, 2)))

移除指定元素后，新数组的长度为：3

有序数组的平方#

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序，要求时间复杂度O(n)。

解题思路：双指针法，数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

class Solution(object):
    def sorted_squares(self, nums):
        """sorted squares"""
        size = len(nums)
        left = 0
        right = size - 1
        idx = size - 1
        res = [0] * size
        
        while left <= right:
            left_square_val = nums[left] ** 2
            right_square_val = nums[right] ** 2
            if left_square_val < right_square_val:
                res[idx] = right_square_val
                right -= 1
            else:
                res[idx] = left_square_val
                left += 1
            idx -= 1
            
        return res
    
nums = [-2, -1, 0, 1, 2, 3]
s = Solution()
print("res: {}".format(s.sorted_squares(nums)))

res: [0, 1, 1, 4, 4, 9]

206. 反转链表#

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路：双指针法

from __future__ import print_function


class Solution(object):
    def reverse_list(self, head):
        """reverse list"""
        pre = None
        cur = head
        tmp = None
        
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        return pre


class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        

a = ListNode(1, ListNode(2, ListNode(3)))


def print_list(head):
    """print list"""
    while head:
        print("{}->".format(head.val), end="")
        head = head.next
    print(None)

    
print_list(a)
s = Solution()
b = s.reverse_list(a)
print_list(b)

1->2->3->None
3->2->1->None

24. 两两交换链表中的节点#

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

class Solution(object):
    def swap_pairs(self, head):
        """swap pairs"""
        dummy = ListNode(next=head)
        cur = dummy
        
        while cur.next and cur.next.next:
            tmp1 = cur.next
            tmp2 = cur.next.next
            
            tmp1.next = tmp2.next
            tmp2.next = tmp1
            
            cur.next = tmp2
            cur = cur.next.next
        
        return dummy.next

    
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        

a = ListNode(1, ListNode(2, ListNode(3)))


def print_list(head):
    """print list"""
    while head:
        print("{}->".format(head.val), end="")
        head = head.next
    print(None)
    

print_list(a)
s = Solution()
b = s.swap_pairs(a)
print_list(b)

1->2->3->None
2->1->3->None

203. 移除链表元素#

给你一个链表的头节点head和一个整数val ，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点 。

解题思路：设置虚拟头节点，原链表所有的节点都可以按照统一的方式进行处理

class Solution(object):
    def remove_elements(self, head, val):
        """remove elements"""
        dummy = ListNode(next=head)
        cur = dummy
        
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        
        return dummy.next

a = ListNode(1, ListNode(2, ListNode(3)))


def print_list(head):
    """print list"""
    while head:
        print("{}->".format(head.val), end="")
        head = head.next
    print(None)
    

print_list(a)
s = Solution()
b = s.remove_elements(a, 3)
print_list(b)

1->2->3->None
1->2->None

长度最小的子数组#

给定一个含有 n 个正整数的数组和一个正整数 target **。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0 。

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        size = len(nums)
        left = 0
        right = 0
        cur_sum = 0
        min_len = float('inf')
        while right < size:
            cur_sum += nums[right]
            while cur_sum >= target:
                sub_length = right - left + 1
                min_len = sub_length if sub_length < min_len else min_len
                cur_sum -= nums[left]
                left += 1
            right += 1
        return min_len if min_len != float('inf') else 0
    

a = [1, 2, 2, 1, 3, 6]
s = Solution()
print("min len: {}".format(s.minSubArrayLen(4, a)))

min len: 1
Contents