leetcode 刷题视频(7) - 哈希表与字符串

2024-05-06 01:38
文章标签 leetcode 视频 字符串 哈希 刷题 表与

本文主要是介绍leetcode 刷题视频(7) - 哈希表与字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哈希表与字符串

预备知识

拉链法解决冲突，构造哈希表。

#include <iostream>
using namespace std;
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};int hash_func(int key, int table_len) { return key % table_len; }
void insert(ListNode *hash_table[], ListNode *node, int table_len) {int hash_key = hash_func(node->val, table_len);node->next = hash_table[hash_key]->next;hash_table[hash_key] = node;
}
bool search(ListNode *hash_table[], int value, int table_len) {int hash_key = hash_func(value, table_len);ListNode *head = hash_table[hash_key];while (head) {if (head->val == value) {return true;}head = head->next;}return false;
}

TABLE_LEN取为质数，冲突比其它数字少。

STL的map

#include <iostream>
#include <map>
using namespace std;int main() {map<string, int> hash_map;string str1 = "abc";string str2 = "aaa";string str3 = "xxxxxx";hash_map[str1] = 1;hash_map[str2] = 2;hash_map[str3] = 100;if (hash_map.find(str1) != hash_map.end()) {printf("map[%s]=%d\n", str1.c_str(), hash_map[str1]);}for (auto &it : hash_map) {printf("hasp_map[%s]=%d\n", it.first.c_str(), it.second);}return 0;
}

问题1 最长回文串

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1

Example 3:

Input: s = "bb"
Output: 2

Constraints:

  • 1 <= s.length <= 2000
  • s consits of lower-case and/or upper-case English letters only.

链接：https://leetcode-cn.com/problems/longest-palindrome/

使用字符串s中的字符，任意组合(可以交换顺序)，生成新字符串。若生成的字符串为回文字符串，需要除了中心字符，其余字符只要头部出现，尾部就要对应出现。

思路：

  1. 利用字符哈希方法，统计字符串中所有字符数量；

  2. 设置最长回文串偶数字符长度为 max_length = 0；

  3. 设置是否有中心点标记 flag = 0；

  4. 遍历每一个字符，字符数为 count，若 count 为偶数，则max_length+=count；若count为奇数，则max_length+=count-1，flag=1；

  5. 最终回文串长度为max_length+flag。

问题2 词语模式

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", s = "dog dog dog dog"
Output: false

Constraints:

  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters.
  • 1 <= s.length <= 3000
  • s contains only lower-case English letters and spaces ' '.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.

链接：https://leetcode-cn.com/problems/word-pattern/

在这里插入图片描述

在这里插入图片描述

这个遇到的最大问题是：函数的输入一直搞混 pattern 和 s。（在字符串问题里遇到的都是这种错误）
另外pattern和单词的数量必须相等；
只建立单向映射是不行的，比如只建立pattern到单词的映射，如果新pattern出现，那么会不知道单词是不是也是新出现；如果只建立单词到pattern的映射，如果新单词出现，也不知道pattern是不是新的。检测字符出现比检测单词出现代价小一些，所以后者好一些。

问题3 相同字符的词语分组

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lower-case English letters.

链接：https://leetcode-cn.com/problems/group-anagrams/

方法1 字符排序

思路：设置字符串到字符串向量的哈希表anagram，遍历输入的字符串列表strs中的单词strs[i]：

  1. 设置临时变量str=strs[i]，对str进行排序
  2. 若str未出现在anagram中，设置str到一个空字符串向量的映射
  3. 将strs[i]添加至字符串向量anagram[str]中
class Solution {
public:vector<vector<string> > groupAnagrams(vector<string> &strs) {map<string, vector<string> > anagram;vector<vector<string> > result;for (auto &i : strs) {string str = i;sort(str.begin(), str.end());if (anagram.find(str) == anagram.end()) {vector<string> item;anagram[str] = item;}anagram[str].push_back(i);}result.reserve(anagram.size());for (auto &it : anagram) {result.push_back(it.second);}return result;}
};

方法2 统计字符数量

以字符到个数的vector为key，以字符串向量为value。

步骤：

  1. 统计各个字符数量，存储至vec；
  2. 若vec未出现在anagram中，则设置vec到一个空向量的映射；
  3. 将strs[i]添加到字符串向量anagram[vec]中；

问题4 无重复字符的最长子串

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路：

  1. 设置一个记录字符数量的字符哈希 char_map
  2. 设置一个记录当前满足条件的最长子串 word
  3. 设置两个指针 i 与 begin 指向字符串的第一个字符
  4. 设置最长满足条件的子串的长度 result
  5. i 指针向后逐个扫描字符串中的字符，在这个过程中，使用char_map记录字符数量；
    • 如果word中没出现该字符，对word尾部添加字符并检查result是否需要更新
    • 否则begin指针向前移动，更新char_map中的字符数量，直到s[i]的数量为1

在这里插入图片描述

