Leetcode#2@2017

考试周的题目堆到了现在 。在补。
week7是我自己出的题。96,95,279.
week8的list:381,380,344.
week9的list:238,384,108.

---

96 二叉搜索树有几种。
自己给自己挖的坑真难出来啊。
想了下找规律：1有1种；2有2种。3呢？
规律很好找。但是。感觉不会用py了。List掌握的不太好
这样写的问题究竟在哪。。。然后我用了append。

        nums=[1,1]+[0]*(n-1)
        for i in range(2,n+1):
            for j in range(i):
                nums[i]=nums[i]+nums[i-1-j]*nums[j]
        return nums[n]

95是升级版。
上一题的情况是左侧n种可能，右侧m种可能，那么就一定会有nm种可能
这题是把mn种可能列出来。如果沿用96的做法，GG。分治法即可。

def dfs(self,start,end):
        if start > end:
            return [None]
        ans = []
        for val in range(start, end + 1):
            leftTree = self.dfs(start, val - 1)
            rightTree = self.dfs(val + 1, end)
            for l in leftTree:
                for r in rightTree:
                    root = TreeNode(val)
                    root.left = l
                    root.right = r
                    ans.append(root)
        return ans

279除了暴力以外没有想到正常思路。
暴力思路如下：
1：列出n-sqrt(n)^2,...n-1的值。得0就返回，否则保留差值。
2：对上一步的差值重复1的运算。
3：根据2的相差值继续。
4：根据3的相差值继续。
最多到n也就结束了。每一轮的数据量都会减小。
n没有给范围，真是难过。
（根据后来下一段话，我们知道这个循环次数最多也就到4了）
复杂度最多到n的1.5次方。
看到的最优解是利用大自然的智慧的。我猜到会有规律。但是这个规则我不知道。
感谢拉格朗日。。。

        while(n%4==0):
            n/=4
        if(n%8==7):
            return 4
        m=int(math.sqrt(n))
        for a in range (m+1):
            b=int(math.sqrt(n-a*a))
            if(a*a+b*b==n):
                if(a):
                    return 2
                else:
                    return 1
        return 3

本来想return a?2:1的。py貌似不支持这样写 。
在C里面可以更简单：1+！！a就可以了。
自己挖的坑真是不好出。。。
dp解法的伪代码:

for(...)
  dp[i]=n;
  for()
    dp[i]=Math.min(dp[i],dp[i-j*j]+1);

还有一种广搜的解法；

---

week8想弃疗了咋整
381 设计数据结构的插删&随机返回操作 时间O（1）
直接看题解去了。defaultdict是个好东西
然后没看懂remove怎么搞。。。 题解
380没有重复值就容易了很多。直接remove丢出去
344。。。我记住python的字符串反转怎么写了。

return s[::-1]

java也一样 stringbuffer

---

week9
238:暴力过。（差点以为我只会暴力）

        n,m,flag=1,[],True
        for i in nums:
            if(i==0 and flag):
                flag=False
                continue
            if(i==0 and flag==False):
                return [0]*len(nums)
            n*=i
        for i in range(len(nums)):
            if(flag):
                m.append(n/nums[i])
            else:
                if(nums[i]==0):
                    m.append(n)
                else:
                    m.append(0)
        return m

384啊怎么又回去第八周那个画风了、不过这个真的是简单
核心就是随机交换位置。
洗牌算法：
Fisher-Yates:从原有数组中随机抽一个到新数组
Knuth-Durstenfeld:从未处理数据中随机取一个存放在数组尾部。
in-place：如上。
取样算法
108升序转平衡二叉。和95一个套路直接过。