プログラミングの練習のため、NeetCodeに掲載されているAlgorithmsのRoadmapに従ってGolangでLeetCodeの問題を解いていきます。
今回は、NeetCodeのRoadmapのArrays & Hashingの問題を解いてみます。
Contains Duplicate #
intのスライスnumsが与えられるので、重複する整数があるときはtrueを返し、重複しないときはfalseを返すようにします。
func containsDuplicate(nums []int) bool {
checkMap := map[int]bool{}
for _, n := range nums {
if _, ok := checkMap[n]; ok {
return true
} else {
checkMap[n] = true
}
}
return false
}
Valid Anagram #
2つの文字列sとtが与えられるので、tがsのアナグラムかどうか判定します。
アナグラムのときはtrueを返し、そうでないときはfalseを返します。
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
rune1 := []rune(s)
rune2 := []rune(t)
sortRune(rune1)
sortRune(rune2)
return string(rune1) == string(rune2)
}
func sortRune(r []rune) {
sort.Slice(r, func(i, j int) bool { return r[i] < r[j] })
}
Two Sum #
intのスライスnumsとintのtargetが与えられるので、スライスの中から2つの数値を足してtargetになる組み合わせを探し、
その2つのインデックスを返します。
func twoSum(nums []int, target int) []int {
m := make(map[int]int, len(nums))
for i := 0; i < len(nums); i++ {
findNum := target - nums[i]
if _, ok := m[findNum]; ok {
return []int{m[findNum], i}
}
m[nums[i]] = i
}
return nil
}
Group Anagrams #
文字列のスライスstrsが与えられるので、各文字列がアナグラムになるものをグループ化したスライスを返します。
グループ化したアナグラムのスライスは順不同で問題ありません。
["eat", "tea", "tan", "ate", "nat", "bat"]が与えられたとき、
[["bat"], ["nat","tan"], ["ate","eat","tea"]]を返すようにします。
([["nat","tan"], ["ate","eat","tea"], ["bat"]]などでも問題ありません)
func groupAnagrams(strs []string) [][]string {
sortMap := make(map[string][]int, len(strs))
for i, s := range strs {
splitStr := strings.Split(s, "")
sort.Strings(splitStr)
joinStr := strings.Join(splitStr, "")
sortMap[joinStr] = append(sortMap[joinStr], i)
}
answers := [][]string{}
for _, v := range sortMap {
answer := make([]string, len(v))
for j, sourceIndex := range v {
answer[j] = strs[sourceIndex]
}
answers = append(answers, answer)
}
return answers
}
Top K Frequent Elements #
intのスライスnumsが与えられるので、出現頻度が高い上位k個の要素を返します。
func topKFrequent(nums []int, k int) []int {
m := map[int]int{}
for _, v := range nums {
m[v] += 1
}
numStructSlice := make([]numStruct, len(m))
index := 0
for k, v := range m {
ns := numStruct{k, v}
numStructSlice[index] = ns
index += 1
}
sort.Slice(numStructSlice, func(i, j int) bool {
return numStructSlice[i].value > numStructSlice[j].value
})
answer := make([]int, k)
for i := 0; i < k; i++ {
answer[i] = numStructSlice[i].key
}
return answer
}
type numStruct struct {
key int
value int
}
Encode and Decode Strings(Premiumプラン加入が必要なため解いてません) #
Product of Array Except Self #
intのスライスnumsが与えられるので、各要素自身を除いた積を計算します。
例えば、nums = [1,2,3,4]が与えられたとき、output = [24,12,8,6]になります。
output[0]はnums[0]を除いた積なので、2 * 3 * 4 = 24です。
output[1]はnums[1]を除いた積なので、1 * 3 * 4 = 12です。
以降output[2]とoutput[3]も同様の方法で積を算出するので、
output[2] = 8, output[3] = 6 になります。
制約として下記の2点を満たす必要があります。
- \(O(n)\)の計算量で解くこと
- 除算を使わないこと
自力で解こうとしてみたのですが\(O(n)\)の条件を満たせず、下記を参考に解きました。
func productExceptSelf(nums []int) []int {
n := len(nums)
pre := make([]int, n)
pre[0] = 1
for i := 1; i < n; i++ {
pre[i] = pre[i-1] * nums[i-1]
}
suf := make([]int, n)
suf[n-1] = 1
for i := n - 2; i >= 0; i-- {
suf[i] = suf[i+1] * nums[i+1]
}
answers := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
answers[i] = pre[i] * suf[i]
}
return answers
}
nums = [1,2,3,4]が与えられたときの、nums、pre、sufの値は下記のようになります。
| nums | pre | suf | pre * suf |
|---|---|---|---|
| 1 | 1 | 48 | 48 |
| 2 | 1 | 24 | 24 |
| 4 | 2 | 6 | 12 |
| 6 | 8 | 1 | 8 |
Valid Sudoku #
[][]byteのスライスboardが与えられるので、boardが下記の3つの条件を満たしているかどうかを判定します。
- 横の行に1-9の数字が重複しないで入力されていること
- 縦の列に1-9の数字が重複しないで入力されていること
- 3x3のボックスに1-9の数字が重複しないで入力されていること
3つの条件を満たしているときはtrueを返し、そうでないときはfalseを返します。
const maxLength int = 9
var emptyByte = []byte(".")
func isValidSudoku(board [][]byte) bool {
for y := 0; y < maxLength; y++ {
for x := 0; x < maxLength; x++ {
currentValue := board[y][x]
if currentValue == emptyByte[0] {
continue
}
if !isValidRow(board, y, x, currentValue) {
return false
}
if !isValidColumn(board, y, x, currentValue) {
return false
}
if !isValidCell(board) {
return false
}
}
}
return true
}
func isValidRow(board [][]byte, y, x int, currentValue byte) bool {
for searchX := 0; searchX < maxLength; searchX++ {
if searchX == x {
continue
}
if board[y][searchX] == currentValue {
return false
}
}
return true
}
func isValidColumn(board [][]byte, y, x int, currentValue byte) bool {
for searchY := 0; searchY < maxLength; searchY++ {
if searchY == y {
continue
}
if board[searchY][x] == currentValue {
return false
}
}
return true
}
func isValidCell(board [][]byte) bool {
for y := 0; y < maxLength; y += 3 {
for x := 0; x < maxLength; x += 3 {
if !isValidCellDetail(board, y, x) {
return false
}
}
}
return true
}
func isValidCellDetail(board [][]byte, baseY, baseX int) bool {
m := make(map[byte]int)
for offsetY := 0; offsetY < 3; offsetY++ {
for offsetX := 0; offsetX < 3; offsetX++ {
currentValue := board[baseY+offsetY][baseX+offsetX]
if currentValue == emptyByte[0] {
continue
}
if _, ok := m[currentValue]; ok {
return false
} else {
m[currentValue] += 1
}
}
}
return true
}
Longest Consecutive Sequence #
未ソートのintのスライスnumsが与えられるので、連続する整数の最長の長さを返します。
例えば、nums = [100, 4, 200, 1, 3, 2]が与えられたとき、[1, 2, 3, 4]が連続しているので、4を返すようにします。
func longestConsecutive(nums []int) int {
if len(nums) == 0 {
return 0
}
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
maxCount := 1
count := 1
for i := 0; i < len(nums)-1; i++ {
if nums[i+1]-nums[i] == 1 {
count++
} else if nums[i+1] == nums[i] {
continue
} else {
maxCount = maxCheck(count, maxCount)
count = 1
}
}
maxCount = maxCheck(count, maxCount)
return maxCount
}
func maxCheck(count, maxCount int) int {
if count > maxCount {
return count
}
return maxCount
}