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。

相关文章

流媒体平台/视频监控/安防视频汇聚EasyCVR播放暂停后视频画面黑屏是什么原因？

流媒体平台/视频监控/安防视频汇聚EasyCVR播放暂停后视频画面黑屏是什么原因？

视频智能分析/视频监控/安防监控综合管理系统EasyCVR视频汇聚融合平台，是TSINGSEE青犀视频垂直深耕音视频流媒体技术、AI智能技术领域的杰出成果。该平台以其强大的视频处理、汇聚与融合能力，在构建全栈视频监控系统中展现出了独特的优势。视频监控管理系统EasyCVR平台内置了强大的视频解码、转码、压缩等技术，能够处理多种视频流格式，并以多种格式（RTMP、RTSP、HTTP-FLV、WebS
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2