Leetcode刷题笔记#3

【刷题笔记】Leetcode #3
【思路一：brute force】
Step1：首先考虑先固定住A[1]作为左端的情况。先固定住A[1]，逐个扫描后面的字母和前面的每一个字母进行对比。越到后面的字母所需要的时间越久，因为后面的字母需要和前面每一个进行对比，这一步所需要的时间为O(n^2)
Step2：找到了第一个字母对应的最大长度后，对每一个字母如此操作，需要n次。
T(n)：时间复杂度为O(n^3)

【思路二：Sliding window+Hashmap】
Step1：首先考虑先固定住A[1]作为左端的情况。先固定住A[1]，将第一个字母<value, index>存入hashmap。
Step2：逐个扫描后面的字母，通过hashmap检查该字母是否是否存在于hashmap中，若存在说明有重复（假设A[m]=A[k], m<k，方便后面的讨论），则不需要继续查看了。记录长度和index m，用于以后的对比。这个长度就是开始于A[1]的序列的最长的长度。
Step3：接下来是最奇妙的地方是，我们可能不需要固定住A[2]再重复上面的步骤，我们可以从Step2中发现的重复的那个值第一次出现时的index+1作为左端，也就是那个值右边的第一个数字A[m+1]。
Step4：有了左端A[m+1]，我们开始扫描后面的数字。需要从A[m+2]开始吗？不需要。因为我们在Step2中已经扫描过了，事实上，从A[m]到A[k]之间的字母我们都扫描过了，而且知道他们是互异的，是安全的。A[k]也是安全的，因为和它相等的A[m]也已经排除掉了，因此只需要从A[k+1]开始扫描即可。
Step5：结合step2-4，我们发现，第一次扫描的字母从A[1]到A[m]，第二次扫描的字母从A[m+1]开始，都没有重复过。根据归纳演绎，我们知道扫描的复杂度为O(n)。
T(n)：由于hashmap查找的复杂度为O(1)，扫描为O(n)，所以时间复杂度为O(1)*O(n)=O(n)

======
大家好！我是一名转专业小白，目前正在刷题中。我的背景是教育心理学，今年fall马上就要就读CS专业了（为了隐私暂且隐去学校和location）。
我发表这个帖子有两个目的，一是帮助我自己整理思路，还有一个目的是和大家交流分享~我希望可以帮助到和我一样正在努力转专业的同学们，也希望可以和大家和平交流。
谢谢：）


补充内容 (2020-7-22 08:59):
我个人认为，先想到brute force解题方法是学习过程中很关键的一环。虽然brute force看上去笨笨的，但是它可以帮我们去判断复杂度的上限，也能够更加appreciate优化后的算法的精妙之处。

哇，教育心理学，感觉背景和cs差很多啊。加油加油。

不知道小帅 发表于 2020-8-17 11:24
哇，教育心理学，感觉背景和cs差很多啊。加油加油。

谢谢~其实我觉得还蛮有意思的~坚持坚持！