【代码随想录——哈希表】

1.哈希表理论基础

首先什么是 哈希表，哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。
在这里插入图片描述
那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

2. 有效的字母异位词

在这里插入图片描述

// 判断字符串 t 是否是字符串 s 的字母异位词
func isAnagram(s string, t string) bool {
    charCount := make(map[rune]int,0)
    // 若字符串长度不同，直接返回 false
    if len(s) != len(t) {
        return false
    }
    // 将字符串转换为字符数组，并对字符数组进行排序
    sChars := []rune(s)
    tChars := []rune(t)
    
    for i:=0;i<len(sChars);i++{
        if _,ok:=charCount[sChars[i]];ok{
            charCount[sChars[i]]++
        }else{
            charCount[sChars[i]]=1
        }
    }

    for i:=0;i<len(tChars);i++{
        char,ok := charCount[tChars[i]]
        if !ok || char==0{
            return false
        }
        charCount[tChars[i]]--
    }
    return true
}

这是官方的一种更简洁的写法：

func isAnagram(s string, t string) bool {
    if len(s)!=len(t){
        return false
    }
    s_map:=[26]int{}
    t_map:=[26]int{}
    for i:=0;i<len(s);i++{
        s_map[s[i]-'a']++
        t_map[t[i]-'a']++
    }
    return s_map==t_map
}

2.1 字母异位词分组

在这里插入图片描述

2.1.1 第一次的写法，有点慢

func groupAnagrams(strs []string) [][]string {
	map_style := make([][26]int, 0)
	str_list := make([][]string, 0)
	map_index := 0
	for _, str := range strs {
		strMap := changeStrToMap(str)
		index := findCorrectStyle(strMap, map_style, map_index)
		if index == -1 {
			//表明这是一个新的style
            map_style = append(map_style, strMap)
            temp := []string{str}
			str_list = append(str_list, temp)
			map_index++
		} else {
			str_list[index] = append(str_list[index], str)
		}
	}
	return str_list[0:map_index]
}

func changeStrToMap(s string) [26]int {
	s_map := [26]int{}
	for i := 0; i < len(s); i++ {
		s_map[s[i]-'a']++
	}
	return s_map
}

func findCorrectStyle(strMap [26]int, map_style [][26]int, map_index int) int {
	for i := 0; i < map_index; i++ {
		if strMap == map_style[i] {
			return i
		}
	}
	return -1
}

2.1.2 学习一下高手的写法

确实快，主体思路没什么问题，就是不知道数组也能当做map的key。

func groupAnagrams(strs []string) [][]string {
    // 没想到数组也可以当做key
    hmap := make(map[[26]int][]string)
    for _, str := range strs {
        // key 表示str 的字符最多26个，每个字符有多少个
        key := [26]int{}
        // 计数
        for _, ch := range str {
            // idx 代表字符距离小写字母的距离, b 的话是1
            idx := ch - 'a'
            key[idx] ++
        }
        hmap[key] = append(hmap[key], str)
    }

    result := make([][]string, 0, len(hmap))
    for _, v := range hmap {
        result = append(result, v)
    }   
    return result
}

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

在这里插入图片描述

func findAnagrams(s string, p string) []int {
	res := make([]int, 0)
	if len(s) < len(p) {
		return res
	}
	// 用来存储p中各个小写字母出现的次数
	pattern := [26]int{}
	temp := [26]int{}
	for i := 0; i < len(p); i++ {
		pattern[p[i]-'a']++
		temp[s[i]-'a']++
	}
	if pattern == temp {
		res = append(res, 0)
	}
	for i := 0; i < len(s)-len(p); i++ {
		temp[s[i]-'a']--
		temp[s[i+len(p)]-'a']++
		if pattern == temp {
			res = append(res, i+1)
		}
	}
	return res
}

3. 两个数组的交集

在这里插入图片描述

