代码随想录

数组

二分查找

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

arr = [5,7,7,8,8,10]  
s = Solution()  
s.search(arr, 8)

移除元素

数组的地址是连续的，如果需要删除元素，则需要对其他元素进行缩进，双指针，其中一个指针用于遍历全部元素，另一个指针用于记录需要替换的地址。

class Solution(object):  
    def removeElement(self, nums, val):  
        """  
        :type nums: List[int]        
        :type val: int        
        :rtype: int  
        """        size = len(nums)  
        fast = 0  # 快指针  
        slow = 0  # 慢指针  
        while fast < size:  
            if nums[fast] != val:  
                nums[slow] = nums[fast]  
                slow += 1  
            fast += 1  
        return slow  
  
  
arr = [1, 5, 2, 6, 2, 1, 2, 2, 9]  
ss = Solution()  
ss.removeElement(arr, 2)  
print(arr)

有序数组的平方

因为是有序数组，数组平方后最大值只会在数组的两边，采用双指针，指向数组的两边，哪边大哪边的指针向中间前进一步

class Solution(object):  
    def sortedSquares(self, nums: list[int]) -> list[int]:  
  
        """  
        :type nums: List[int]        
        :rtype: List[int]  
        """        len_arr = len(nums)  
        start = 0  
        end = len_arr - 1  
        res = [0] * len_arr  
        i = 0  
        while start <= end:  
            n1 = nums[start]**2  
            n2 = nums[end]**2  
            if n2 > n1:  
                x = len_arr - 1 - i  
                res[len_arr - 1 - i] = n2  
                end -= 1  
            else:  
                y = len_arr - 1 - i  
                res[len_arr - 1 - i] = n1  
                start += 1  
            i += 1  
        return res  
  
  
arr = [-4, -1, 0, 3, 10]  
S = Solution()  
da = S.sortedSquares(arr)  
print(da)

长度最小的子数组

使用滑动窗口的思想， 滑动窗口也是采用了双指针，一个指针指向窗口的结尾，一个指针指向了窗口的开始，通过 for 循环来改变窗口的结尾，如果窗口内的数据和大于目标值，则通过改变窗口的起始指针来不断缩小窗口

class Solution(object):  
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:  
        """  
        :type target: int        
        :type nums: List[int]        
        :rtype: int  
        """        len_arr = len(nums)  
        start = 0  
        end = 0  
        sum_n = 0  
        min_len = len_arr + 1  
        while end < len_arr:  
            sum_n += nums[end]  
            while sum_n >= target:  
                min_len = min(min_len, end - start + 1)  
                sum_n -= nums[start]  
                start += 1  
            end += 1  
        return min_len if min_len != len_arr + 1 else 0  
  
  
arr = [1,1,1,1,1,1,1,1]  
tar = 15  
S = Solution()  
da = S.minSubArrayLen(tar, arr)  
print(da)

螺旋矩阵

关键在于采用统一的规则来控制边界，这里采用左闭右开的方法，‘

class Solution(object):  
    def generateMatrix(self, n):  
        """  
        :type n: int        
        :rtype: List[List[int]]  
        """        
        if n <= 0:  
            return []  
        matrix = [[0]*n for _ in range(n)]  
        top, bottom, left, right = 0, n-1, 0, n-1 # 将边界统一为数组0-(n-1)的形式
        x = 1  
        while top <= bottom and left <= right:  
            for i in range(left, right+1-1): # 控制上边界,+1 表示是从left-right完整的一圈，-1 表示完整的一圈减去 1
                matrix[top][i] = x  
                x += 1  
            for i in range(top, bottom+1-1):  
                matrix[i][right] = x  
                x += 1  
            for i in range(right, left-1+1, -1):  
                matrix[bottom][i] = x  
                x += 1  
            for i in range(bottom, top-1+1, -1):  
                matrix[i][left] = x  
                x += 1  
            top += 1  
            right -= 1  
            bottom -= 1  
            left += 1  
        if (top-1) == (bottom+1):  
            matrix[top-1][left-1] = x  
        return matrix  
  
  
da = Solution().generateMatrix(5)  
print(da)

区间和

通过一个记录累加值的数组来求区间和

def main():  
    data = input().split()  
    n = int(data[0])  
    val = data[1:(n+1)]  
    idx = data[(n+1):]  
    sum_ = 0  
    p = []  
    for v in val:  
        sum_ += int(v)  
        p.append(sum_)  
    i = 0  
    results = []  
    while i <= len(idx)-1:  
        a = int(idx[i])  
        b = int(idx[i+1])  
        i += 2  
        if a == 0:  
            sum_value = p[b]  
        else:  
            sum_value = p[b] - p[a - 1]  
        results.append(sum_value)  
    for result in results:  
        print(result)  
  
  
main()

开发商买土地

def main():  
    data = input().split()  
    m, n = int(data[0]), int(data[1])  
    val = data[2:]  
    arr = []  
    for i in range(m):  
        row = []  
        for j in range(n):  
            row.append(int(val[i*n+j]))  
        arr.append(row)  
    print(arr)  
    row_sum = []  
    col_sum = []  
    sum_tmp = 0  
    for r in range(m):  
        sum_tmp += arr_add(arr[r])  
        row_sum.append(sum_tmp)  
    sum_tmp = 0  
    for c in range(n):  
        sum_tmp += arr_add([r[c] for r in arr])  
        col_sum.append(sum_tmp)  
    print(row_sum)  
    print(col_sum)  
    min_cha = row_sum[-1]  
    for r in range(0, m-1):  
        a = row_sum[r]  
        b = row_sum[-1] - a  
        min_cha = min(min_cha, abs(b - a))  
    for c in range(0, n-1):  
        a = col_sum[c]  
        b = col_sum[-1] - a  
        min_cha = min(min_cha, abs(b - a))  
    print(min_cha)  
  
  
def arr_add(arr):  
    res = 0  
    for v in arr:  
        res += v  
    return res  
  
  
main()