链表
今日任务
242.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母
//定义一个数组叫做record用来上记录字符串s里字符出现的次数。
//需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
//再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。
func isAnagram(s string, t string) bool {
record := [26]int{}
for _,v := range s {
record[v - 'a'] ++
}
for _,v := range t {
record[v - 'a'] --
}
return record == [26]int{}
}
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
records := [26]int{}
for index := 0; index < len(s); index++ {
if s[index] == t[index] {
continue
}
sCharIndex := s[index] - 'a'
records[sCharIndex]++
tCharIndex := t[index] - 'a'
records[tCharIndex]--
}
return records == [26]int{}
}
349. 两个数组的交集
题意：给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的
提示：
1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000
func intersection(nums1 []int, nums2 []int) []int {
set := make(map[int]struct{},0)
res := make([]int,0)
for _,v := range nums1{
if _,sv := set[v];!sv{
set[v] = struct{}{}
}
}
for _,v := range nums2{
if _,sv := set[v];sv{
res = append(res,v)
delete(set,v)
}
}
return res
}
第202题. 快乐数
力扣题目链接(opens new window)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19 输出：true 解释： 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
func getSum(v int) int{
res := 0
for v > 0 {
res += (v % 10) * (v % 10)
v = v / 10
}
return res
}
func isHappy(n int) bool {
m := make(map[int]bool)
for n != 1 && !m[n]{
n,m[n] = getSum(n),true
}
return n == 1
}
//2 4 16 37 58 89 145 42 20 4
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
这里知识点主要是 a,b := map[key] a接收的是v b接受的是存在不，是一个bool
func twoSum(nums []int, target int) []int {
mapv := make(map[int]int)
for i,v := range nums{
if val,isexist := mapv[target - v]; isexist{
return []int{val,i}
}
mapv[v] = i
}
return []int{}
}
第454题.四数相加II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如:
输入:
A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出:
2
解释:
两个元组如下:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
res := 0
map12 := make(map[int]int)
for _,i := range nums1{
for _,j := range nums2{
map12[i+j]++
}
}
for _,k := range nums3{
for _,l := range nums4{
if v,isexist := map12[-k-l];isexist{
res+= v
}
}
}
return res
}
383. 赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”) -> true
func canConstruct(ransomNote string, magazine string) bool {
cnt := [26]int{}
for _,ch := range magazine{
cnt[ch - 'a'] ++
}
for _,ch := range ransomNote{
cnt[ch - 'a'] --
if cnt[ch - 'a'] < 0{
return false
}
}
return true
}
第15题. 三数之和
力扣题目链接(opens new window)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
func quicksort(nums []int,l int,r int) []int{
left := l
right := r
pvt := nums[left]
for left < right{
for left < right && nums[right] > pvt{
right --
}
if left < right{
nums[left] = nums [right]
}
for left < right && nums[left] < pvt {
left ++
}
if left < right {
nums[right] = nums[left]
}
}
nums[left] = pvt
quicksort(nums,l,left-1)
quicksort(nums,left+1,r)
return nums
}
//双指针
func threeSum(nums []int) [][]int {
res := [][]int{}
sort.Ints(nums)
for i := 0; i < len(nums); i++{
n1 := nums[i]
if n1 > 0 {
break
}
if i > 0 && nums[i] == nums[i-1]{
continue
}
l,r := i+1 ,len(nums)-1
for l < r{
n2,n3 := nums[l],nums[r]
if n1+n2+n3 == 0 {
res = append(res,[]int{n1,n2,n3})
for l < r && n2 == nums[l]{
l++
}
for l < r && n3 == nums[r]{
r--
}
}else if n1+n2+n3 < 0{
l++
}else{
r--
}
}
}
return res
}
第18题. 四数之和
力扣题目链接(opens new window)
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
func fourSum(nums []int, target int) (quadruplets [][]int) {
sort.Ints(nums)
n := len(nums)
for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target {
continue
}
for j := i + 1; j < n-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target {
continue
}
for left, right := j+1, n-1; left < right; {
if sum := nums[i] + nums[j] + nums[left] + nums[right]; sum == target {
quadruplets = append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]})
for left++; left < right && nums[left] == nums[left-1]; left++ {
}
for right--; left < right && nums[right] == nums[right+1]; right-- {
}
} else if sum < target {
left++
} else {
right--
}
}
}
}
return
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/4sum/solutions/436368/si-shu-zhi-he-by-leetcode-solution/
总结
https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/
