第十一天

顺时针旋转矩阵

在Go语言中，实现矩阵顺时针旋转90度的算法可以通过逐层遍历矩阵并交换元素位置来完成。以下是一个简单的Go语言实现：

package main

import "fmt"

// RotateMatrix 顺时针旋转矩阵90度
func RotateMatrix(matrix [][]int) [][]int {
    rows := len(matrix)
    cols := len(matrix[0])

    // 确保矩阵是正方形的
    if rows != cols {
        panic("Input matrix must be square")
    }

    // 采用原地旋转的方式，首先进行转置，然后反转每行
    transpose(matrix)
    reverseEachRow(matrix)

    return matrix
}

// transpose 矩阵转置
func transpose(matrix [][]int) {
    for i := 0; i < len(matrix); i++ {
        for j := i + 1; j < len(matrix[0]); j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
}

// reverseEachRow 反转每行
func reverseEachRow(matrix [][]int) {
    for row := range matrix {
        for left, right := 0, len(matrix[row])-1; left < right; left, right = left+1, right-1 {
            matrix[row][left], matrix[row][right] = matrix[row][right], matrix[row][left]
        }
    }
}

func main() {
    input := [][]int{
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
    }

    rotated := RotateMatrix(input)
    fmt.Println(rotated)
}

这段代码首先定义了一个名为RotateMatrix的函数，它接收一个整数矩阵作为输入，然后通过两个辅助函数来实现旋转操作：

1. transpose函数用于矩阵转置，即将矩阵的行变为列，列变为行。
2. reverseEachRow函数用于反转矩阵的每一行，使得矩阵顺时针旋转90度。

最后，main函数中给出了一个3x3矩阵作为示例，并展示了旋转后的结果。运行该程序，会得到一个顺时针旋转90度后的矩阵。

合并区间

合并区间是指在给定一系列的区间后，将有交集或者连续的区间合并成一个大的区间。这个问题通常可以采用排序和遍历的方式来解决，以下是一个简单的Go语言实现：

package main

import (
    "fmt"
    "sort"
)

type Interval struct {
    Start int
    End   int
}

// compareIntervals 用于对区间进行排序的比较函数
func compareIntervals(a, b *Interval) bool {
    return a.Start < b.Start
}

// mergeIntervals 合并区间
func mergeIntervals(intervals []*Interval) []*Interval {
    // 先对区间按起点进行排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i].Start < intervals[j].Start
    })

    result := make([]*Interval, 0, len(intervals))
    curr := intervals[0]

    for _, interval := range intervals[1:] {
        // 如果当前区间与新区间有交集，则扩大当前区间的终点
        if curr.End >= interval.Start {
            curr.End = max(curr.End, interval.End)
        } else {
            // 如果没有交集，则将当前区间加入结果集，并将新区间设为当前区间
            result = append(result, curr)
            curr = interval
        }
    }

    // 最后加入最后一个区间
    result = append(result, curr)

    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    intervals := []*Interval{
        {1, 3},
        {2, 6},
        {8, 10},
        {15, 18},
    }

    fmt.Println("Before merging:")
    for _, interval := range intervals {
        fmt.Printf("[%d, %d]\n", interval.Start, interval.End)
    }

    merged := mergeIntervals(intervals)

    fmt.Println("\nAfter merging:")
    for _, interval := range merged {
        fmt.Printf("[%d, %d]\n", interval.Start, interval.End)
    }
}

在这个示例中，首先对输入的区间列表按照起始点进行排序，然后遍历排序后的区间，将有交集的区间合并在一起，最后得到的就是合并后的区间列表。注意，这个示例假设输入的区间都是左闭右闭的形式，即 [start, end]。如果有特殊边界条件，比如左开右闭等，需要根据实际情况调整。