当前位置: 首页 > article >正文

Golang每日一练(leetDay0006)

目录

16. 最接近的三数之和 3Sum Closest  ★★

17. 电话号码的字母组合 Letter-combinations-of-a-phone-number  ★★

18. 四数之和 4Sum  ★★

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


16. 最接近的三数之和 3Sum Closest

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2:

输入:nums = [0,0,0], target = 1
输出:0

提示:

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4

代码: 双指针

package main

import (
	"fmt"
	"sort"
)

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums) // 先排序
	res := nums[0] + nums[1] + nums[2]
	for i := 0; i < len(nums)-2; i++ {
		l, r := i+1, len(nums)-1 // 双指针
		for l < r {
			sum := nums[i] + nums[l] + nums[r]
			if abs(sum-target) < abs(res-target) {
				res = sum
			}
			if sum == target {
				return target
			} else if sum < target {
				l++
			} else {
				r--
			}
		}
	}
	return res
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {

	fmt.Println(threeSumClosest([]int{-1, 2, 1, -4}, 1))
	fmt.Println(threeSumClosest([]int{0, 0, 0}, 1))

}

输出:

2
0

循环暴力法:

package main

import "fmt"

func threeSumClosest(nums []int, target int) int {
	res, dif := 0, 20000  //见提示中参数的范围,设置20000足够
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				sum := nums[i] + nums[j] + nums[k]
				tmp := sum - target
				if tmp < 0 {
					tmp = target - sum
				}
				if tmp < dif {
					dif, res = tmp, sum
				}
			}
		}
	}
	return res
}

func main() {

	fmt.Println(threeSumClosest([]int{-1, 2, 1, -4}, 1))
	fmt.Println(threeSumClosest([]int{0, 0, 0}, 1))

}

17. 电话号码的字母组合 Letter-combinations-of-a-phone-number

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入:digits = ""
输出:[]

示例 3:

输入:digits = "2"
输出:["a","b","c"]

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

代码: 

package main

import (
	"fmt"
)

func letterCombinations(digits string) []string {
	if digits == "" {
		return []string{}
	}
	dict := map[byte][]string{
		'2': {"a", "b", "c"},
		'3': {"d", "e", "f"},
		'4': {"g", "h", "i"},
		'5': {"j", "k", "l"},
		'6': {"m", "n", "o"},
		'7': {"p", "q", "r", "s"},
		'8': {"t", "u", "v"},
		'9': {"w", "x", "y", "z"},
	}
	res := []string{""}
	for i := 0; i < len(digits); i++ {
		temp := []string{}
		for j := 0; j < len(res); j++ {
			for k := 0; k < len(dict[digits[i]]); k++ {
				temp = append(temp, res[j]+dict[digits[i]][k])
			}
		}
		res = temp
	}
	return res
}

func main() {

	fmt.Println(letterCombinations("23"))
	fmt.Println(letterCombinations(""))
	fmt.Println(letterCombinations("2"))

}

输出: 

[ad ae af bd be bf cd ce cf]
[]
[a b c]


18. 四数之和 4Sum

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • abc 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1:

输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

提示:

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

代码: 

package main

import (
	"fmt"
	"sort"
)

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums) // 先排序
	res := [][]int{}
	for i := 0; i < len(nums)-3; i++ {
		if i > 0 && nums[i] == nums[i-1] { // 跳过重复的元素
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] { // 跳过重复的元素
				continue
			}
			l, r := j+1, len(nums)-1 // 双指针
			for l < r {
				sum := nums[i] + nums[j] + nums[l] + nums[r]
				if sum == target {
					res = append(res, []int{nums[i], nums[j], nums[l], nums[r]})
					for l < r && nums[l] == nums[l+1] { // 跳过重复的元素
						l++
					}
					for l < r && nums[r] == nums[r-1] { // 跳过重复的元素
						r--
					}
					l++
					r--
				} else if sum < target {
					l++
				} else {
					r--
				}
			}
		}
	}
	return res
}

func main() {

	fmt.Println(fourSum([]int{1, 0, -1, 0, -2, 2}, 0))
	fmt.Println(fourSum([]int{2, 2, 2, 2, 2}, 8))

}

输出: 

[[-2 -1 1 2] [-2 0 0 2] [-1 0 0 1]]
[[2 2 2 2]]


🌟 每日一练刷题专栏 🌟

 持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力! 

🌟 收藏,你的青睐是我努力的方向! 

 评论,你的意见是我进步的财富!  

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


http://www.kler.cn/a/644.html

相关文章:

  • 我的Opencv
  • MySQL变量
  • 在Windows11上编译C#的实现Mono的步骤
  • 【蓝桥杯——物联网设计与开发】拓展模块3 - 温度传感器模块
  • 数据结构之线性表之顺序表
  • 操作系统导论读书笔记
  • shell-流程控制-3
  • Java实现调用第三方相关接口(附详细思路)
  • 【spring】spring如何解决bean的循环依赖
  • Java的二叉树、红黑树、B+树
  • 项目实战典型案例26——nacos的命名空间名称和id不一致带来的思考
  • C语言/动态通讯录
  • 10个最频繁用于解释机器学习模型的 Python 库
  • 全国自学考试03708《中国近现代史纲要》重点复习精要
  • 微信小程序搭建流程
  • Python+Yolov8目标识别特征检测
  • HTTP 缓存的工作原理
  • springboot健身房管理系统
  • 【云原生·Docker】常用命令
  • 「ML 实践篇」分类系统:图片数字识别
  • Java每日一练(20230313)
  • 编辑器进化 VSCode + Vim
  • AutoSAR NM【一文读懂网络管理接口】
  • 数据结构——顺序表
  • Docker Registry部署镜像私有仓库及鉴权认证
  • React 架构流程概览