プログラミングの練習のため、NeetCodeに掲載されているAlgorithmsのRoadmapに従ってGolangでLeetCodeの問題を解いていきます。
LeetCodeでPremiumプランに加入しないとアクセスできない問題については解いてません。
また、難易度Hardの問題については解いていません。
NeetCodeのRoadmapのTwo Pointersの問題を解いてみます。
Valid Palindrome #
文字列sが与えられたとき、それが回文であればtrueを、そうでなければfalseを返します。
func isPalindrome(s string) bool {
if len(s) == 1 {
return true
}
var alphabet = []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j",
"k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
"y", "z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
alphabetMap := make(map[string]struct{}, 26)
for _, v := range alphabet {
alphabetMap[v] = struct{}{}
}
lowerStr := strings.ToLower(s)
backwardPointer := len(lowerStr) - 1
for i := 0; i < len(lowerStr); i++ {
if i >= len(lowerStr) || backwardPointer < 0 {
break
}
for {
if _, ok := alphabetMap[string(lowerStr[i])]; ok {
break
} else {
i++
if i >= len(lowerStr) {
break
}
}
}
for {
if _, ok := alphabetMap[string(lowerStr[backwardPointer])]; ok {
break
} else {
backwardPointer--
if backwardPointer < 0 {
break
}
}
}
if i >= len(lowerStr) || backwardPointer < 0 {
break
}
if lowerStr[i] != lowerStr[backwardPointer] {
return false
}
backwardPointer--
}
return true
}
Two Sum II - Input Array Is Sorted #
昇順でソート済みのintのスライスnumbersとintのtargetが与えられるので、スライスの中から2つの数値を足してtargetになる組み合わせを探し、その2つのインデックスを返します。
正解の組み合わせは1つだけ存在し、同じ要素を2回使うことはできません。
func twoSum(numbers []int, target int) []int {
i := 0
j := len(numbers) - 1
for {
sum := numbers[i] + numbers[j]
if sum == target {
return []int{i + 1, j + 1}
}
if sum > target {
j--
} else {
i++
}
}
}
3Sum #
intのスライスnumsが与えられたとき、以下の条件を満たすすべての組[nums[i], nums[j], nums[k]]を返します。
i != j, i != k, j != knums[i] + nums[j] + nums[k] == 0
ただし、解答セットに重複する組を含めてはいけません。
(例えば[0,1,-1]と[0,-1,1]は要素の順序だけ違い、使用している要素は重複しているため、どちらか一方のみを回答に含めます)
Time Limit Exceededになってしまって自力で解けなかったので、下記を参考に解きました。
3Sum Efficiently: Essential LeetCode Guide
func threeSum(nums []int) [][]int {
slices.Sort(nums)
answers := [][]int{}
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
left := i + 1
right := len(nums) - 1
for left < right {
currentSum := nums[i] + nums[left] + nums[right]
if currentSum == 0 {
answers = append(answers, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if currentSum < 0 {
left++
} else {
right--
}
}
}
return answers
}
Container With Most Water #
長さnのintのスライスheightが与えられます。
n本の垂直線が引かれており、i番目の直線の2つの両端は(i, 0)と(i, height[i])となっています。
コンテナを形成する2本の垂直線を見つけ、そのコンテナが最も多くの水を含むようにします。
コンテナが最も多くの水を含むときの量を返してください。
自力で解けなかったので、下記を参考に解きました。
<title data-react-helmet="true">Container With Most Water
func maxArea(height []int) int {
maxWater := 0
leftPointer := 0
rightPointer := len(height) - 1
for leftPointer != rightPointer {
leftHeight := height[leftPointer]
rightHeight := height[rightPointer]
height := min(leftHeight, rightHeight)
width := rightPointer - leftPointer
water := height * width
if water > maxWater {
maxWater = water
}
if leftHeight < rightHeight {
leftPointer++
} else {
rightPointer--
}
}
return maxWater
}