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