func intersection(nums1 []int, nums2 []int) []int {
    mp := make(map[int]struct{},0)
    res := make([]int,0)
    // 遍历nums1
    for _,num := range(nums1){
        mp[num] = struct{}{}
    }
    // 遍历nums2
    for _,num := range(nums2){
        _,ok := mp[num]
        if ok{
        	// 查找到相同元素，加入答案。并从mp中删除
            res = append(res,num)
            delete(mp,num)
        }
    }
    return res
}

3.1 两个数组的交集②

在这里插入图片描述
和上面的代码只有一点点区别，区别在于这道题目需要记录元素出现的个数。

func intersect(nums1 []int, nums2 []int) []int {
    mp := make(map[int]int,0)
    res := make([]int,0)
    // 遍历nums1
    for _,num := range(nums1){
        _,ok := mp[num]
        if !ok{
            mp[num]=1
        }else{
            mp[num]++
        }
    }
    // 遍历nums2
    for _,num := range(nums2){
        _,ok := mp[num]
        if ok{
        	// 查找到相同元素，加入答案。并从mp中删除
            res = append(res,num)
            mp[num]--
            if mp[num]==0{
              delete(mp,num)
            }
        }
    }
    return res
}

4.快乐数

在这里插入图片描述

func isHappy(n int) bool {
    mp := make(map[int]struct{},0)
    for n != 1{
        _,ok := mp[n]
        if ok {
            //这个数见过
            return false
        }
        //没见过，就记录一下
        mp[n] = struct{}{}
        n = getSum(n)
    }
    return true
}

func getSum(n int)int{
    res := 0
    for n>0{
        res = res + (n%10)*(n%10)
        n = n/10
    }
    return res
}

5. 两数之和

在这里插入图片描述

func twoSum(nums []int, target int) []int {
    m:=make(map[int]int)
    for i,n:= range nums {
        j,ok:= m[target-n]
        if ok {
            return []int{i,j}
        }
        m[n]=i
    }
    return []int{}
}

6. 四数相加②

在这里插入图片描述
思路：两两组合

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    res := 0
    mp := make(map[int]int,len(nums1)*len(nums1))
    //循环遍历nums1和nums2两个数组
    for i:=0;i<len(nums1);i++{
        for j:=0;j<len(nums2);j++{
            num := nums1[i] + nums2[j]
            if _,ok := mp[num];ok{
                mp[num]++
            }else{
                mp[num]=1
            }
        }
    }
    //循环遍历nums3和nums4两个数组
    for i:=0;i<len(nums3);i++{
        for j:=0;j<len(nums4);j++{
            num := nums3[i] + nums4[j]
            if _,ok := mp[-num];ok{
                res += mp[-num]
            }
        }
    }
    return res
}

7.赎金信

在这里插入图片描述

func canConstruct(ransomNote string, magazine string) bool {
    pattern1 := [26]int{}
    for i:=0;i<len(magazine);i++{
        pattern1[magazine[i]-'a']++
    }
    for i:=0;i<len(ransomNote);i++{
        pattern1[ransomNote[i]-'a']--
        if pattern1[ransomNote[i]-'a']<0{
            return false
        }
    }
    return true
}

8.三数之和

在这里插入图片描述
方法一：哈希表

这题不太适合使用hash来做

方法二：双指针，需要先排序。感觉不够快

func threeSum(nums []int) [][]int {
	var result [][]int
	if nums == nil || len(nums) < 3 {
		return result
	}
	slices.Sort(nums)
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			return result
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		L := i + 1
		R := len(nums) - 1
		for L < R {
			if nums[i]+nums[L]+nums[R] == 0 {
				sub := []int{nums[i], nums[L], nums[R]}
				result = append(result, sub)
				for L < R && nums[L] == nums[L+1] {
					L += 1
				}
				for L < R && nums[R] == nums[R-1] {
					R -= 1
				}
				L += 1
				R -= 1
			}else if nums[i]+nums[L]+nums[R] > 0 {
				R -= 1
			} else {
				L += 1
			}
		}
	}
	return result
}

9.四数之和

在这里插入图片描述

9.1 利用map的写法

我的方法无法通过测试用例，会超时
在这里插入图片描述

