Leetcode#3@2017

马上就赶上进度君了，我很感动。
week10的题目：41 448 283
week11的题目：217 219 220
我尽量回家之前把落下的补完好伐~

---

41

边边角角的情况老是考虑不到。。。心急没好事。哎
还是蠢了。把存在的所有都安置到它该放的位置去。位置不对的就是错误开始的地方。

        n=len(nums)
        nums.sort()
        for i in range(n):
            if(nums[i]>0 and nums[i]<=n):
                nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]
        print(nums)
        for i in range(n):
            if(nums[i]!=i+1):
                return i+1
        return n+1

448

要求是O（n）sort一下就已经nlogn了
和442一个思路:增加正负属性。

        for i in range(n):
            inx=abs(nums[i])-1
            nums[inx]=-abs(nums[inx]) #出现过就标负
        return [i+1 for i in range(len(nums)) if nums[i]>0]

py直接用list减了(真是6并且我脑子可能真的有坑)

283

我一开始想简单了。
打算一路统计0的个数cnt一路把之后的数往前移cnt位。
想的太美了。全0就进入死循环了啊。
调整了下思路：非0的数字直接交换到正确位置。

        l,i=0,0
        while(i<n):
            if(nums[i]!=0):
                nums[l],nums[i]=nums[i],nums[l]
                l+=1
            i+=1

---

217

无话可说。检测是否有重复值

        return len(nums)!=len(set(nums))

219

有坑。仔细审题
第一遍看的时候没注意：存在两个不同且距离最多为k的位置值相等
如果瞎到看不见最多俩字，可以过17/23的样例。
看见之后，复杂度最多n*k。好蠢。最后用了枚举和字典。
讲真这个题就算用C++我也会map的。（好像我的dict真当map用的）
至于py的map就是另外一回事了。

        dic = {}
        for i, v in enumerate(nums):  #成为枚举类型
            if v in dic and i - dic[v] <= k:
                return True
            dic[v] = i
        return False

220

此处安利一个网站:VisuAlgo关于算法可视化的
这题用桶。我大致理解。

        for i in range(n):
            m=nums[i]/w#分桶,w内有两种情况：同桶or隔壁
            if m in d:return True
            if m+1 in d and abs(nums[i]-d[m+1])<w:return True
            if m-1 in d and abs(nums[i]-d[m-1])<w:return True
            d[m]=nums[i]
            if i>=k:del d[nums[i-k]/w]#排除已经太过古老不在范围内的桶，不会伤及无辜，如果有无辜存在早就True了
        return False

---

放心回家。假期会恶补数学，夯实一些最重要的东西。