BabbleDay's Blog

心得：特殊情况还是单独处理，可以简化思路，代码正确实现后，再考虑合并特殊情况

def summaryRanges(self, nums):
        rtn = []
        if len(nums) == 0:
            return rtn
        if len(nums) == 1:
            rtn.append(str(nums[0]))
            return rtn

        i = 0
        while(i<len(nums)):
            start = nums[i]
            end = nums[i]
            while(i+1<len(nums) and end+1 == nums[i+1]):
                end = nums[i+1]
                i += 1

            if start==end:
                rtn.append(str(start))
            else:
                rtn.append(str(start)+"->"+str(end))
            i += 1
        
        return rtn

方法一 insert执行效率低

    def rotate(self, nums, k):
        for _ in range(k):
            nums.insert(0,nums[-1])
            del(nums[-1])
        return

方法二 list赋值

def rotate(self, nums, k):
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k] 

心得：思考要完整。。。

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {boolean}
    def containsNearbyDuplicate(self, nums, k):
        dict = {}
        for i in range(len(nums)):
            if(nums[i] in dict):
                if(i-dict[nums[i]]<=k):
                    return True
            dict[nums[i]] = i
        return False

心得：编程语言随机应变＝ ＝

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l = m + n - 1;
        int a = m-1;
        int b = n-1;
        int i=l;
        while(i>=0){
            if(a<0) nums1[i--] = nums2[b--];
            else if(b<0) nums1[i--] = nums1[a--];
            else if(nums1[a]>nums2[b]) nums1[i--] = nums1[a--];
            else nums1[i--] = nums2[b--];
        }
    }
}

注意这里的输入是行的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)