func fourSum(nums []int, target int) [][]int {
	res := make(map[[4]int]struct{}, 0)
	mp := make(map[int][]int, 0)
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			temp := nums[i] + nums[j]
			arr, ok := mp[temp]
			if !ok {
				slice := make([]int, 2)
				slice[0] = i
				slice[1] = j
				mp[temp] = slice
			} else {
				//已有
				arr = append(arr, i)
				arr = append(arr, j)
				mp[temp] = arr
			}
		}
	}
	for key, arr1 := range mp {
		toFind := target - key
		arr2, ok := mp[toFind]
		if !ok {
			continue
		}
		for i := 0; i < len(arr1)/2; i++ {
			for j := 0; j < len(arr2)/2; j++ {
				index_a, index_b := arr1[i*2], arr1[i*2+1]
				index_c, index_d := arr2[j*2], arr2[j*2+1]
				if index_a == index_c || index_a == index_d || index_b == index_c || index_b == index_d {
					continue
				}
				item := []int{nums[index_a], nums[index_b], nums[index_c], nums[index_d]}
				sort.Ints(item)
				res[[4]int{item[0], item[1], item[2], item[3]}] = struct{}{}
			}
		}
	}
	back := [][]int{}
	for key, _ := range res {
		back = append(back, key[:])
	}
	return back
}

9.2 使用双指针的解法

两层for循环，套用一个左右指针。可以通过剪枝提高算法的运行速度。

func fourSum(nums []int, target int) [][]int {
	if len(nums) < 4 {
		return nil
	}
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums)-3; i++ {
		n1 := nums[i]
		// if n1 > target { // 不能这样写,因为可能是负数
		// 	break
		// }
		if i > 0 && n1 == nums[i-1] {  // 对nums[i]去重
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			n2 := nums[j]
			if j > i+1 && n2 == nums[j-1] {  // 对nums[j]去重
				continue
			}
			l := j + 1
			r := len(nums) - 1
			for l < r {
				n3 := nums[l]
				n4 := nums[r]
				sum := n1 + n2 + n3 + n4
				if sum < target {
					l++
				} else if sum > target {
					r--
				} else {
					res = append(res, []int{n1, n2, n3, n4})
					for l < r && n3 == nums[l+1] { // 去重
						l++
					}
					for l < r && n4 == nums[r-1] { // 去重
						r--
					}
					// 找到答案时,双指针同时靠近
					r--
					l++
				}
			}
		}
	}
	return res
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/599377.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

高素质高学历婚恋相亲交友平台有哪些？分享我的网上找对象成功脱单经历！

高素质高学历婚恋相亲交友平台有哪些？分享我的网上找对象成功脱单经历！

尽管觉得在社交软件上找到真爱的可能性很小&#xff0c;但我却时常看到别人成功的案例&#xff0c;这也让我跃跃欲试了。没想到&#xff0c;我真的成功了&#xff01;以下是我亲身使用过的一些方法&#xff0c;在此与大家分享&#xff0c;仅供参考哦&#xff01; &#x1f449;…
阅读更多...
c++ cpp 在类中执行线程 进行恒定计算

c++ cpp 在类中执行线程 进行恒定计算

在编程中&#xff0c;顺序执行是常见的模式&#xff0c;但是对cpu的利用率不是很高&#xff0c;采用线程池&#xff0c;又太麻烦了&#xff0c;原因是还得不断地把任务拆分&#xff0c;扫描返回值。 如果 初始化n个类的时候&#xff0c;传递数据自身即可异步计算&#xff0c;那…
阅读更多...
libcity笔记:libcity/data/batch.py

libcity笔记:libcity/data/batch.py

1 Batch 2 BatchPAD
阅读更多...
六、文件查找

六、文件查找

一、文件查找 1.查找文件内容 ​ 命令&#xff1a;grep keywords /dir_path/filename 2.查找系统命令 ​ 命令&#xff1a;which command 3.查找命令及配置文件位置 ​ 命令&#xff1a;whereis command 4.find查找 ​ find $find_path -name|-type|-perm|-size|-atime…
阅读更多...
【前端】HTML基础（3）

