文档章节

leetCode题解之字符最短路径解法2

o
 osc_z1hvg4cu
发布于 2018/04/24 10:28
字数 186
阅读 19
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

1、题目描述

2、分析

  之前使用的大循环再向两边寻找的算法是 O(n^2)复杂度的,可以利用 multimap降低其复杂度。

3、代码

 1 vector<int> shortestToChar(string S, char C) {
 2         // 使用标准库中的multimap 存储每个字符和其下标
 3         // multimap的优势在于key值可以重复
 4         vector<int> ans;
 5         multimap<char,int> m;
 6         for( int i = 0; i< S.size(); i++)
 7             m.insert( make_pair(S[i],i) );
 8         
 9         for( int i =0;i<S.size();i++)
10         {
11             if( S[i] == C )
12             {
13                 ans.push_back(0);
14             }    
15             else
16             {
17                 int k = S.size()-1;
18                 for( auto pos = m.lower_bound( C ); pos != m.upper_bound( C ); pos++ )
19                 {
20                     
21                         if( abs( pos->second - i ) < k )
22                             k = abs( pos->second -i );
23                 }
24                  ans.push_back(k); 
25             } 
26         }
27         return ans; 
28     }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Kubernetes发布SpringBoot项目过程总结

SpringBoot 项目创建完成后,通常会打成 jar 包运行,如果不使用 Kubernetes 可以直接通过 java -jar 或者脚本启动,如果需要发布到 Kubernetes 环境,那么需要编写 Dockerfile、构建镜像、推...

strict_nerd
05/23
0
0
👉 最新推出【Jenkins扩展篇-API实践|监控】教程🎉🎉🎉 助力全方位Jenkins管理!课程详情可添加小助手微信: proc_code。

本文分享自微信公众号 - DevOps云学堂(idevopsvip)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

泽阳DevOps
02/18
0
0
没错,用三方 Github 做授权登录就是这么简单!(OAuth2.0实战)

本文收录在个人博客:www.chengxy-nds.top,技术资源共享。 上一篇《OAuth2.0 的四种授权方式》文末说过,后续要来一波OAuth2.0实战,耽误了几天今儿终于补上了。 最近在做自己的开源项目(f...

程序员内点事
11分钟前
17
0
Docker可视化工具Portainer

前言 对于新手来说,还是要熟悉并掌握Docker命令,因为它的命令还是非常清晰简单的。随着逐渐熟悉命令后,为了提高工作效率我们可以考虑借助一些工具协助。目前业界对于Docker可视化工具比较...

ville
15分钟前
29
0
从 Git 仓库的 Commit 历史中移除敏感文件

在很多情况,我们由于疏忽会将一些敏感信息误传到 Git 仓库上面去。 尽管我们可以使用git rm将包含敏感信息文件删除掉,然后重新提交上传,文件就不会在仓库文件列表显示。 但是这并不能完全...

A_laoshiren
20分钟前
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部