Goコーディング試験問題集
ちょうど一年前🇺🇸旅行に行った際に10時間以上飛行機の中での暇潰しにChatGPTを利用してLeetCodeの練習用の問題とGolangを用いた解答を作成してもらい意外と勉強になったので忘れた頃にもう一度挑戦するための備忘録として残します。LeetCodeの練習をGoを用いたい方向けです。初級問題は駆け出しの方の練習問題としても最適かと。
おすすめ書籍
アルゴリズム?何それ美味しいの?状態だった私にもわかりやすく実用的なアルゴリズムをイラストベースで解説してくれる本です。こちらの記事で取り上げている問題でも使用する2分探索、幅優先探索、動的計画法といったアルゴリズムを網羅的にまとめられています。
初級問題
問題1:FizzBuzz
問題: 1から100までの数字を順に出力してください。ただし、数字が3の倍数のときは「Fizz」、5の倍数のときは「Buzz」、15の倍数のときは「FizzBuzz」と出力してください。
解答例:
package main
import (
"fmt"
)
func main() {
for i := 1; i <= 100; i++ {
switch {
case i%15 == 0:
fmt.Println("FizzBuzz")
case i%3 == 0:
fmt.Println("Fizz")
case i%5 == 0:
fmt.Println("Buzz")
default:
fmt.Println(i)
}
}
}
解説: 数字をループで順にチェックし、条件に応じて適切な文字列を出力します。15の倍数(3と5の公倍数)を最初に判定することで、条件の重複を避けています。
問題2:文字列の逆転
問題: 文字列を逆順に並べ替える関数を作成してください。
解答例:
package main
import (
"fmt"
)
func reverseString(s string) string {
runes := []rune(s)
length := len(runes)
for i := 0; i < length/2; i++ {
// 先頭と末尾を交換
runes[i], runes[length-1-i] = runes[length-1-i], runes[i]
}
return string(runes)
}
func main() {
str := "hello"
fmt.Println(reverseString(str))
}
解説: 文字列をルーンスライスに変換し、先頭と末尾の文字を交換していくことで逆転させます。
問題3:リストの最小値
問題: 整数のリストから最小値を見つける関数を作成してください。
解答例:
package main
import (
"fmt"
)
func findMin(arr []int) (int, error) {
if len(arr) == 0 {
return 0, fmt.Errorf("配列が空です")
}
min := arr[0]
for _, num := range arr {
if num < min {
min = num
}
}
return min, nil
}
func main() {
arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5}
min, err := findMin(arr)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("最小値は", min, "です")
}
解説: 配列の各要素を比較し、最小の値を更新していきます。エラーハンドリングも追加しています。
問題4:数字の桁数を数える
問題: 整数の桁数を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
"math"
)
func countDigits(n int) int {
if n == 0 {
return 1
}
return int(math.Log10(math.Abs(float64(n)))) + 1
}
func main() {
num := -12345
fmt.Printf("%d の桁数は %d 桁です\n", num, countDigits(num))
}
解説: 対数を使用して桁数を計算します。0の場合は特別に1桁と扱います。
問題 5: 2つの配列のマージ
問題: 2つの整数配列を結合して1つの配列にする関数を作成してください。
解答例:
package main
import (
"fmt"
)
func mergeArrays(arr1, arr2 []int) []int {
return append(arr1, arr2...)
}
func main() {
arr1 := []int{1, 2, 3}
arr2 := []int{4, 5, 6}
merged := mergeArrays(arr1, arr2)
fmt.Println("マージされた配列:", merged)
}
解説: append関数を使用して2つのスライスを結合します。
問題6:平均値の計算
問題: 整数のリストの平均値を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func average(arr []int) (float64, error) {
if len(arr) == 0 {
return 0, fmt.Errorf("配列が空です")
}
total := 0
for _, num := range arr {
total += num
}
return float64(total) / float64(len(arr)), nil
}
func main() {
arr := []int{1, 2, 3, 4, 5}
avg, err := average(arr)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("平均値は", avg, "です")
}
解説: 合計を要素数で割り、平均値を計算します。ゼロ除算を防ぐため、配列が空でないかチェックしています。
問題7:矩形の面積
問題: 長方形の幅と高さを受け取り、その面積を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func rectangleArea(width, height float64) (float64, error) {
if width <= 0 || height <= 0 {
return 0, fmt.Errorf("幅と高さは正の数でなければなりません")
}
return width * height, nil
}
func main() {
area, err := rectangleArea(5, 10)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("面積は", area, "です")
}
解説: 面積は幅と高さの積で求められます。入力値が正の数であることを確認しています。
問題8:文字の出現回数
問題: 指定された文字列内にある特定の文字が何回出現するかを数える関数を作成してください。
解答例:
package main
import (
"fmt"
)
func countOccurrences(s string, target rune) int {
count := 0
for _, char := range s {
if char == target {
count++
}
}
return count
}
func main() {
str := "hello world"
char := 'l'
fmt.Printf("文字 '%c' の出現回数は %d 回です\n", char, countOccurrences(str, char))
}
解説: 文字列をルーンスライスとして扱い、ターゲット文字と一致する場合にカウントを増やします。
問題9:リストの合計の偶奇判定
問題: 整数のリストの合計が偶数か奇数かを判定する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func isSumEven(arr []int) bool {
total := 0
for _, num := range arr {
total += num
}
return total%2 == 0
}
func main() {
arr := []int{1, 2, 3, 4}
if isSumEven(arr) {
fmt.Println("合計は偶数です")
} else {
fmt.Println("合計は奇数です")
}
}
解説: 合計を2で割った余りをチェックし、偶数か奇数かを判定します。
問題10:最大公約数(ユークリッドの互除法)
問題: 2つの整数の最大公約数を求める関数を作成してください。
解答例:
package main
import (
"fmt"
)
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func main() {
fmt.Println("最大公約数は", gcd(56, 98), "です")
}
解説: ユークリッドの互除法を使用して最大公約数を計算します。ループを用いて計算しています。
問題11:アナグラム判定
問題: 2つの文字列がアナグラム(文字の並び替えで一致)かどうかを判定する関数を作成してください。
解答例:
package main
import (
"fmt"
"sort"
"strings"
)
func areAnagrams(s1, s2 string) bool {
// 長さが異なる場合はアナグラムではない
if len(s1) != len(s2) {
return false
}
// 文字列をソートして比較
s1Slice := strings.Split(s1, "")
s2Slice := strings.Split(s2, "")
sort.Strings(s1Slice)
sort.Strings(s2Slice)
return strings.Join(s1Slice, "") == strings.Join(s2Slice, "")
}
func main() {
fmt.Println(areAnagrams("listen", "silent")) // true
}
解説: 文字列をスライスに分解し、ソートしてから比較します。
問題12:パリンドローム判定
問題: 与えられた文字列がパリンドローム(回文)かどうかを判定する関数を作成してください。
解答例:
package main
import (
"fmt"
"strings"
"unicode"
)
func isPalindrome(s string) bool {
// 文字列を正規化(小文字化と空白除去)
var filtered []rune
for _, r := range strings.ToLower(s) {
if unicode.IsLetter(r) || unicode.IsNumber(r) {
filtered = append(filtered, r)
}
}
// 左右から文字を比較
for i, j := 0, len(filtered)-1; i < j; i, j = i+1, j-1 {
if filtered[i] != filtered[j] {
return false
}
}
return true
}
func main() {
str := "A man, a plan, a canal: Panama"
fmt.Println(isPalindrome(str)) // true
}
解説: 文字列をルーンスライスに変換し、アルファベットと数字のみを対象に比較します。大文字小文字の違いや空白・記号を無視するため、正規化しています。
問題13:ユークリッド距離の計算
問題: 2次元平面上の2点間のユークリッド距離を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
"math"
)
func euclideanDistance(x1, y1, x2, y2 float64) float64 {
dx := x2 - x1
dy := y2 - y1
return math.Sqrt(dx*dx + dy*dy)
}
func main() {
distance := euclideanDistance(1, 2, 4, 6)
fmt.Printf("2点間の距離は %.2f です\n", distance)
}
解説: 2点間の距離は、x座標の差の二乗とy座標の差の二乗の合計の平方根で計算します。
問題14:文字列の大文字を小文字に変換
問題: 与えられた文字列内の全ての大文字を小文字に変換する関数を作成してください。
解答例:
package main
import (
"fmt"
"strings"
)
func toLowerCase(s string) string {
return strings.ToLower(s)
}
func main() {
str := "HELLO WORLD"
fmt.Println(toLowerCase(str))
}
解説: strings.ToLower関数を使用して文字列を小文字に変換します。
中級問題
問題15:素数判定
問題: 与えられた整数が素数であるかどうかを判定する関数を作成してください。
解答例:
package main
import (
"fmt"
"math"
)
func isPrime(n int) bool {
if n <= 1 {
return false
}
// 2から平方根までの数字で割り切れるかをチェック
sqrt := int(math.Sqrt(float64(n)))
for i := 2; i <= sqrt; i++ {
if n%i == 0 {
return false
}
}
return true
}
func main() {
number := 29
fmt.Println(isPrime(number))
}
解説: 1より大きい整数について、2からその平方根までの整数で割り切れるかを確認します。割り切れない場合は素数と判定します。
問題16:階乗計算
問題: 与えられた整数の階乗を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func factorial(n int) int {
result := 1
for i := 2; i <= n; i++ {
result *= i
}
return result
}
func main() {
num := 5
fmt.Println(factorial(num))
}
解説: ループを使用して1からnまでの数値を順に掛け合わせていきます。
問題17:フィボナッチ数列
問題: n番目のフィボナッチ数を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func fibonacci(n int) int {
if n <= 1 {
return n
}
// メモ化による効率化
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}
func main() {
n := 10
fmt.Println(fibonacci(n))
}
解説: 再帰を使用すると計算量が増大するため、ループを使って前の2つの値を更新しながら計算します。
問題18:リストの中央値
問題: 整数のリストの中央値を求める関数を作成してください。リストはソートされていない場合があります。
解答例:
package main
import (
"fmt"
"sort"
)
func median(arr []int) (float64, error) {
if len(arr) == 0 {
return 0, fmt.Errorf("配列が空です")
}
sort.Ints(arr)
n := len(arr)
if n%2 == 0 {
return float64(arr[n/2-1]+arr[n/2]) / 2.0, nil
}
return float64(arr[n/2]), nil
}
func main() {
arr := []int{3, 5, 1, 4, 2}
med, err := median(arr)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("中央値は", med, "です")
}
解説: 配列をソートし、要素数に応じて中央値を計算します。
問題19:重複要素の削除
問題: 整数のリストから重複する要素を削除し、一意の要素のみを持つ新しいリストを返す関数を作成してください。
解答例:
package main
import (
"fmt"
)
func removeDuplicates(arr []int) []int {
uniqueSet := make(map[int]struct{})
var result []int
for _, num := range arr {
if _, exists := uniqueSet[num]; !exists {
uniqueSet[num] = struct{}{}
result = append(result, num)
}
}
return result
}
func main() {
arr := []int{1, 2, 2, 3, 4, 4, 5}
fmt.Println(removeDuplicates(arr)) // [1 2 3 4 5]
}
解説: マップを使って要素の存在を確認し、重複を避けて結果のスライスに追加します。
問題20:累乗計算
問題: 与えられた基数と指数で累乗を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func power(base, exponent int) int {
result := 1
for exponent > 0 {
if exponent%2 == 1 {
result *= base
}
base *= base
exponent /= 2
}
return result
}
func main() {
fmt.Println("2の10乗は", power(2, 10), "です")
}
解説: 累乗を効率的に計算するために、二分累乗法(指数の二進数表現)を使用しています。
問題21:2つのリストの交差
問題: 2つの整数リストの共通部分を返す関数を作成してください。
解答例:
package main
import (
"fmt"
)
func intersection(arr1, arr2 []int) []int {
m := make(map[int]bool)
for _, num := range arr1 {
m[num] = true
}
var result []int
for _, num := range arr2 {
if m[num] {
result = append(result, num)
m[num] = false // 重複を避ける
}
}
return result
}
func main() {
arr1 := []int{1, 2, 3, 4, 5}
arr2 := []int{4, 5, 6, 7, 8}
fmt.Println("共通部分:", intersection(arr1, arr2))
}
解説: マップを使用して1つ目のリストの要素を記録し、2つ目のリストで共通する要素を探します。
問題22:2つの文字列の共通部分
問題: 2つの文字列に共通する文字を全て抽出する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func commonCharacters(s1, s2 string) []rune {
charMap := make(map[rune]bool)
for _, char := range s1 {
charMap[char] = true
}
var common []rune
for _, char := range s2 {
if charMap[char] {
common = append(common, char)
charMap[char] = false // 重複を避ける
}
}
return common
}
func main() {
s1 := "apple"
s2 := "grape"
fmt.Printf("共通の文字: %c\n", commonCharacters(s1, s2))
}
解説: 最初の文字列の文字をマップに記録し、2つ目の文字列をループして共通する文字を抽出します。
問題23:文字列の単語数を数える
問題: 与えられた文字列内の単語数を数える関数を作成してください。単語はスペースで区切られたものとします。
解答例:
package main
import (
"fmt"
"strings"
)
func countWords(s string) int {
words := strings.Fields(s)
return len(words)
}
func main() {
str := "Hello world this is a test"
fmt.Println("単語数は", countWords(str), "です")
}
解説: strings.Fields関数を使って文字列を単語に分割し、単語数を数えます。
問題24:マトリックスの転置
問題: 与えられたマトリックス(2次元配列)を転置する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func transpose(matrix [][]int) [][]int {
rows := len(matrix)
cols := len(matrix[0])
transposed := make([][]int, cols)
for i := range transposed {
transposed[i] = make([]int, rows)
}
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
transposed[j][i] = matrix[i][j]
}
}
return transposed
}
func main() {
matrix := [][]int{
{1, 2, 3},
{4, 5, 6},
}
trans := transpose(matrix)
fmt.Println("転置行列:")
for _, row := range trans {
fmt.Println(row)
}
}
解説: マトリックスの行と列を入れ替えて新しいマトリックスを作成します。
問題25:リストの逆順
問題: 整数のリストを逆順にする関数を作成してください。
解答例:
package main
import (
"fmt"
)
func reverseList(arr []int) []int {
n := len(arr)
reversed := make([]int, n)
for i, val := range arr {
reversed[n-i-1] = val
}
return reversed
}
func main() {
arr := []int{1, 2, 3, 4, 5}
fmt.Println("逆順リスト:", reverseList(arr))
}
解説: リストを逆順にするために新しいリストを作成し、元のリストを逆順にコピーします。
問題26:文字列の各単語の逆転
問題: 与えられた文字列内の各単語を逆順にする関数を作成してください。
解答例:
package main
import (
"fmt"
"strings"
)
func reverseWords(s string) string {
words := strings.Fields(s)
for i, word := range words {
words[i] = reverseString(word)
}
return strings.Join(words, " ")
}
func reverseString(s string) string {
runes := []rune(s)
length := len(runes)
for i := 0; i < length/2; i++ {
runes[i], runes[length-1-i] = runes[length-1-i], runes[i]
}
return string(runes)
}
func main() {
str := "Hello world"
fmt.Println("各単語を逆転:", reverseWords(str))
}
解説: 文字列を単語ごとに分割し、各単語を逆順にして再び結合します。
問題27:隣接する重複を削除
問題: 文字列から隣接する重複する文字を削除する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func removeAdjacentDuplicates(s string) string {
if len(s) == 0 {
return s
}
result := []rune{rune(s[0])}
for _, char := range s[1:] {
if char != result[len(result)-1] {
result = append(result, char)
}
}
return string(result)
}
func main() {
str := "aabbccddeeff"
fmt.Println("重複削除後の文字列:", removeAdjacentDuplicates(str))
}
解説: 前の文字と異なる場合のみ結果リストに追加し、隣接する重複を避けます。
問題28:ハッシュマップの値の合計
問題: 整数のキーと値を持つハッシュマップの値の合計を計算する関数を作成してください。
解答例:
package main
import (
"fmt"
)
func sumMapValues(m map[int]int) int {
sum := 0
for _, value := range m {
sum += value
}
return sum
}
func main() {
m := map[int]int{1: 10, 2: 20, 3: 30}
fmt.Println("値の合計は", sumMapValues(m), "です")
}
解説: ハッシュマップの各値をループして合計を計算します。
問題29:2つのリストの差
問題: 2つの整数リストから一方のリストにのみ存在する要素を返す関数を作成してください。
解答例:
package main
import (
"fmt"
)
func difference(arr1, arr2 []int) []int {
m := make(map[int]bool)
for _, num := range arr2 {
m[num] = true
}
var result []int
for _, num := range arr1 {
if !m[num] {
result = append(result, num)
}
}
return result
}
func main() {
arr1 := []int{1, 2, 3, 4, 5}
arr2 := []int{4, 5, 6, 7, 8}
fmt.Println("差分リスト:", difference(arr1, arr2))
}
解説: 一方のリストに存在する要素を記録し、もう一方のリストで存在しない要素を見つけます。
問題30:リストの最大値
問題: 整数のリストの中から最大値を見つける関数を作成してください。
解答例:
package main
import (
"fmt"
)
func findMax(arr []int) (int, error) {
if len(arr) == 0 {
return 0, fmt.Errorf("配列が空です")
}
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
return max, nil
}
func main() {
arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5}
max, err := findMax(arr)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("最大値は", max, "です")
}
解説: 配列をループして最大値を見つけます。配列が空の場合はエラーを返します。
問題31:ハッシュマップのキーのリスト
問題: ハッシュマップのキーを全て含むリストを返す関数を作成してください。
解答例:
package main
import (
"fmt"
)
func keys(m map[int]int) []int {
var keys []int
for key := range m {
keys = append(keys, key)
}
return keys
}
func main() {
m := map[int]int{1: 10, 2: 20, 3: 30}
fmt.Println("キーのリスト:", keys(m))
}
解説: ハッシュマップの全てのキーをリストに追加し、返します。
問題32:2つの文字列の部分文字列判定
問題: 1つの文字列がもう1つの文字列の部分文字列であるかどうかを判定する関数を作成してください。
解答例:
package main
import (
"fmt"
"strings"
)
func isSubstring(s1, s2 string) bool {
return strings.Contains(s2, s1)
}
func main() {
fmt.Println(isSubstring("test", "this is a test string")) // true
}
解説: strings.Contains関数を使用して部分文字列の判定を行います。
問題33:最大公約数(再帰版)
問題: 2つの整数の最大公約数を再帰を使って求める関数を作成してください。
解答例:
package main
import (
"fmt"
)
func gcdRecursive(a, b int) int {
if b == 0 {
return a
}
return gcdRecursive(b, a%b)
}
func main() {
fmt.Println("最大公約数は", gcdRecursive(56, 98), "です")
}
解説: ユークリッドの互除法を再帰を使って実装し、最大公約数を求めます。
上級問題
問題34:2つの数の和
問題: 2つの数の和が特定のターゲットになるようなリストの中の2つの数のインデックスを返す関数を作成してください。
解答例:
package main
import "fmt"
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for i, num := range nums {
if j, ok := m[target-num]; ok {
return []int{j, i}
}
m[num] = i
}
return nil
}
func main() {
nums := []int{2, 7, 11, 15}
target := 9
fmt.Println("インデックス:", twoSum(nums, target))
}
解説: マップを使用して過去の要素を記録し、ターゲットとの差がマップに存在するかをチェックします。
問題35:バイナリサーチ(2分探索)
問題: ソート済みのリストにおけるターゲット値のインデックスを見つける関数を作成してください。
解答例:
package main
import "fmt"
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
func main() {
nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
target := 5
fmt.Println("インデックス:", binarySearch(nums, target))
}
解説: バイナリサーチを使用してターゲット値のインデックスを効率的に検索します。
問題36:2つの数を加算(リンクリスト)
問題: リンクリストで表現された2つの非負整数を加算する関数を作成してください。
解答例:
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current, carry := dummy, 0
for l1 != nil || l2 != nil || carry != 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
carry = sum / 10
current.Next = &ListNode{Val: sum % 10}
current = current.Next
}
return dummy.Next
}
func main() {
// リストの例
l1 := &ListNode{2, &ListNode{4, &ListNode{3, nil}}}
l2 := &ListNode{5, &ListNode{6, &ListNode{4, nil}}}
result := addTwoNumbers(l1, l2)
fmt.Print("結果: ")
for result != nil {
fmt.Print(result.Val)
result = result.Next
}
}
解説: 各ノードを順に加算し、桁上がりを処理します。リンクリストを使用して大きな整数を扱います。
問題37:2つのソート済みリストのマージ
問題: 2つのソート済みのリンクリストをマージして1つのソート済みリンクリストを作る関数を作成してください。
解答例:
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return dummy.Next
}
func main() {
// リストの例
l1 := &ListNode{1, &ListNode{2, &ListNode{4, nil}}}
l2 := &ListNode{1, &ListNode{3, &ListNode{4, nil}}}
merged := mergeTwoLists(l1, l2)
fmt.Print("マージ結果: ")
for merged != nil {
fmt.Print(merged.Val, " ")
merged = merged.Next
}
}
解説: 2つのリンクリストをポインタを使ってマージし、新しいソート済みリストを作成します。
問題38:重複しない最長部分文字列
問題: 重複する文字がない最長の部分文字列を見つける関数を作成してください。
解答例:
package main
import "fmt"
func lengthOfLongestSubstring(s string) int {
m := make(map[byte]int)
maxLen, left := 0, 0
for right := 0; right < len(s); right++ {
if idx, ok := m[s[right]]; ok && idx >= left {
left = idx + 1
}
m[s[right]] = right
if right-left+1 > maxLen {
maxLen = right - left + 1
}
}
return maxLen
}
func main() {
s := "abcabcbb"
fmt.Println("最長部分文字列の長さ:", lengthOfLongestSubstring(s))
}
解説: スライディングウィンドウとハッシュマップを使用して、重複を避けながら最長の部分文字列を見つけます。
問題39:アナグラムのグループ化
問題: アナグラムのグループを見つける関数を作成してください。
解答例:
package main
import (
"fmt"
"sort"
)
func groupAnagrams(strs []string) [][]string {
anagrams := make(map[string][]string)
for _, str := range strs {
sortedStr := sortString(str)
anagrams[sortedStr] = append(anagrams[sortedStr], str)
}
var result [][]string
for _, group := range anagrams {
result = append(result, group)
}
return result
}
func sortString(s string) string {
runes := []rune(s)
sort.Slice(runes, func(i, j int) bool {
return runes[i] < runes[j]
})
return string(runes)
}
func main() {
strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
fmt.Println("アナグラムのグループ:", groupAnagrams(strs))
}
解説: 各文字列をソートし、同じソート結果を持つ文字列を同じグループにまとめます。
問題40:上位K個の頻出要素
問題: 頻度が最も高いk個の要素を見つける関数を作成してください。
解答例:
package main
import (
"container/heap"
"fmt"
)
type Element struct {
Value int
Count int
}
type MinHeap []Element
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Count < h[j].Count }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(Element))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func topKFrequent(nums []int, k int) []int {
freqMap := make(map[int]int)
for _, num := range nums {
freqMap[num]++
}
h := &MinHeap{}
heap.Init(h)
for value, count := range freqMap {
heap.Push(h, Element{Value: value, Count: count})
if h.Len() > k {
heap.Pop(h)
}
}
var result []int
for h.Len() > 0 {
result = append(result, heap.Pop(h).(Element).Value)
}
return result
}
func main() {
nums := []int{1, 1, 1, 2, 2, 3}
k := 2
fmt.Println("上位", k, "個の要素:", topKFrequent(nums, k))
}
解説: ヒープを使用して頻度の高い要素を効率的に取得します。
問題41:最長増加部分列
問題: 最長増加部分列を見つける関数を作成してください。
解答例:
package main
import "fmt"
func lengthOfLIS(nums []int) int {
if len(nums) == 0 {
return 0
}
dp := make([]int, len(nums))
maxLen := 0
for i := range nums {
dp[i] = 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
dp[i] = max(dp[i], dp[j]+1)
}
}
maxLen = max(maxLen, dp[i])
}
return maxLen
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
fmt.Println("最長増加部分列の長さ:", lengthOfLIS(nums))
}
解説: 動的計画法を使用して、各位置での最長増加部分列の長さを計算します。
問題42:2つのソート済み配列の中央値
問題: 2つのソート済み配列の中央値を見つける関数を作成してください。
解答例:
package main
import (
"fmt"
)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
if m > n {
return findMedianSortedArrays(nums2, nums1)
}
imin, imax, halfLen := 0, m, (m+n+1)/2
for imin <= imax {
i := (imin + imax) / 2
j := halfLen - i
if i < m && nums2[j-1] > nums1[i] {
imin = i + 1
} else if i > 0 && nums1[i-1] > nums2[j] {
imax = i - 1
} else {
maxOfLeft := 0
if i == 0 {
maxOfLeft = nums2[j-1]
} else if j == 0 {
maxOfLeft = nums1[i-1]
} else {
maxOfLeft = max(nums1[i-1], nums2[j-1])
}
if (m+n)%2 == 1 {
return float64(maxOfLeft)
}
minOfRight := 0
if i == m {
minOfRight = nums2[j]
} else if j == n {
minOfRight = nums1[i]
} else {
minOfRight = min(nums1[i], nums2[j])
}
return float64(maxOfLeft+minOfRight) / 2.0
}
}
return 0.0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
nums1 := []int{1, 3}
nums2 := []int{2}
fmt.Println("中央値:", findMedianSortedArrays(nums1, nums2))
}
解説: 2つの配列を適切に分割し、中央値を計算します。バイナリサーチを使用しています。
問題43:K個のソート済みリストのマージ
問題: K個のソート済みリンクリストを1つのソート済みリンクリストにマージする関数を作成してください。
解答例:
package main
import (
"container/heap"
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
type ListNodeHeap []*ListNode
func (h ListNodeHeap) Len() int { return len(h) }
func (h ListNodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h ListNodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *ListNodeHeap) Push(x interface{}) {
*h = append(*h, x.(*ListNode))
}
func (h *ListNodeHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func mergeKLists(lists []*ListNode) *ListNode {
h := &ListNodeHeap{}
heap.Init(h)
for _, list := range lists {
if list != nil {
heap.Push(h, list)
}
}
dummy := &ListNode{}
current := dummy
for h.Len() > 0 {
node := heap.Pop(h).(*ListNode)
current.Next = node
current = current.Next
if node.Next != nil {
heap.Push(h, node.Next)
}
}
return dummy.Next
}
func main() {
// リストの例
l1 := &ListNode{1, &ListNode{4, &ListNode{5, nil}}}
l2 := &ListNode{1, &ListNode{3, &ListNode{4, nil}}}
l3 := &ListNode{2, &ListNode{6, nil}}
lists := []*ListNode{l1, l2, l3}
merged := mergeKLists(lists)
fmt.Print("マージ結果: ")
for merged != nil {
fmt.Print(merged.Val, " ")
merged = merged.Next
}
}
解説: ヒープを使用して各リストの先頭を管理し、最小の要素を順に取り出します。
問題44:最長の有効な括弧
問題: 最長の有効な括弧の部分文字列を見つける関数を作成してください。
解答例:
package main
import "fmt"
func longestValidParentheses(s string) int {
maxLen := 0
stack := []int{}
stack = append(stack, -1)
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1]
if len(stack) == 0 {
stack = append(stack, i)
} else {
currentLen := i - stack[len(stack)-1]
if currentLen > maxLen {
maxLen = currentLen
}
}
}
}
return maxLen
}
func main() {
s := "(()"
fmt.Println("最長の有効な括弧の長さ:", longestValidParentheses(s))
}
解説: スタックを使用して括弧の位置を追跡し、有効な部分文字列の長さを計算します。
問題45:自身を除く配列の積
問題: 配列の各要素に対して、その要素を除いた他の全ての要素の積を計算する関数を作成してください。
解答例:
package main
import "fmt"
func productExceptSelf(nums []int) []int {
n := len(nums)
result := make([]int, n)
// 左からの積を計算
leftProduct := 1
for i := 0; i < n; i++ {
result[i] = leftProduct
leftProduct *= nums[i]
}
// 右からの積を計算し、結果に乗じる
rightProduct := 1
for i := n - 1; i >= 0; i-- {
result[i] *= rightProduct
rightProduct *= nums[i]
}
return result
}
func main() {
nums := []int{1, 2, 3, 4}
fmt.Println("結果配列:", productExceptSelf(nums))
}
解説: 左右からの累積積を使用して、除いた積を効率的に計算します。
問題46:最小ウィンドウ部分文字列
問題: 文字列sの中で、文字列tの全ての文字を含む最小の部分文字列を見つける関数を作成してください。
解答例:
package main
import (
"fmt"
)
func minWindow(s string, t string) string {
if len(s) == 0 || len(t) == 0 {
return ""
}
// tの文字カウントを作成
tCount := make(map[byte]int)
for i := 0; i < len(t); i++ {
tCount[t[i]]++
}
required := len(tCount)
left, right := 0, 0
windowCount := make(map[byte]int)
formed := 0
ans := []int{-1, 0, 0}
for right < len(s) {
char := s[right]
windowCount[char]++
if tCount[char] > 0 && windowCount[char] == tCount[char] {
formed++
}
for left <= right && formed == required {
char = s[left]
if ans[0] == -1 || right-left+1 < ans[0] {
ans[0] = right - left + 1
ans[1] = left
ans[2] = right
}
windowCount[char]--
if tCount[char] > 0 && windowCount[char] < tCount[char] {
formed--
}
left++
}
right++
}
if ans[0] == -1 {
return ""
}
return s[ans[1] : ans[2]+1]
}
func main() {
s := "ADOBECODEBANC"
t := "ABC"
fmt.Println("最小ウィンドウ:", minWindow(s, t))
}
解説: スライディングウィンドウとハッシュマップを使用して、最小の部分文字列を見つけます。
問題47:デコード方法
問題: 与えられた数字の文字列をアルファベットにデコードする方法の数を計算する関数を作成してください。
解答例:
package main
import "fmt"
func numDecodings(s string) int {
if len(s) == 0 || s[0] == '0' {
return 0
}
dp := make([]int, len(s)+1)
dp[0], dp[1] = 1, 1
for i := 2; i <= len(s); i++ {
if s[i-1] != '0' {
dp[i] += dp[i-1]
}
twoDigit := (s[i-2]-'0')*10 + (s[i-1] - '0')
if twoDigit >= 10 && twoDigit <= 26 {
dp[i] += dp[i-2]
}
}
return dp[len(s)]
}
func main() {
s := "226"
fmt.Println("デコード方法の数:", numDecodings(s))
}
解説: 動的計画法を使用して、部分問題を解きながらデコード方法の総数を計算します。
問題48:ワードサーチ
問題: 2Dグリッドと単語が与えられたとき、グリッド内に単語が存在するかどうかを判定する関数を作成してください。
解答例:
package main
import "fmt"
func exist(board [][]byte, word string) bool {
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if backtrack(board, word, i, j, 0) {
return true
}
}
}
return false
}
func backtrack(board [][]byte, word string, i, j, index int) bool {
if index == len(word) {
return true
}
if i < 0 || j < 0 || i >= len(board) || j >= len(board[0]) || board[i][j] != word[index] {
return false
}
temp := board[i][j]
board[i][j] = ' '
found := backtrack(board, word, i+1, j, index+1) ||
backtrack(board, word, i-1, j, index+1) ||
backtrack(board, word, i, j+1, index+1) ||
backtrack(board, word, i, j-1, index+1)
board[i][j] = temp
return found
}
func main() {
board := [][]byte{
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'},
}
word := "ABCCED"
fmt.Println("単語が存在するか:", exist(board, word))
}
解説: 深さ優先探索を使用して、グリッド内を探索し、単語が存在するかをチェックします。
問題49:順列
問題: 与えられたリストの全ての順列を生成する関数を作成してください。
解答例:
package main
import "fmt"
func permute(nums []int) [][]int {
var result [][]int
var backtrack func(int)
backtrack = func(first int) {
if first == len(nums) {
perm := make([]int, len(nums))
copy(perm, nums)
result = append(result, perm)
return
}
for i := first; i < len(nums); i++ {
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
}
}
backtrack(0)
return result
}
func main() {
nums := []int{1, 2, 3}
fmt.Println("順列:", permute(nums))
}
解説: バックトラッキングを使用して、全ての可能な順列を生成します。
問題50:組み合わせの和
問題: 与えられた数値リストの中から、合計がターゲットとなるすべての組み合わせを見つける関数を作成してください。
解答例:
package main
import "fmt"
func combinationSum(candidates []int, target int) [][]int {
var result [][]int
var backtrack func(target, start int, comb []int)
backtrack = func(target, start int, comb []int) {
if target == 0 {
combCopy := make([]int, len(comb))
copy(combCopy, comb)
result = append(result, combCopy)
return
}
for i := start; i < len(candidates); i++ {
if candidates[i] <= target {
comb = append(comb, candidates[i])
backtrack(target-candidates[i], i, comb)
comb = comb[:len(comb)-1]
}
}
}
backtrack(target, 0, []int{})
return result
}
func main() {
candidates := []int{2, 3, 6, 7}
target := 7
fmt.Println("組み合わせの和:", combinationSum(candidates, target))
}
解説: バックトラッキングを使用して、全ての組み合わせを探索します。
問題51:画像の回転
問題: n×nの2Dマトリックスを90度回転させる関数を作成してください。
解答例:
package main
import "fmt"
func rotate(matrix [][]int) {
n := len(matrix)
for i := 0; i < n/2; i++ {
for j := i; j < n-i-1; j++ {
temp := matrix[i][j]
matrix[i][j] = matrix[n-j-1][i]
matrix[n-j-1][i] = matrix[n-i-1][n-j-1]
matrix[n-i-1][n-j-1] = matrix[j][n-i-1]
matrix[j][n-i-1] = temp
}
}
}
func main() {
matrix := [][]int{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
}
rotate(matrix)
fmt.Println("回転後のマトリックス:")
for _, row := range matrix {
fmt.Println(row)
}
}
解説: マトリックスを層ごとに回転させ、要素を適切に交換します。
問題52:ワードラダー
問題: 開始単語から終了単語に変換するために必要な最小のステップ数を求める関数を作成してください。単語の変換は辞書にある単語のみ許可されます。
解答例:
package main
import (
"fmt"
)
func ladderLength(beginWord string, endWord string, wordList []string) int {
wordSet := make(map[string]bool)
for _, word := range wordList {
wordSet[word] = true
}
if !wordSet[endWord] {
return 0
}
queue := []string{beginWord}
level := 1
for len(queue) > 0 {
nextQueue := []string{}
for _, word := range queue {
wordBytes := []byte(word)
for i := 0; i < len(wordBytes); i++ {
originalChar := wordBytes[i]
for c := 'a'; c <= 'z'; c++ {
wordBytes[i] = byte(c)
newWord := string(wordBytes)
if newWord == endWord {
return level + 1
}
if wordSet[newWord] {
nextQueue = append(nextQueue, newWord)
delete(wordSet, newWord)
}
}
wordBytes[i] = originalChar
}
}
queue = nextQueue
level++
}
return 0
}
func main() {
beginWord := "hit"
endWord := "cog"
wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
fmt.Println("最小ステップ数:", ladderLength(beginWord, endWord, wordList))
}
解説: 幅優先探索を使用して、単語の変換経路を最短で見つけます。
問題53:バイナリツリーのシリアライズとデシリアライズ
問題: バイナリツリーをシリアライズおよびデシリアライズするための関数を作成してください。
解答例:
package main
import (
"fmt"
"strconv"
"strings"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func serialize(root *TreeNode) string {
var sb strings.Builder
var build func(node *TreeNode)
build = func(node *TreeNode) {
if node == nil {
sb.WriteString("null,")
return
}
sb.WriteString(strconv.Itoa(node.Val) + ",")
build(node.Left)
build(node.Right)
}
build(root)
return sb.String()
}
func deserialize(data string) *TreeNode {
vals := strings.Split(data, ",")
var build func() *TreeNode
build = func() *TreeNode {
if vals[0] == "null" {
vals = vals[1:]
return nil
}
val, _ := strconv.Atoi(vals[0])
vals = vals[1:]
return &TreeNode{
Val: val,
Left: build(),
Right: build(),
}
}
return build()
}
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 4,
},
Right: &TreeNode{
Val: 5,
},
},
}
data := serialize(root)
fmt.Println("シリアライズ結果:", data)
deserializedRoot := deserialize(data)
fmt.Println("デシリアライズ結果:", serialize(deserializedRoot))
}
解説: プリオーダートラバーサルを使用してツリーをシリアライズし、再帰的にデシリアライズします。
まとめ
以上、Go言語のコーディング試験でよく出題される全53問とその解答・解説を紹介しました。これらの問題を通じて、基本的なアルゴリズムやデータ構造の理解を深め、実践的なコーディングスキルを磨いてください。
注意事項
各問題は、理解を深めるために実際にコードを実行してみることをお勧めします。
問題の難易度は目安であり、個人のスキルや経験によって異なる場合があります。
Discussion