leetcode解题思路分析(五十)432 - 438 题

2024-09-05 04:58

本文主要是介绍leetcode解题思路分析(五十)432 - 438 题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  1. 全O(1)的数据结构

哈希表+链表即可

class AllOne {
public:/** Initialize your data structure here. */struct Node{unordered_set<string> container;int val = 0;Node(int v):val(v){}};unordered_map<string, list<Node>::iterator> kv;list<Node> List;AllOne() {}/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */void inc(string key) {if(kv.count(key)){auto oldNode = kv[key];auto newNode = next(oldNode, 1);if(newNode == List.end() || newNode->val>oldNode->val+1){newNode = List.insert(newNode, Node(oldNode->val+1));}newNode->container.insert(key);oldNode->container.erase(key);if(oldNode->container.empty()){List.erase(oldNode);}kv[key] = newNode;} else {auto newNode = List.begin();if(List.empty() || List.begin()->val>1)newNode = List.insert(List.begin(), Node(1));newNode->container.insert(key);kv[key] = newNode;}}/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */void dec(string key) {if(kv.count(key)){auto oldNode = kv[key];if(oldNode->val==1) {kv.erase(key);} else {auto newNode = next(oldNode, -1);if(oldNode==List.begin() || newNode->val<oldNode->val-1){newNode = List.insert(oldNode, Node(oldNode->val-1));}newNode->container.insert(key);kv[key] = newNode;}oldNode->container.erase(key);if(oldNode->container.empty()){List.erase(oldNode);}}}/** Returns one of the keys with maximal value. */string getMaxKey() {if(List.empty()) return "";return *List.rbegin()->container.begin();}/** Returns one of the keys with Minimal value. */string getMinKey() {if(List.empty()) return "";return *List.begin()->container.begin();}
};
  1. 最小基因变化
    现在给定3个参数 — start, end, bank,分别代表起始基因序列,目标基因序列及基因库,请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化,请返回 -1。

依次从基因库找变换一个字母可以构成的,然后删除基因库中的对应基因,继续查找直至找到或者找不到

class Solution {
public:int Dif_num(string& s1, string& s2){int cnt = 0;for (int i = 0; i < s1.size(); i++){if (s1[i] != s2[i])cnt++;}return cnt;}int minMutation(string start, string end, vector<string>& bank) {queue<string>qu;qu.push(start);int res = 0;unordered_map<string, int>vis;while (!qu.empty()){int size = qu.size();for (int i = 0; i < size; i++){string cur = qu.front();vis[cur] = 1;qu.pop();if (cur == end)return res;for (int i = 0; i < bank.size(); i++){if (Dif_num(cur, bank[i]) == 1 && !vis[bank[i]]){qu.push(bank[i]);}}}res++;}return -1;}
};
  1. 字符串中的单词数
    统计字符串中的单词个数,这里的单词指的是连续的不是空格的字符。

考察一个边界条件,十分简单了

class Solution {
public:int countSegments(string s) {int ret = 0;if (s.size() == 0) return ret;else if (s[0] != ' ') ret++;for (int i  = 0; i < s.size() - 1; i++){if (s[i] == ' ' && s[i + 1] != ' ') {ret++;i++;}}return ret;}
};
  1. 无重叠区间
    给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

贪心算法的经典运用。先排序,然后挨个判断:如果包含关系则取小的,如果交错则抛弃后者,如果不相交则都存着

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.empty()) return 0;sort(intervals.begin(), intervals.end());int left = intervals[0][1];int res = 0;for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] < left) {++res;left = min(left, intervals[i][1]);} else {left = intervals[i][1];}}return res;}
};
  1. 寻找右区间
    给定一组区间,对于每一个区间 i,检查是否存在一个区间 j,它的起始点大于或等于区间 i 的终点,这可以称为 j 在 i 的“右侧”。

分别存两份数组以区间起点和终点排序,然后进行比较得出右侧区间

// 利用两个数组,分别排序起点和终点位置
class Solution {
public:vector<int> findRightInterval(vector<vector<int>>& intervals) {vector<pair<int, int>> start;vector<pair<int, int>> end;int len = intervals.size();for(int i = 0; i < len; i++){start.push_back(make_pair(intervals[i][0], i));end.push_back(make_pair(intervals[i][1],i));}sort(start.begin(), start.end());sort(end.begin(), end.end(),[](pair<int, int> p1, pair<int, int> p2){if(p1.first == p2.first)return p1.second < p2.second;return p1.first < p2.first;//如果两个终点相同,会返回那个索引小的});vector<int> ans(len, -1);int indexS = 0;int indexE = 0;while(indexS < len && indexE < len){while(indexS < len && (start[indexS].second == end[indexE].second || start[indexS].first < end[indexE].first))indexS++;if(indexS < len)ans[end[indexE++].second] = start[indexS].second;}return ans;}
};
  1. 路径总和3
    给定一个二叉树,它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。

使用前缀和记录从而减小内存消耗,只需遍历一次树即可。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:unordered_map<int, int> m;int sum, res = 0;
public:void dfs(TreeNode* root, int cur_sum){if (root == nullptr) return;if (m.count(cur_sum - sum))res += m[cur_sum - sum];m[cur_sum] ++;if (root->left)  dfs(root->left, cur_sum + root->left->val);if (root->right) dfs(root->right, cur_sum + root->right->val);m[cur_sum]--;}int pathSum(TreeNode* root, int sum) {if (root == nullptr) return 0;this->sum = sum;// 构建前缀和m[0] = 1;dfs(root, root->val);return res;}
};
  1. 找到字符串中所有字母异位词
    给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

采用双指针滑动,用一个字典数组保存P的特征,滑动的过程中–,如果恰好为0且长度相等则说明找到了,否则滑动指针并++

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> res;int m[128] = {0};int left = 0, right = 0, need = 0;for (char c : p)++m[c];while (right < s.size()){if (m[s[right]] > 0)     ++need;--m[s[right]];++right;while (need == p.size()){if (right - left == p.size())   res.push_back(left);      //通过长度判断异位词,加入res中if (m[s[left]] == 0)     --need;++m[s[left]];++left;}}return res;}
};

这篇关于leetcode解题思路分析(五十)432 - 438 题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1138006

相关文章

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景

MyBatis-Plus中静态工具Db的多种用法及实例分析

《MyBatis-Plus中静态工具Db的多种用法及实例分析》本文将详细讲解MyBatis-Plus中静态工具Db的各种用法,并结合具体案例进行演示和说明,具有很好的参考价值,希望对大家有所帮助,如有... 目录MyBATis-Plus中静态工具Db的多种用法及实例案例背景使用静态工具Db进行数据库操作插入

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手:启用 pprof3. CPU Profiling:分析 C