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

簡單題 小紅的校招筆試

1. 輸入處理：

   • 接收一個整數(shù) n，表示數(shù)組長度
   • 創(chuàng)建一個長度為 n 的整數(shù)數(shù)組 a
   • 使用循環(huán)讀入 n 個整數(shù)

2. 計算排名：

   • 設(shè)置初始排名 rk = 1
   • 遍歷數(shù)組，如果發(fā)現(xiàn)比第一個數(shù)（a[0]）大的數(shù)，就給排名加1
   • 這樣可以得到第一個數(shù)的排名

3. 判斷條件：

   • 特殊情況：如果 n = 1，直接輸出 "Yes"
   • 一般情況：如果排名 rk > n/2（即第一個數(shù)排在后半段），輸出 "No"
   • 否則（即第一個數(shù)排在前半段），輸出 "Yes"

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	rk := 1
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		if a[0] < a[i] {
			rk++
		}
	}
	if n == 1 {
		fmt.Println("Yes")
		return
	}
	if rk > n/2 {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}

中等題 小紅的區(qū)間查詢

1. 數(shù)據(jù)輸入部分:

   • 讀入兩個整數(shù) n 和 q，分別表示數(shù)組長度和操作次數(shù)
   • 創(chuàng)建一個長度為 n+1 的數(shù)組 a（注意索引從1開始使用）
   • 循環(huán)讀入 n 個數(shù)作為數(shù)組的初始值

2. 操作處理部分:

   • 執(zhí)行 q 次操作，每次讀入三個整數(shù)：
     • op：操作類型（1或2）
     • id：操作相關(guān)的位置/范圍
     • x：操作的值

3. 兩種操作類型:

   • 操作1（修改操作）：

     • 當(dāng) op = 1 時
     • 將數(shù)組位置 id 的值修改為 x

   • 操作2（查詢操作）：

     • 當(dāng) op = 2 時
     • 統(tǒng)計數(shù)組從位置1到位置id中等于x的元素個數(shù)
     • 輸出統(tǒng)計結(jié)果

package main

import "fmt"

func main() {
	var n, q int
	fmt.Scan(&n, &q)
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
	}
	for i := 0; i < q; i++ {
		var op, id, x int
		fmt.Scan(&op, &id, &x)
		switch op {
		case 1:
			a[id] = x
		case 2:
			cnt := 0
			for j := 1; j <= id; j++ {
				if a[j] == x {
					cnt++
				}
			}
			fmt.Println(cnt)
		}
	}
}

困難題 最長回文子序列

1. 狀態(tài)定義

   • 我們使用二維數(shù)組 dp[i][j] 來表示字符串 s 中從第 i 個字符到第 j 個字符之間的最長回文子序列的長度。

2. 轉(zhuǎn)移方程

   1. 對于任意情況，dp[i][j] = max(dp[i+1][j], dp[i][j-1])，最長回文子序列要么在 s[i+1..j] 中，要么在 s[i..j-1] 中。
   2. 如果 s[i] == s[j]，存在 dp[i][j] = dp[i+1][j-1] + 2 ，如果兩端字符相等，那么它們一定可以作為回文的一部分，而中間部分的狀態(tài)由 dp[i+1][j-1] 決定。

3. 初始化

   • 對于單個字符的情況，即 dp[i][i]，顯然最長回文子序列就是該字符本身，因此 dp[i][i] = 1。

package main

import "fmt"

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

func main() {
	var s string
	fmt.Scan(&s)
	n := len(s)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}
	for l := 2; l <= n; l++ {
		for i := 0; i+l-1 < n; i++ {
			j := i + l - 1
			dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			if s[i] == s[j] {
				dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2)
			}
		}
	}
	fmt.Println(dp[0][n-1])
}