【前端】HTML基础（3）

文章目录 前言一、HTML基础1、表格标签1.1 基本使用1.2 合并单元格 2、列表标签2.1 无序列表2.2 有序列表2.3 自定义列表 3、 表单标签2.1 form标签2.2 input标签2.3 label标签2.4 select标签2.5 textarea标签 4、无语义标签5、HTML特殊字符 前言 这篇博客仅仅是对HTML的基本结…
阅读更多...
RVM（相关向量机）、CNN_RVM（卷积神经网络结合相关向量机）、RVM-Adaboost（相关向量机结合Adaboost）

RVM（相关向量机）、CNN_RVM（卷积神经网络结合相关向量机）、RVM-Adaboost（相关向量机结合Adaboost）

当我们谈到RVM&#xff08;Relevance Vector Machine&#xff0c;相关向量机&#xff09;、CNN_RVM&#xff08;卷积神经网络结合相关向量机&#xff09;以及RVM-Adaboost&#xff08;相关向量机结合AdaBoost算法&#xff09;时&#xff0c;每种模型都有其独特的原理和结构。以…
阅读更多...
streamlit通过子目录访问

streamlit通过子目录访问

运行命令&#xff1a; streamlit hello 系统默认使用8501端口启动服务&#xff1a; 如果想通过子目录访问服务&#xff0c;可以这么启动服务 streamlit hello --server.baseUrlPath "app" 也可以通过以下命令换端口 streamlit hello --server.port 9999 参考&…
阅读更多...
2024最新CTF入门的正确路线

2024最新CTF入门的正确路线

目录 前言 一、什么是CTF比赛&#xff1f; 二、CTF比赛的流程 三、需要具备的知识 四、总结 前言 随着网络安全意识的增强&#xff0c;越来越多的人开始涉足网络安全领域&#xff0c;其中CTF比赛成为了重要的学习和竞赛平台。本人从事网络安全工作多年&#xff0c;也参加过…
阅读更多...
甲小姐对话柳钢：CEO对股东最大的责任，是对成功的概率负责｜甲子光年

甲小姐对话柳钢：CEO对股东最大的责任，是对成功的概率负责｜甲子光年

只有看见最微小的事物&#xff0c;才能洞悉伟大的定律。 来源&#xff5c;甲子光年 作者&#xff5c;甲小姐 刘杨楠 编辑&#xff5c;栗子 商业史上&#xff0c;职业经理人成为“空降CEO”的故事往往胜少败多。 “究其原因有三条——容易自嗨、喊口号&#xff1b;不顾公司历…
阅读更多...
笔试强训Day19 数学知识 动态规划 模拟

笔试强训Day19 数学知识 动态规划 模拟

[编程题]小易的升级之路 题目链接&#xff1a;小易的升级之路__牛客网 思路&#xff1a; 按题目写即可 注意辗转相除法。 AC code&#xff1a; #include<iostream> using namespace std; int gcd(int a, int b) {return b ? gcd(b, a % b) : a; } int main() {int n…
阅读更多...
三步学会苹果手机怎么关震动的方法！

三步学会苹果手机怎么关震动的方法！

苹果手机的震动功能在某些情况下可能会被认为是不必要的&#xff0c;比如在会议、课堂或者晚间睡眠时。因此&#xff0c;学会如何关闭苹果手机的震动功能是非常实用的。苹果手机怎么关震动&#xff1f;在本文中&#xff0c;我们将介绍三个步骤&#xff0c;帮助你关闭苹果手机的…
阅读更多...
openEuler 22.03 GPT分区表模式下磁盘分区管理

openEuler 22.03 GPT分区表模式下磁盘分区管理

目录 GPT分区表模式下磁盘分区管理parted交互式创建分区步骤 1 执行如下步骤对/dev/sdc磁盘分区 非交互式创建分区步骤 1 输入如下命令直接创建分区。 删除分区步骤 1 执行如下命令删除/dev/sdc1分区。 GPT分区表模式下磁盘分区管理 parted交互式创建分区 步骤 1 执行如下步骤…
阅读更多...
ThingsBoard版本控制配合Gitee实现版本控制

