BabbleDay's Blog

心得：思考要完整。。。

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)

位操作 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一行

ComposingPrograms 1.7 Exercises

def countdown(n):
    print(n)
    if n>1:
        countdown(n-1)

def countup(n):
    if n>0:
        countup(n-1)
        print(n)

def recursive(m,n):
    if n>0:
        return m + recursive(m, n-1)
    else:
        return 0

def expt(base, power):
    if power==0:
        return 1
    else:
        return base * expt(base, power-1)

def sum_digits(n):
    if n<10:
        return n
    else:
        return n%10 + sum_digits(n//10)

def is_prime(n, d):
    if n<=1:
        return False
    elif d==1:
        return True
    elif n%d==0:
        return False
    else:
        return is_prime(n, d-1)

def sum_primes_up_to(n):
    if n==2:
        return 2
    elif is_prime(n, n-1):
        return sum_primes_up_to(n-1) + n
    else:
        return sum_primes_up_to(n-1)