1.删除排序数组中的重复数字

给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。

不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。

样例

给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。

# _*_ coding:utf-8 _*_
class Solution:
    """
    @param: nums: An ineger array
    @return: An integer
    """
    def removeDuplicates(self, nums):
        # write your code here
        len_nums = len(nums)
        if len_nums < 3:
            return len_nums
        lenth = 0
        for index in range(1, len_nums):
            if nums[index] != nums[lenth]:
                lenth += 1
                nums[lenth] = nums[index]
        return lenth + 1

2.两数之和

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。

你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。

样例
给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].

class Solution:
    """
    @param: numbers: An array of Integer
    @param: target: target = numbers[index1] + numbers[index2]
    @return: [index1 + 1, index2 + 1] (index1 < index2)
    """
    def twoSum(self, numbers, target):
        # write your code here
        num = {}
        for k, v in enumerate(numbers):
            num[v] = k
        for i in numbers:
            if target - i in num and numbers.index(i) != num[target-i]:
                return numbers.index(i), num[target-i]

3.删除元素

给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。

元素的顺序可以改变，并且对新的数组不会有影响。
样例
给出一个数组 [0,4,4,0,0,2,4,4]，和值 4

返回 4 并且4个元素的新数组为[0,0,0,2]

class Solution:
    """
    @param: A: A list of integers
    @param: elem: An integer
    @return: The new length after remove
    """
    def removeElement(self, A, elem):
        # write your code here
        i = 0
        j = len(A) - 1
        while i <= j:
            if A[i] == elem:
                if A[j] != elem:
                    A[i], A[j] = A[j], A[i]
                    i += 1
                    j -= 1
                else:
                    j -= 1
            else:
                i += 1
        A = A[:i]

        return len(A)

4.加一

给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。

该数字按照大小进行排列，最大的数在列表的最前面。
样例
给定 [1,2,3] 表示 123, 返回 [1,2,4].

给定 [9,9,9] 表示 999, 返回 [1,0,0,0].

class Solution:
    """
    @param: digits: a number represented as an array of digits
    @return: the result
    """
    def plusOne(self, digits):
        # write your code here
        j = len(digits)-1
        num = digits[j] + 1
        for i in range(len(digits)):
            digits[j] = num % 10
            if not num / 10:
                break
            if j == 0:
                digits.insert(0, num / 10)
                break
            j -= 1
            digits[j] += num / 10
            num = digits[j]
        return digits

5.爬楼梯

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
样例
比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法

返回 3

class Solution:
    """
    @param n: An integer
    @return: An integer
    """

    def climbStairs(self, n):
        # write your code here
        list = [1, 2]
        if n < 3:
            return list[n - 1]
        for i in range(n - 2):
            list.append(list[i + 1] + list[i])

        return list[n - 1]

6.落单的数

给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
样例
给出 [1,2,2,1,3,4,3]，返回 4

class Solution:
    """
    @param: A: An integer array
    @return: An integer
    """

    def singleNumber(self, A):
        # write your code here
        dict = {}
        for i in A:
            if i in dict:
                dict[i] = dict[i] + 1
            else:
                dict[i] = 1

        for k in dict:
            if dict[k] == 1:
                return k