活動(dòng)地址： ?？痛赫兴㈩}訓(xùn)練營 - 編程打卡活動(dòng)

簡單題 小紅的多彩糖葫蘆

1. 輸入處理：

   • 讀取一個(gè)字符串 s，每個(gè)字符代表一個(gè)糖葫蘆的顏色

2. 核心算法：

   • 從第一個(gè)糖葫蘆開始遍歷 (i 從 0 開始)
   • 對于每個(gè)位置 i，檢查當(dāng)前糖葫蘆的顏色是否和前一個(gè)相同
   • 如果發(fā)現(xiàn)相同顏色（s[i] == s[i-1]），則停止吃糖葫蘆

3. 結(jié)果輸出：

   • 如果找到相同顏色的相鄰糖葫蘆，輸出此時(shí)的位置 i（表示吃了多少個(gè)糖葫蘆）
   • 如果遍歷完整串都沒有找到相同顏色，輸出字符串長度（表示可以把整串都吃完）

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	for i := 0; i < len(s); i++ {
		if i != 0 && s[i] == s[i-1] {
			fmt.Println(i)
			return
		}
	}
    fmt.Println(len(s))
}

中等題 小紅的好數(shù)

1. 輸入整數(shù) k
2. 定義了一個(gè) check 函數(shù)來判斷一個(gè)字符串是否每個(gè)字符都不重復(fù)：
   • 使用 map 記錄已出現(xiàn)的字符
   • 如果發(fā)現(xiàn)重復(fù)字符返回 false，否則返回 true
3. 主要邏輯：
   • 從 98765 到 1234 遞減遍歷所有 5 位數(shù)
   • 將每個(gè)數(shù)字格式化為 5 位字符串（不足位補(bǔ) 0）
   • 使用 check 函數(shù)檢查是否每位數(shù)字都不同
   • 如果是不重復(fù)的數(shù)字，k 減 1
   • 當(dāng) k 變?yōu)?0 時(shí)，輸出當(dāng)前數(shù)字并結(jié)束程序

package main

import "fmt"

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

func main() {
	var n int
	fmt.Scan(&n)
	mp := make(map[int]int)
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		mp[a]++
	}
	var ans int
	for _, v := range mp {
		ans = max(ans, v)
	}
	if ans == n {
		fmt.Println(n)
	} else {
		fmt.Println(ans + 1)
	}
}

困難題 滑雪

1. 狀態(tài)定義：
   • 定義一個(gè)二維數(shù)組dp，其中dp[x][y]表示從位置(x, y)出發(fā)，能夠走的最長遞減路徑長度。
   • 初始時(shí)，所有dp[x][y]的值為0，表示尚未計(jì)算。
2. 轉(zhuǎn)移方程：
   • 對于當(dāng)前位置(x, y)，可以向四個(gè)方向移動(dòng)：上、下、左、右。
   • 如果從(x, y)移動(dòng)到(xx, yy)滿足a[x][y] > a[xx][yy]（即目標(biāo)位置的值更?。?，則更新dp[x][y]為：
   • 這意味著當(dāng)前路徑長度等于目標(biāo)路徑長度加1。
3. 邊界條件：
   • 如果越界（即xx < 0、xx >= n、yy < 0或yy >= m），則跳過該方向。
   • 如果dp[x][y]已經(jīng)計(jì)算過（即dp[x][y] != 0），直接返回結(jié)果，避免重復(fù)計(jì)算（記憶化搜索）。
4. DFS與記憶化搜索：
   • 使用深度優(yōu)先搜索（DFS）遞歸地計(jì)算每個(gè)位置的最長路徑長度。
   • 在遞歸過程中，通過dp數(shù)組記錄已經(jīng)計(jì)算過的結(jié)果，避免重復(fù)計(jì)算，從而提高效率。
5. 主邏輯：
   • 遍歷矩陣中的每一個(gè)點(diǎn)(i, j)，調(diào)用dfs(i, j)計(jì)算從該點(diǎn)出發(fā)的最長路徑。
   • 記錄全局最大值ans，即所有起點(diǎn)中最長路徑的長度。

package main

import (
	"fmt"
)

var (
	n, m int
	a    [][]int
	dp   [][]int
	dx   = []int{0, 0, 1, -1}
	dy   = []int{1, -1, 0, 0}
)

func dfs(x, y int) int {
	if dp[x][y] != 0 {
		return dp[x][y]
	}
	dp[x][y] = 1
	for i := 0; i < 4; i++ {
		xx, yy := x+dx[i], y+dy[i]
		if xx < 0 || xx >= n || yy < 0 || yy >= m {
			continue
		}
		if a[x][y] > a[xx][yy] {
			dp[x][y] = max(dp[x][y], dfs(xx, yy)+1)
		}
	}
	return dp[x][y]
}

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

func main() {
	fmt.Scan(&n, &m)
	a = make([][]int, n)
	dp = make([][]int, n)
	for i := range a {
		a[i] = make([]int, m)
		dp[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Scan(&a[i][j])
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			ans = max(ans, dfs(i, j))
		}
	}
	fmt.Println(ans)
}