【LeetCode】1768. Merge Strings Alternately
概要
一番最初の考え
- word1とword2のどちらのほうが長いかを確認する。
- 短い方の長さでループを回し、word1,word2から交互に1文字ずつ解答用の文字列に入れていく
- 余った方の残りを解答用の文字列に入れる
- 出力
コピペ忘れて消したので貼り付けなし。
import ( "strings" ) func mergeAlternately(word1 string, word2 string) string { rune1 := []rune(word1) rune2 := []rune(word2) var builder strings.Builder for i := 0; i < len(rune1) || i < len(rune2); i++ { if i < len(rune1) { builder.WriteRune(rune1[i]) } if i < len(rune2) { builder.WriteRune(rune2[i]) } } return builder.String() }
今回の学び
文字を1文字づつ追加して文字列を作成するときは、stringライブラリを使うと作成するたびに再作成しなくて済むので省メモリ化できる。
【LeetCode】1. Two Sum
概要
一番最初の
func twoSum(nums []int, target int) []int { for parentIdx, parentVal := range nums { for childIdx, childVal := range nums { if (childIdx == parentIdx){ continue } if (childVal + parentVal == target){ return []int{childIdx, parentIdx} } } } return nil }
改善策
現状、配列の各要素について、他のすべての要素との合計をチェックしているのでO(n2)の時間複雑度を持っています。 これを改善するために、ハッシュマップ(Goではmapと呼ばれます)を使用して、一度のループで問題を解くことができます。 これにより時間複雑度はO(n)になります。
func twoSum(nums []int, target int) []int { m := make(map[int]int) for i, num := range nums { // 補数を求める complement := target - num // mapのkeyに補数があるか if j, ok := m[complement]; ok { return []int{j, i} } // なければmapのkeyにnum、valにindexを入れる m[num] = i fmt.Println(m) } return nil }
このコードは、各要素を訪れるときに、それが必要な補数(目標となる合計からその要素を引いたもの)が既にマップ内に存在するかどうかをチェックします。存在する場合、それは目標の合計を構成する2つの数が見つかったことを意味します。存在しない場合、その要素をマップに追加します(キーは要素の値、値は要素のインデックス)。
まとめ
ループが二重、O(n2)だと思ったら思ったらハッシュマップが使えないか調べてみる。
golangで詰まった点: todo redeclared in this block (compile)
# golangで詰まった点
golangの返り値の書き方には2種類ある。
一つ目は返り値の方のみ指定するパターン
func GetTodo(id int) (Todo, error) {}
二つ目は同時に宣言する場合パターン
func GetTodo(id int) (todo Todo, err error) {}
二つ目のパターンで宣言していると、関数内で同じ名前で宣言した場合に指摘が入る。
正:
func GetTodo(id int) (todo Todo, err error) {
Db.Find(&todo, id)
return todo, err
}
誤:
func GetTodo(id int) (todo Todo, err error) {
var todo Todo
Db.Find(&todo, id)
return todo, err
}
# 対応するエラー
todo redeclared in this block (compile)
この仕組みをNamed return valueというらしい。
詳しくは以下の記事を参照。
基本的には使わない方向のほうが良さそう。