当前位置：首页 > news >正文

二十天刷leetcode【hot100】算法- day2[后端golang]

news 2024/11/21 1:31:36

指针

6.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。
在这里插入图片描述
leetcode 15. 三数之和

题解

该题需要先从小到大排序，后需要建立三个指针，从头到尾完成遍历，第一层遍历决定第一个元素(first)，第二层遍历决定第二个元素(second = first + 1)跟第三个元素(third,初始化为最大的元素)。其中对于确认了first后，就要对second和third进行首尾遍历。原则为：三者相加，大于target则左移third，小于则右移second。另外需要注意,不能输出相同的元素，又因为该数组一开始就经过排序，则可以跳过相等的两个元素。

package mainimport ("fmt""sort"
)func threeSum(nums []int) [][]int {var res [][]intsort.Ints(nums) // 使用sort包中的Ints函数对切片进行排序for first := 0; first < len(nums); first++ {if first > 0 && nums[first] == nums[first-1] {continue // 跳过重复元素}target := -nums[first]third := len(nums) - 1for second := first + 1; second < len(nums)-1; second++ {if second > first+1 && nums[second] == nums[second-1] {continue // 跳过重复元素}for second < third && nums[second]+nums[third] > target {third-- // 向头部收缩}if second == third {break // 相等了，则直接跳出内层循环}if nums[second]+nums[third] == target {res = append(res, []int{nums[first], nums[second], nums[third]})}}}return res
}func main() {arr := threeSum([]int{-1, 0, 1, 2, -1, -4})fmt.Println(arr) // 输出: [[-1 -1 2] [-1 0 1]]
}

7.最接近的两数和 - 字节-上海

给出一个数组和一个目标值，找出两个和最接近目标值的子项

题解

数组从大到小排序，双指针首尾收缩遍历，当前两者相加大于目标则收缩尾部，小于则收缩头部，用res记录最接近目标值的值

package mainimport ("fmt""math""sort"
)func testNear(arrNear []int, targetNear int) int {// 排序sort.Ints(arrNear)left, right := 0, len(arrNear)-1var res intfor left < right {temp := arrNear[left] + arrNear[right]if temp == targetNear {return temp // 直接返回结果，因为找到了精确匹配} else if temp > targetNear {right--} else {left++}// 更新最接近的值if math.Abs(float64(targetNear-res)) > math.Abs(float64(targetNear-temp)) {res = temp}}return res
}func main() {arrNear := []int{24, 69, 14, 37}targetNear := 60nearP := testNear(arrNear, targetNear)fmt.Printf("最接近的值是: %d\n", nearP) // 61
}

8 接雨水 - 腾讯cdg

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
在这里插入图片描述
leetcode 42. 接雨水

题解

一：动态规划

用dp数组记录下标i及其左（leftMax ）右（rightMax）边的所有柱子的最大高度。dp数组初始化，leftMax[0] = height[0];和rightMax[len - 1] = height[len - 1];。dp数组遍历过程中，左右侧的值与当值的高度进行对比，更新dp数组

leftMax[i] = Math.max(leftMax[i - 1], height[i]);
rightMax[j] = Math.max(rightMax[j + 1], height[j]);

左右侧最高的两条柱子中，矮的那条减自身高度，即为当前柱子能接的水

// 动态规划
package mainimport ("fmt"
)func trapDp(height []int) int {if len(height) == 0 {return 0}len := len(height)// 下标i及其左边的所有柱子的最大高度leftMax := make([]int, len)leftMax[0] = height[0]// 下标i及其右边的所有柱子的最大高度rightMax := make([]int, len)rightMax[len-1] = height[len-1]// 计算每个位置左侧的最大高度for i := 1; i < len; i++ {leftMax[i] = max(leftMax[i-1], height[i])}// 计算每个位置右侧的最大高度for j := len - 2; j >= 0; j-- {rightMax[j] = max(rightMax[j+1], height[j])}var ans int// 计算总的水量for k := 0; k < len; k++ {// 左右侧最高的两条柱子中，矮的那条减自身高度，即为当前柱子能接的水ans += min(leftMax[k], rightMax[k]) - height[k]}return ans
}// 辅助函数：返回两个整数中的较大值
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() {height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}result := trapDp(height)fmt.Println(result) // 输出: 6
}

二、双指针

头尾双指针收缩遍历，详细见代码解

package mainimport ("fmt"
)func trap(height []int) int {if len(height) == 0 {return 0}left, right := 0, len(height)-1leftMax, rightMax := height[left], height[right]ans := 0for left < right {// 更新左右两侧的最大值if height[left] > leftMax {leftMax = height[left]}if height[right] > rightMax {rightMax = height[right]}// 移动较矮的指针并累加可以积累的雨水if height[left] < height[right] {ans += leftMax - height[left]left++} else {ans += rightMax - height[right]right--}}return ans
}func main() {height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}result := trap(height)fmt.Println(result) // 输出: 6
}

9 无重复字符串的最长子串

给定一个字符串s ，请你找出其中不含有重复字符的最长
子串的长度。
在这里插入图片描述
leetcode 3.无重复字符串的最长子串

题解

双指针搭配set, 用set去重，左指针移动, set移除元素，右指针移动，且右指针元素不存在于set中，则加入set，最后根据左右指针位置更新最大长度

package mainimport ("fmt"
)func lengthOfLongestSubstring(s string) int {// 使用map作为set，用于存储当前考虑的子字符串中的字符charSet := make(map[rune]bool)left, right := 0, -1ans := 0for left < len(s) {if left > 0 {// 移除左指针指向的字符delete(charSet, rune(s[left-1]))}// 尝试移动右指针for right+1 < len(s) && !charSet[rune(s[right+1])] {// 右指针指向的字符不在集合中，则加入集合并移动右指针charSet[rune(s[right+1])] = trueright++}// 更新最长子字符串的长度ans = max(ans, right-left+1)// 移动左指针left++}return ans
}// 辅助函数：返回两个整数中的较大值
func max(a, b int) int {if a > b {return a}return b
}func main() {s := "abcabcbb"result := lengthOfLongestSubstring(s)fmt.Println(result) // 输出: 3
}

10 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
在这里插入图片描述
leetcode 438.找到字符串中所有字母异位词

题解

使用《位置数组》记录当前值在英文字母中的顺序。初始化遍历先把p字符串和s下标0到pLen - 1的子串遍历完。如这个时候如果位置数组相等，则把下标0推进数组。后将s剩下的数据遍历完成。

package mainimport ("fmt"
)func findAnagrams(s, p string) []int {sLen, pLen := len(s), len(p)if sLen < pLen {return []int{}}ans := []int{}sCount := make([]int, 26)pCount := make([]int, 26)// 初始化pCount和sCount（s的前pLen个字符）for i := 0; i < pLen; i++ {sCount[s[i]-'a']++pCount[p[i]-'a']++}// 检查初始窗口是否匹配if arraysEqual(sCount, pCount) {ans = append(ans, 0)}// 滑动窗口for i := 0; i < sLen-pLen; i++ {// 移除窗口左侧的字符sCount[s[i]-'a']--// 添加窗口右侧的字符sCount[s[i+pLen]-'a']++// 检查窗口是否匹配if arraysEqual(sCount, pCount) {ans = append(ans, i+1)}}return ans
}// 辅助函数：检查两个整数数组是否相等
func arraysEqual(a, b []int) bool {if len(a) != len(b) {return false}for i := range a {if a[i] != b[i] {return false}}return true
}func main() {s := "cbaebabacd"p := "abc"arr := findAnagrams(s, p)fmt.Println(arr) // 输出: [0 6]
}