Go 数据结构与算法、SQL 刷题 ⌨️

// 组数不确定，组内元素数量确定，无结束输入条件
package main
import "fmt"
func main() {
    var a, b int
    for {
        //也可以用 fmt.Scan
        n, _ := fmt.Scanln(&a, &b)  
        if n == 0 {
            break
        } else {
            fmt.Printf("%d\n", a+b)
        }
    }
}

// 组数确定，组内元素数量确定
func main() {
    var t, a, b int
    fmt.Scanln(&t)
    for i := 0; i < t; i++ {
        fmt.Scanln(&a, &b)
        fmt.Printf("%d\n", a + b)
    }
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	// 输入的组数
	time, _ := reader.ReadString('\n')
	times, _ := strconv.Atoi(strings.TrimSpace(time))
	// 每一组两个元素
	for i := 0; i < times; i++ {
		// 读取 n 和 k
		line, _ := reader.ReadString('\n')
		params := strings.Fields(line)
		n, _ := strconv.Atoi(params[0])
		k, _ := strconv.Atoi(params[1])
		fmt.Println(n, k)
	}
}

// 组数不确定，组内元素确定，有结束输入条件
func main() {
    var a, b int
    for {
        fmt.Scanln(&a, &b)
        if a == 0 && b == 0 {
            break
        } else {
            fmt.Printf("%d\n", a + b)
        }
    }
}

// 组数不确定，组内元素数量确定并用数组装，有结束输入条件
func main() {
    var t int
    for {
        var sum int
        fmt.Scan(&t)
        if t == 0 {
            break
        } else {
            a := make([]int, t)
            for i := 0; i < t; i++ {
                fmt.Scan(&a[i])
                sum += a[i]
            }
        }
        fmt.Println(sum)
    }    
}

// 组数确定，组内元素数量确定
func main() {
    var t int
    fmt.Scan(&t)
    for i := 0; i < t; i++ {
        var num, sum, a int
        fmt.Scan(&num)
        for j := 0; j < num; j++ {
            fmt.Scan(&a)
            sum += a
        }
        fmt.Println(sum)
    }
}

// 组数不确定，组内元素数量确定并用数组装，无结束输入条件
func main() {
    var t int
    for {
        var sum int
        n, _ := fmt.Scan(&t)
        if n == 0 {
            break
        } else {
            nums := make([]int, t)
            for i := 0; i < t; i++ {
                fmt.Scan(&nums[i])
                sum += nums[i]
            }
        }
        fmt.Println(sum)
    }
}

// 组数不确定，组内元素数量不确定⚠️，无结束输入条件
package main
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    sc := bufio.NewScanner(os.Stdin)
    //每次读入一行
    for sc.Scan() { 
        //通过空格将他们分割，并存入一个字符串切片
        strs := strings.Split(sc.Text(), " ")  
        var sum int
        for i := range strs {
            //将字符串转换为 int
            val, _ := strconv.Atoi(strs[i])   
            sum += val
        }
        fmt.Println(sum)
    }
}

// 组数确定，组内元素数量确定
package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
    var t int
    fmt.Scanln(&t)
    strs := make([]string, t)
    for i := 0; i < t; i++ {
        fmt.Scan(&strs[i])
    }
    sort.Strings(strs)
    fmt.Println(strings.Join(strs, " "))
    
	// sc := bufio.NewScanner(os.Stdin)
	// for sc.Scan() {
	// 	strs := strings.Split(sc.Text(), " ")
	// 	sort.Strings(strs)
	// 	fmt.Println(strings.Join(strs, " "))
	// }
}

// 组数不确定，组内元素数量不确定⚠️
func main() {
    sc := bufio.NewScanner(os.Stdin)
    for sc.Scan() {
        strs := strings.Split(sc.Text(), " ")
        sort.Strings(strs)
        fmt.Println(strings.Join(strs, " "))
    }
}

// 和上面那个一样的
func main(){
    sc := bufio.NewScanner(os.Stdin)
    for sc.Scan(){
        strs := strings.Split(sc.Text(),",")
        sort.Strings(strs)
        fmt.Println(strings.Join(strs, ","))
    }
}

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func constructBinaryTree(array []int) *TreeNode {
	var root *TreeNode
	nodes := make([]*TreeNode, len(array))
	// 初始化二叉树节点
	for i := 0; i < len(nodes); i++ {
		var node *TreeNode
		if array[i] != -1 {
			node = &TreeNode{Val: array[i]}
		}
		nodes[i] = node
		if i == 0 {
			root = node
		}
	}
	// 串联节点
	for i := 0; i*2+2 < len(nodes); i++ {
		if nodes[i] != nil {
			nodes[i].Left = nodes[i*2+1]
			nodes[i].Right = nodes[i*2+2]
		}
	}
	return root
}