class Solution {
public:int lengthOfLongestSubstring(string s) {int begin = 0;int result = 0;string word;int char_map[128] = {0};for (int i = 0; i < s.length(); i++) {char_map[s[i]]++;if (char_map[s[i]] == 1) {word += s[i];if (result < word.length()) {result = word.length();}} else {cout << char_map[s[begin]] << endl;while (/*begin < i &&*/char_map[s[i]] > 1) {char_map[s[begin]]--;begin++;}word = s.substr(begin, i - begin + 1); // substr(begin, length)}}return result;}
};

上面的代码效率太低了，更新一下稍微快点的

   int lengthOfLongestSubstring(string s) {if (s.empty()) return 0;int winStart = 0; // 当前窗口的起点int maxLeft = 0, maxRight = 0; // 结果的左右边界vector<int> lastPosition(128, -1);lastPosition[s[0]] = 0; // 第一个字母特殊处理，标记本单词的位置for (int i = 1; i < s.size(); i++) { // 从第二个字母开始if (lastPosition[s[i]] >= 0) { // 如果之前存在这个字符// 则依次标记为-1int end = lastPosition[s[i]];for (int j = winStart; j <= end; j++) {lastPosition[s[j]] = -1;}winStart = end + 1;  // 更新窗口起点}lastPosition[s[i]] = i;if (i - winStart > maxRight - maxLeft) {maxLeft = winStart;maxRight = i;}}return maxRight - maxLeft + 1;}

问题5 找出重复序列

All DNA is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T', for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

Constraints:

  • 0 <= s.length <= 105
  • s[i] is 'A', 'C', 'G', or 'T'.

找出长度为10且超过1次的字符串。

链接：https://leetcode-cn.com/problems/repeated-dna-sequences

方法1 简单思路

将所有长度为10的子串加入hash map中，并记录子串数量。

方法2 设计一个序列到int的映射

AGCT只有4种可能可以用2bit表示，10个字符可以用20bit表示，int还是能盛下的。

之后的思路和方法1一样。

本来映射应该使用map结构的，但是这道题使用数组结构竟然比map还省内存，震惊！

class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {if (s.size() <= 10) return {};vector<string> result;unsigned chMap[128];chMap['A'] = 0;chMap['C'] = 1;chMap['G'] = 2;chMap['T'] = 3;char state[2 << 20 + 1] = {0}; // 0表示未出现 1表示第一次出现，2表示多次出现 [如果用bitset存储会更省内存]// 处理第一个单词unsigned key = 0;for (int j = 0; j < 10; j++) {int index = 9 - j;key += chMap[s[index]] << (j * 2); // 之前少写了加号}state[key] = true;for (int i = 10; i < s.size(); i++) {key <<= 2; // 左移两位key &= 0xfffff; // 去掉高位key += chMap[s[i]];if (state[key] == 0) {state[key] = 1;} else {if (state[key] == 1) { // 仅处理第一次出现result.push_back(s.substr(i - 9, 10));state[key] = 2;}}}return result;}
};

问题6 最小窗口子串

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

链接：https://leetcode-cn.com/problems/minimum-window-substring/

在这里插入图片描述

class Solution {
public:string minWindow(string s, string t) {const int MAX_ARRAY_LEN = 128;int map_t[MAX_ARRAY_LEN] = {0};int map_s[MAX_ARRAY_LEN] = {0};vector<int> vec_t;// 统计T中有哪些字符for (char c : t) {map_t[c]++;}//  将T中出现的字符存储到vec_t中for (int i = 0; i < MAX_ARRAY_LEN; i++) {if (map_t[i] > 0)vec_t.push_back(i);}int windows_begin = 0;string result;for (int i = 0; i < s.length(); ++i) {map_s[s[i]]++;while (windows_begin < i) {char begin_ch = s[windows_begin];if (map_t[begin_ch] == 0) {windows_begin++;} else if (map_s[begin_ch] > map_t[begin_ch]) {map_s[begin_ch]--;windows_begin++;} else { // ms <= mt && mt != 0break;}}if (is_window_ok(map_s, map_t, vec_t)) {int new_window_len = i - windows_begin + 1;if (result.empty() || new_window_len < result.length()) {result = s.substr(windows_begin, new_window_len);}}}return result;}private:// 检查 s 是否包括 tbool is_window_ok(int map_s[], int map_t[], vector<int> &vec_t) {for (int i = 0; i < vec_t.size(); i++) {if (map_s[vec_t[i]] < map_t[vec_t[i]]) {return false;}}return true;}
};

leetcode 官方解法：test

这篇关于leetcode 刷题视频(7) - 哈希表与字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/963184。

相关文章

Python中反转字符串的常见方法小结

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函
阅读更多...
Python使用OpenCV实现获取视频时长的小工具

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文
阅读更多...
MySQL查询JSON数组字段包含特定字符串的方法

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案（推荐）2. 模糊匹配方案参数化查询示例使用场景建议性能优
阅读更多...
MySQL 获取字符串长度及注意事项

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2
阅读更多...
Springboot3+将ID转为JSON字符串的详细配置方案

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》：本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制（可选）4. OpenAPI (Spri
阅读更多...
使用Python实现base64字符串与图片互转的详细步骤

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意
阅读更多...
golang float和科学计数法转字符串的实现方式

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》：本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float
阅读更多...
Python如何判断字符串中是否包含特殊字符并替换

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一：使用正则表达式方法二：手动检查特定字符Pytho
阅读更多...
MySQL 字符串截取函数及用法详解

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length)：从右侧截取指定长度的字符SUBST
阅读更多...
Python将字符串转换为小写字母的几种常用方法

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》：本文主要介绍Python中将字符串大写字母转小写的四种方法：lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()（最简单）二、手动遍历 + ASCII 码转换三、使用 str.tr
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2