ThingsBoard版本控制配合Gitee实现版本控制

1、概述 2、架构 3、导出设置 4、仓库 5、同步策略 6、扩展 7、案例 7.1、首先需要在Giitee上创建对应同步到仓库地址 ​7.2、giit仓库只能在租户层面进行配置 7.3、 配置完成后&#xff1a;检查访问权限。显示已成功验证仓库访问&#xff01;表示配置成功 7.4、添加设…
阅读更多...
喜报 | 擎创科技荣获NIISA联盟2023年度创新技术特等奖！

喜报 | 擎创科技荣获NIISA联盟2023年度创新技术特等奖！

为深入实施创新驱动发展战略&#xff0c;紧紧把握全球科技革命和产业变革方向&#xff0c;密切跟踪前沿科技新趋势&#xff0c;经科技部中国民营促进会业务主管部门批准以及国家互联网数据中心产业技术创新战略联盟&#xff08;以下简称联盟&#xff09;总体工作安排&#xff0…
阅读更多...
前端nginx（windows操作系统）学习配置开发验证

前端nginx（windows操作系统）学习配置开发验证

Nginx概述 Nginx 作为负载均衡在 Linux 系统上具备很好的并发性能&#xff0c;并且占用极小的内存。但是在 Windows 系统上并不支撑较高并发&#xff0c;所以在Windows系统上选用Nginx作为负载均衡&#xff0c;需要考虑并发情况。 若并发需求低于 300&#xff0c;部署集群仅以…
阅读更多...
LMdeploy推理实践

LMdeploy推理实践

在inter-studio平台上&#xff0c;下载模型&#xff0c;体验lmdeploy 下载模型 这里是因为平台上已经有了internlm2模型&#xff0c;所以建立一个符号链接指向它&#xff0c;没有重新下载 ln -s /root/share/new_models/Shanghai_AI_Laboratory/internlm2-chat-1_8b /root/如…
阅读更多...
四级英语翻译随堂笔记

四级英语翻译随堂笔记

降维表达&#xff1a;中译英&#xff0c;英译英 没有强调主语&#xff0c;没有说明主语&#xff1a;用被动 但如果实在不行&#xff0c;再增添主语 不会就不翻译&#xff0c;不要乱翻译 以xxx为背景&#xff1a;against the backdrop of the xxx eg:against the backdrop of…
阅读更多...
关于执行CLAM的代码的一些需要记录的点

关于执行CLAM的代码的一些需要记录的点

文章链接&#xff1a;[2004.09666] Data Efficient and Weakly Supervised Computational Pathology on Whole Slide Images (arxiv.org) 代码链接&#xff1a;GitHub - mahmoodlab/CLAM: Data-efficient and weakly supervised computational pathology on whole slide images…
阅读更多...
如何将 ONLYOFFICE 协作空间服务器版更新至 2.5

如何将 ONLYOFFICE 协作空间服务器版更新至 2.5

最近我们发布了 ONLYOFFICE 协作空间 2.5 云端版。好消息&#xff0c;该文档协作平台的自托管版本也已推出。现在&#xff0c;您可以轻松更新协作空间的实例&#xff0c;在本地尝试所有新功能。阅读本文了解更多信息。 ONLYOFFICE 协作空间 2.5 新功能 更新到 ONLYOFFICE 协作…
阅读更多...
暴雨发布大模型专用分布式全闪存储

暴雨发布大模型专用分布式全闪存储

近日&#xff0c;暴雨信息发布为大模型专门优化的分布式全闪存储AVERSE系列。该系列依托暴雨信息自研分布式文件系统&#xff0c;搭载新一代数据加速引擎Xdata&#xff0c;通过盘控协同、GPU直访存储、全局一致性缓存等技术为AI大模型数据归集、训练、数据归档与管理等阶段提供…
阅读更多...
最新文章

Copyright @ 2022~2023