// 层序列遍历
func printBinaryTree(root *TreeNode) {
	res := make([][]int, 0)
	if root == nil {
		fmt.Println(res)
		return
	}
	curLevel := []*TreeNode{root}
	for len(curLevel) > 0 {
		nextLevel := make([]*TreeNode, 0)
		vals := make([]int, 0)
		for _, node := range curLevel {
			vals = append(vals, node.Val)
			if node.Left != nil {
				nextLevel = append(nextLevel, node.Left)
			}
			if node.Right != nil {
				nextLevel = append(nextLevel, node.Right)
			}
		}
		res = append(res, vals)
		curLevel = nextLevel
	}
	fmt.Println(res)
}

func main() {
	// 用 -1 来表示 nil
	array := []int{4, 1, 6, 0, 2, 5, 7, -1, -1, -1, 3, -1, -1, -1, 8}
	root := constructBinaryTree(array)
	printBinaryTree(root)
}

import "sort"

// in ascending order.
func sortExample(exampleSlice []int) {
    sort.Slice(exampleSlice, func(i, j int) bool {
        return exampleSlice[i] < exampleSlice[j]
  })
}

func sortExample(exampleSlice []int) {
    sort.Ints(exampleSlice)
}

func ReverseSlice(slice []int) {
	for i := 0; i < len(slice)/2; i++ {
		j := len(slice) - i - 1
		slice[i], slice[j] = slice[j], slice[i]
	}
}

// Example of using map for counting occurrences of elements in a slice.
func countOccurrences(nums []int) map[int]int {
	counts := make(map[int]int)
	for _, num := range nums {
		counts[num]++
	}
	return counts
}

// Example of using map for checking if an element exists.
func checkElements(numsMap map[int]int, certainValue int) bool {
	// Check if the certainValue exists in the numsMap
	_, exists := numsMap[certainValue]
	return exists
}

package main

import (
	"fmt"
)

// Stack Define a struct for the Stack
type Stack struct {
	data []interface{}
}

// Push adds an element to the top of the stack
func (s *Stack) Push(item interface{}) {
	s.data = append(s.data, item)
}

// Pop removes and returns the top element from the stack
func (s *Stack) Pop() interface{} {
	if len(s.data) == 0 {
		return nil // Stack is empty
	}
	item := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return item
}

// Peek returns the top element of the stack without removing it
func (s *Stack) Peek() interface{} {
	if len(s.data) == 0 {
		return nil // Stack is empty
	}
	return s.data[len(s.data)-1]
}

// isEmpty returns true if the stack is empty, false otherwise
func (s *Stack) isEmpty() bool {
	return len(s.data) == 0
}

func main() {
	// Create a new stack
	stack := Stack{}
	// Push elements onto the stack
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
	// Peek at the top element
	fmt.Println("Top element:", stack.Peek())
	// Pop elements from the stack
	fmt.Println("Popped element:", stack.Pop())
	fmt.Println("Popped element:", stack.Pop())
	// Check if the stack is empty
	fmt.Println("Is stack empty?", stack.isEmpty())
}

func bubbleSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	for i := 0; i < len(nums); i++ {
		for j := 0; j < len(nums)-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
	return nums
}

/* 快速排序 */
func quickSort(nums []int, left, right int) {
	// 子数组长度为 1 时终止递归
	if left >= right {
		return
	}
	// 哨兵划分
	pivot := partition(nums, left, right)
	// 递归左子数组、右子数组
	quickSort(nums, left, pivot-1)
	quickSort(nums, pivot+1, right)
}

/* 哨兵划分 */
func partition(nums []int, left, right int) int {
	// 以 nums[left] 为基准数
	i, j := left, right
	for i < j {
		for i < j && nums[j] >= nums[left] {
			j-- // 从右向左找首个小于基准数的元素
		}
		for i < j && nums[i] <= nums[left] {
			i++ // 从左向右找首个大于基准数的元素
		}
		// 元素交换
		nums[i], nums[j] = nums[j], nums[i]
	}
	// 将基准数交换至两子数组的分界线
    // 此时 i 位置上的值并不会比基准数大
	nums[i], nums[left] = nums[left], nums[i]
	return i // 返回基准数的索引
}

