代码随想录算法训练营第二天 | 209、59、kama58、kama44

209. 长度最小的子数组

package main

func minSubArrayLen(target int, nums []int) int {
    n := len(nums)
    left, sum := 0, 0
    minLen := n + 1 // 初始化为不可能的大值

    for right := 0; right < n; right++ {
        sum += nums[right]
        // 当 sum >= target 时，尝试缩小窗口
        for sum >= target {
            currentLen := right - left + 1
            if currentLen < minLen {
                minLen = currentLen
            }
            sum -= nums[left]
            left++
        }
    }

    if minLen == n+1 {
        return 0
    }
    return minLen
}

59. 螺旋矩阵 II

package main

func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    start := 1
    loop := 0

    for loop < n/2 {
        // 填充顶行（左→右）
        for j := loop; j < n-loop; j++ {
            matrix[loop][j] = start
            start++
        }
        // 填充右列（上→下）
        for i := loop + 1; i < n-loop; i++ {
            matrix[i][n-loop-1] = start
            start++
        }
        // 填充底行（右→左）
        for j := n - loop - 2; j >= loop; j-- {
            matrix[n-loop-1][j] = start
            start++
        }
        // 填充左列（下→上）
        for i := n - loop - 2; i > loop; i-- {
            matrix[i][loop] = start
            start++
        }
        loop++
    }

    // 处理 n 为奇数时的中心元素
    if n%2 != 0 {
        mid := n / 2
        matrix[mid][mid] = start
    }

    return matrix
}

kama58. 区间和

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)

    // 读取数组长度 n
    scanner.Scan()
    n, _ := strconv.Atoi(scanner.Text())

    // 读取数组元素
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        scanner.Scan()
        num, _ := strconv.Atoi(scanner.Text())
        arr[i] = num
    }

    // 构建前缀和数组
    prefix := make([]int, n+1)
    for i := 1; i <= n; i++ {
        prefix[i] = prefix[i-1] + arr[i-1]
    }

    // 处理查询
    for scanner.Scan() {
        line := scanner.Text()
        line = strings.TrimSpace(line)
        if line == "" {
            continue
        }
        parts := strings.Split(line, " ")
        a, _ := strconv.Atoi(parts[0])
        b, _ := strconv.Atoi(parts[1])
        sum := prefix[b+1] - prefix[a]
        fmt.Println(sum)
    }
}

kama44. 开发商购买土地

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)

    // 读取 n 和 m
    scanner.Scan()
    n, _ := strconv.Atoi(scanner.Text())
    scanner.Scan()
    m, _ := strconv.Atoi(scanner.Text())

    // 读取矩阵元素
    grid := make([][]int, n)
    for i := 0; i < n; i++ {
        grid[i] = make([]int, m)
        for j := 0; j < m; j++ {
            scanner.Scan()
            num, _ := strconv.Atoi(scanner.Text())
            grid[i][j] = num
        }
    }

    // 计算总和
    total := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            total += grid[i][j]
        }
    }

    // 预处理横向的前缀和
    rowSum := make([]int, n)
    for i := 0; i < n; i++ {
        sum := 0
        for j := 0; j < m; j++ {
            sum += grid[i][j]
        }
        rowSum[i] = sum
    }
    rowPrefix := make([]int, n+1)
    for k := 1; k <= n; k++ {
        rowPrefix[k] = rowPrefix[k-1] + rowSum[k-1]
    }

    // 预处理纵向的前缀和
    colSum := make([]int, m)
    for j := 0; j < m; j++ {
        sum := 0
        for i := 0; i < n; i++ {
            sum += grid[i][j]
        }
        colSum[j] = sum
    }
    colPrefix := make([]int, m+1)
    for l := 1; l <= m; l++ {
        colPrefix[l] = colPrefix[l-1] + colSum[l-1]
    }

    minDiff := 1 << 30

    // 处理横向切割
    if n > 1 {
        for k := 1; k <= n-1; k++ {
            sum := rowPrefix[k]
            diff := abs(2*sum - total)
            if diff < minDiff {
                minDiff = diff
            }
        }
    }

    // 处理纵向切割
    if m > 1 {
        for l := 1; l <= m-1; l++ {
            sum := colPrefix[l]
            diff := abs(2*sum - total)
            if diff < minDiff {
                minDiff = diff
            }
        }
    }

    fmt.Println(minDiff)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}