Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

一些建议 #53

Open
TheStarBoys opened this issue Nov 23, 2021 · 4 comments
Open

一些建议 #53

TheStarBoys opened this issue Nov 23, 2021 · 4 comments

Comments

@TheStarBoys
Copy link

  1. 尽量给出使用标准库的解法,与纯算法(不使用任何库)两种。使用库将题做对,面试官可能也不会特别满意,虽然也足以应付一般的场景。
  2. 给出每个解法的时间复杂度,空间复杂度。如果能够分析为什么是这样最好。示例解法由于使用了大量标准库方法,效率太低了,除非你的代码永远没有优化的需求,否则你需要理解如何优化时间复杂度或空间复杂度。
@lifei6671
Copy link
Owner

这是我面试的时候学习用的,我给的解法肯定不是最优解法。而且我也不知道你标准的最优解法是啥。。

@TheStarBoys
Copy link
Author

不是我标准的最优解法。。只是说面试考你算法的时候,面试官可能会问你如何优化。。如果说给不出最优解的话,可能分会给你较低一点。

@TheStarBoys
Copy link
Author

TheStarBoys commented Nov 27, 2021

比如你在《判断两个给定的字符串排序后是否一致》里面的解法,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) 的算法吗?”

@viper-00
Copy link

@TheStarBoys rune 你要考虑字符串出现中文或其他字符的情况。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants