这两天生物钟差不多调过来了，已经能正常按时早起，按时午休，身体出现的不适感也没有很多。今天在看书的时候感觉PRML对我来说还是有些太难了，很多公式和推导其实都看不懂，所以感觉不太适合现在的阶段去看，暂时先不想调整，看这周的面试情况吧。做题的话今天感觉比昨天顺畅一点了，但是还是没法得到正确解，慢慢来吧。
一、PRML
今天看了第一章的第六节，信息熵。讲了一些信息量的概念、平均信息量、乘数等等。对于离散变量，最大的熵值产生于均匀分布，对于连续变量，最大的熵值产生于高斯分布。还讲了相对熵和互信息的概念。
第二章就开始讲各种概率分布了，各种公式真的爆炸多，我觉得基本的思路就是先讲概率密度函数，然后是均值、方差、似然估计，从伯努利分布到Beta分布再到高斯分布，都差不多的思路。今天看到高斯分布的最大似然估计部分，明天继续。
二、LeetCode
17# 电话号码的数字组合
这个题目的意思就是要写出所有数字代表的字母的排列组合，可以抽象出来是求几个字符串的单字母排列组合。所以先要有一个字典存放数字对应的字符串。然后先取出第一个数字对应的所有字母，构成一个列表，然后从第二个数字开始，将它对应的所有字母与上一个列表里的所有元素进行拼接，比如第一个数字是2，那开始的类别是['a','b','c'],第二个数字是3，对应的是def，那现在的结果就是把d、e、f分别和abc拼，得到['ad','ae','af','bd','be','bf','cd','ce','cf'],之后都是用当前数字对应的所有字母与之前的结果进行拼接。
19# 删除链表的倒数第N个节点
这个题目的一种解法是，选择两个指针，fast和slow，先让fast指针前进n步，这时候fast和slow再同时出发，fast到达最后的时候slow指向的就是要删除的节点。这里有两点要注意的，一个是如果要删除的是第一个元素，要单独考虑，因为到fast走了n步的时候，最后一次执行fast=fast.next已经把fast指向最后一个值的next了，所以这时候如果fast为None，说明已经走到最后了，要删除的就是第一个元素，那么令head= head.next就可以了。另一点是最终fast和slow停下以后，slow停的位置就是要删除的节点，所以循环之后用slow.next = slow.next.next就是完成了删除操作。
22# 括号生成
括号生成用到了递归的方法，大致的意思是如果左括号还有剩余，那就把字符串加上左括号，然后递归，同时把左括号数量减去1，下一步如果右括号还有剩余，这时候要判断右括号的数量是不是小于左括号，如果是，就把右括号加上，并进行递归。我觉得递归还挺难懂的，就直接上代码吧。
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.res = []
self.generateParenthesisIter('', n, n)
return self.res
def generateParenthesisIter(self, mstr, l, r):
if l == 0 and r == 0:
self.res.append(mstr)
return
# 如果左括号还有剩余，加上左括号然后递归
if l > 0:
self.generateParenthesisIter(mstr+'(', l-1, r)
# 如果右括号还有剩余，且目前右括号的数量小于左括号的，也就是
# 剩余的r比剩余的l大，那么就加右括号然后递归
if r > 0 and r>l:
self.generateParenthesisIter(mstr+')', l, r-1)
29# 两数相除
这个题目首先要确定符号，然后把dividend和divisor都取绝对值，然后就是用dividend减去除数，当然这样的话时间会超时，所以做了一个改进就是先用divisor去减，然后在内层循环去给divisor左移一位，也就相当于2倍，加快减的过程。如果减的多了，再回到外循环，重新减divisor，而且i可以控制是减去了divisor的几倍。最后也上下代码吧。
class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
flag = (dividend < 0) is (divisor < 0)
num = 0
dividend, divisor = abs(dividend), abs(divisor)
while dividend >= divisor:
tmp, i = divisor, 1
while dividend - tmp >= 0:
dividend -= tmp
num += i
i <<= 1
tmp <<= 1
if not flag:
num = -num
return min(2147483647, max(num, -2147483648))
33# 搜索旋转排序数组
这个题目我之前面试遇到过，所以大概知道思路，没想到写的时候还是翻了下车。因为数组是升序的，旋转之后就分成了两段升序的。因为是搜索的题目，所以我们可以考虑到用二分，但是往哪边分就是个问题了。解决的思路是这样的，用中间的元素跟最右边的元素比，如果比最右边的大，那左半边一定是有序的，反推很容易得到这个结论。那这样的话就可以判断target是不是在left和mid之间，如果是，就在左边二分，如果不是就在右边二分。同样的，如果中间的值右边的小，那么右半边一定是有序的，后面就跟上面类似了。
35# 在排序数组中查找元素的第一个和最后一个位置
题目时间复杂度的要求可以看出是要用到二分了，那分的关键就是要先不断二分，直到找到一个等于target的值，然后从这个位置开始，left和right指针合并，然后往前后两个方向走，直到出现不是target的位置，那就可以分别确定第一个和最后一个的位置了。
写在最后：要写这么一段博客真的好不容易啊，要理清楚这些题目更是不容易，现在的阶段还仅仅是能把别人的思路看懂，实现一下，还总是出错，相信自己多多实践，也能自己写出来的，加油！
网友评论