Comments (4)
这是我面试的时候学习用的,我给的解法肯定不是最优解法。而且我也不知道你标准的最优解法是啥。。
from interview-go.
不是我标准的最优解法。。只是说面试考你算法的时候,面试官可能会问你如何优化。。如果说给不出最优解的话,可能分会给你较低一点。
from interview-go.
比如你在《判断两个给定的字符串排序后是否一致》里面的解法,sl1 := len([]rune(s1))
这里的转换其实会有点多余,len(s1)
就已经能取到字符串长度了。
再来看算法,表面上是一次迭代,时间复杂度为 O(N),但其实没考虑到 strings.Count
的时间复杂度。要统计一个字符串中的字符出现次数,必定至少会发生完整的一次迭代,所以 Count 操作时间复杂度至少也姑且认为是 O(N)。那总体看来,解法的时间复杂度实际为 O(N^2)。
func isRegroup(s1,s2 string) bool {
sl1 := len([]rune(s1))
sl2 := len([]rune(s2))
if sl1 > 5000 || sl2 > 5000 || sl1 != sl2{
return false
}
for _,v := range s1 {
if strings.Count(s1,string(v)) != strings.Count(s2,string(v)) {
return false
}
}
return true
}
那面试官可能会问:“能实现时间复杂度为 O(N) 的算法吗?”
from interview-go.
@TheStarBoys rune
你要考虑字符串出现中文或其他字符的情况。
from interview-go.
Related Issues (20)
- 实现 Sunday 匹配 精简版代码
- 第三题的答案是否使用了额外的空间 HOT 1
- gpm窃取过程不对 HOT 1
- 常见语法题目 一 的第6题,CAS操作 HOT 3
- 语法找错题 最后一道解答错误
- question17/多协程切片查询
- 最长公共前缀 go版本代码有误
- 第六题机器人坐标计算有问题
- 冒泡排序完全是错的 HOT 1
- “实现阻塞读且并发安全的map”答案补充 HOT 1
- q001中的chan类型应该用struct{}
- 实现 Sunday 匹配 needle在最末尾的时候返回结果异常
- 读阻塞且并发安全的 Map,答案是否有问题?
- 最接近的三数之和,代码有误
- Goroutine泄露问题——交替打印数字和字母
- q006 机器人坐标,L 跟 R指令是不是调转了
- 判断字符串中字符是否全都不同为什么有个127的判断?
- 『goroutine和channel使用一』 答案协程泄露
- interview-go/question /q015.md
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from interview-go.