BabbleDay's Blog

注意这里的输入是行的Index，不是行数

通过记录上一行

class Solution:
    # @param {integer} rowIndex
    # @return {integer[]}
    def getRow(self, rowIndex):
        rtn, prev = [1], [1,1]
        for k in range(rowIndex+1):
            rtn = [1] * (k+1)
            if k>1:
                for j in range(1,k):
                    rtn[j] = prev[j-1] + prev[j]
                prev = rtn
        return rtn

在一行内解决

观察

1 3 3 1

S1: 尾部加一  1 3 3 1 1

S2: 从倒数第二个到正数第二个，每个数变成当前数与其左边的数之和

1 3 3 4 1

1 3 6 4 1

1 4 6 4 1

class Solution:
    # @param {integer} numRows
    # @return {integer[][]}
    def generate(self, numRows):
        if numRows == 0:
            return []
        if numRows == 1:
            return [[1]]
        rtn = [[1],[1,1]]
        for i in range(2,numRows):
            temp = [1]
            for j in range(1, i):
                temp.append(rtn[i-1][j-1]+rtn[i-1][j])
            temp.append(1)
            rtn.append(temp)
        return rtn

归并边界 Most Voted Solution

class Solution:
# @return a list of lists of integers
def generate(self, numRows):
    lists = []
    for i in range(numRows):
        lists.append([1]*(i+1))
        if i>1 :
            for j in range(1,i):
                lists[i][j]=lists[i-1][j-1]+lists[i-1][j]
    return lists

心得：想清楚，打草稿，避免不必要的错误

记录是否进位

class Solution:
    # @param {integer[]} digits
    # @return {integer[]}
    
    def plusOne(self, digits):
        i, carry = -1, True
        while(carry):
            if digits[i]==9:
                digits[i] = 0
                if i==-len(digits):
                    digits = [1] + digits
                    carry = False
                i -= 1
            else:
                digits[i] += 1
                carry = False
        return digits

是九变0，最高位加［1］

class Solution:
    # @param {integer[]} digits
    # @return {integer[]}
    def plusOne(self, digits):
        i = -1
        while(not i<-len(digits)):
            if digits[i] != 9:
                digits[i] += 1
                return digits
            else:
                digits[i] = 0
            i -= 1
        digits = [1] + digits
        return digits

使用del删除list里的元素

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def removeDuplicates(self, nums):
        i, j = 0, 1
        if len(nums)<2:
            return len(nums)
        while(i < len(nums)-1):
            j = i+1
            if nums[i] == nums[j]:
                del nums[j]
            else:
                i += 1
        return len(nums)

不改变list

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def removeDuplicates(self, nums):
        l, i = 1, 1
        if len(nums)<2:
            return len(nums)
        for i in range(1,len(nums)):
            if nums[i]!=nums[i-1]:
                nums[l] = nums[i]
                l += 1
        return l

利用Python的list comprehension想写出一行代码

class Solution:
    # @param {integer[]} nums
    # @param {integer} val
    # @return {integer}
    
    def removeElement(self, nums, val):
        # nums = [x for x in nums if x!=val]
        z = [y for y in nums if y != val]
        for k,v in enumerate(z):
            nums[k] = v
        return len(z)

但是题目要求要在原地修改list的内容，所以原来就想着直接给nums赋值，结果大错特错！

问题在于，Python中的Naming是将一个名字和一个Object绑定即binding，而不是以前的assign。带图的解释戳这里

而且Python的binding是有作用域的，即scope。在一个作用域里的绑定是不会在子作用域里被改变的。

在这里就是，大环境下绑定了nums(原），而在函数中重新建立了一个list并用nums（新）去绑定了。当函数执行完毕之后，回到大环境下，nums其实还是nums（原），所以之前的写法会错。

这一段论述可以由下图验证：

那这样的解决办法就是在函数中，给nums（原）绑定的对重写。即for k,v in enumerate(z): nums[k] = v。

利用此题中众数次数超过一半的特性 O(n)

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def majorityElement(self, nums):
        count, temp = 1, nums[0]
        for x in nums[1:]:
            if x==temp:
                count += 1
            else:
                count -= 1
            if count==0:
                temp = x
                count = 1
        return temp

哈希表 O(n)

位操作 O(n)

class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def containsDuplicate(self, nums):
        pos, neg = 0, 0
        for x in nums:
            if x < 0:
                temp = 1 << -x
                if neg & temp != 0:
                    return True
                pos |= temp
            else:
                temp = 1 << x
                if pos & temp != 0:
                    return True
                pos |= temp
        return False

哈希表 O(n)

Python一行