// 查找两个链表中最长的公共连续片段
func findMaxCommonSegment(head1 *ListNode, head2 *ListNode) []int {
	list1 := linkedListToList(head1)
	list2 := linkedListToList(head2)

	n := len(list1)
	m := len(list2)

	// 创建 DP 表
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m+1)
	}

	maxLen := 0  // 记录最长公共片段的长度
	endIdx := -1 // 记录最长公共片段的结束位置

	// 动态规划填表
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if list1[i-1] == list2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				if dp[i][j] > maxLen {
					maxLen = dp[i][j]
					endIdx = i - 1
				}
			}
		}
	}

	// 如果没有公共片段，返回 -1
	if maxLen == 0 {
		return []int{-1}
	}

	// 获取最长公共片段
	startIdx := endIdx - maxLen + 1
	return list1[startIdx : endIdx+1]
}

// 将链表转换为数组
func linkedListToList(head *ListNode) []int {
	var list []int
	for head != nil {
		list = append(list, head.Val)
		head = head.Next
	}
	return list
}

package main

import (
	"fmt"
	"math"
)

type Node struct {
	x, y      int  // 当前节点的坐标
	cost      int  // 到达该节点的开销
	visitedC  bool // 是否访问过检查点
}

var directions = [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func inBounds(x, y, N, M int) bool {
	return x >= 0 && x < N && y >= 0 && y < M
}

// 主函数：最短路径求解
func findMinCostPath(grid [][]string, N, M int) int {
	var startX, startY, endX, endY int

	// 构建cost图
	costGrid := make([][]int, N)
	for i := 0; i < N; i++ {
		costGrid[i] = make([]int, M)
		for j := 0; j < M; j++ {
			if grid[i][j] == "S" {
				startX, startY = i, j
			} else if grid[i][j] == "E" {
				endX, endY = i, j
			} else if grid[i][j] == "B" {
				costGrid[i][j] = math.MaxInt32 // 阻塞点不可达
			} else if grid[i][j] == "C" {
				costGrid[i][j] = 0 // 检查点本身无需额外成本
			} else {
				fmt.Sscanf(grid[i][j], "%d", &costGrid[i][j])
			}
		}
	}

	// 定义 BFS 队列
	queue := []Node{{startX, startY, 0, false}}

	// 记录访问状态和最小成本
	visited := make([][][]bool, N)
	minCost := make([][][]int, N)
	for i := range visited {
		visited[i] = make([][]bool, M)
		minCost[i] = make([][]int, M)
		for j := range visited[i] {
			visited[i][j] = make([]bool, 2) // 记录是否访问过该点，分为是否经过检查点的两种状态
			minCost[i][j] = []int{math.MaxInt32, math.MaxInt32}
		}
	}
	visited[startX][startY][0] = true
	minCost[startX][startY][0] = 0

	// 开始 BFS
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		x, y, cost, visitedC := node.x, node.y, node.cost, node.visitedC

		// 到达终点并且经过了检查点
		if x == endX && y == endY && visitedC {
			return cost
		}

		// 扩展到四个方向
		for _, dir := range directions {
			nx, ny := x+dir[0], y+dir[1]
			if !inBounds(nx, ny, N, M) || grid[nx][ny] == "B" {
				continue
			}

			newCost := cost + costGrid[nx][ny]
			newVisitedC := visitedC || grid[nx][ny] == "C"

			state := 0
			if newVisitedC {
				state = 1
			}

			// 如果新状态的代价小于当前记录的最小代价，则更新并加入队列
			if newCost < minCost[nx][ny][state] {
				minCost[nx][ny][state] = newCost
				queue = append(queue, Node{nx, ny, newCost, newVisitedC})
				visited[nx][ny][state] = true
			}
		}
	}

	// 无法找到满足条件的路径
	return -1
}

func main() {
	var N, M int
	fmt.Scan(&N, &M)

	grid := make([][]string, N)
	for i := 0; i < N; i++ {
		grid[i] = make([]string, M)
		for j := 0; j < M; j++ {
			fmt.Scan(&grid[i][j])
		}
	}

	result := findMinCostPath(grid, N, M)
	fmt.Println(result)
}