leetcode简单题1-20
- Two Sum(e-1)
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if i!=j and nums[i]+nums[j]==target:
print(i,j)
- Reverse Integer(e-2)
Given a 32-bit signed integer, reverse digits of an integer.
class Solution(object):
def reverse(self, x):
if '-' not in str(x):
x=[int(i) for i in list(str(x))]
x=x[::-1]
else:
x=abs(x)
x=[int(i) for i in list(str(x))]
x=x[::-1]
x=-x
- Palindrome Number(e-3)
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: true
class Solution(object):
def isPalindrome(self, x):
if x>0:
a=[int(i) for i in list(str(x))]
x=[int (i) for i in list(str(x))]
a=a[::-1]
if a==x:
return True
else:
return False
else:
x=abs(x)
a=[int(i) for i in list(str(x))]
x=[int (i) for i in list(str(x))]
a=a[::-1]
if a==x:
return True
else:
return False
- Roman to Integer(e-4)
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
d = {"I":1, "V": 5, "X":10,"L":50,"C":100, "D":500, "M":1000}
ans = 0
for i in xrange(0, len(s) - 1):
c = s[i]
cafter = s[i + 1]
if d[c] < d[cafter]:
ans -= d[c]
else:
ans += d[c]
ans += d[s[-1]]
return ans
- Longest Common Prefix(e-5)
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
class Solution:
def longestCommonPrefix(self, strs):
if not strs:
return ""
if len(strs) == 1:
return str[0]
minl=min([len(x) for x in strs])
end=0
while end < minl:
for i in range(1,len(strs)):
if strs[i][end]!= strs[i-1][end]:
return strs[0][:end]
end += 1
return strs[0][:end]
- Valid Parentheses(e-6)
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
class Solution(object):
def isValid(self, s):
stack = []
d = ["()", "[]", "{}"]
for i in range(0, len(s)):
stack.append(s[i])
if len(stack) >= 2 and stack[-2]+stack[-1] in d:
stack.pop()
stack.pop()
return len(stack) == 0
- Merge Two Sorted Lists(e-7)
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
class Solution(object):
def mergeTwoLists(self, l1, l2):
head = dummy = ListNode(-1)
while l1 and l2:
if l1.val<l2.val:
head.next=l1
l1=l1.next
else:
head.next=l2
l2=l2.next
head=head.next
if l1:
head.next=l1
if l2:
head.next=l2
return dummy.next
- Remove Duplicates from Sorted Array(e-8)
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return len(nums)
slow = 0
for i in xrange(1, len(nums)):
if nums[i] != nums[s]:
slow += 1
nums[s] = nums[i]
return slow + 1
- Remove Element(e-9)
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
class Solution(object):
def removeElement(self, nums, val):
slow = -1
for i in range(0, len(nums)):
if nums[i] != val:
slow += 1
nums[slow] = nums[i]
return slow + 1
- Implement strStr(e-10)
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
class Solution:
def strStr(self, haystack, needle):
return haystack.find(needle)
- Search Insert Position(e-11)
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
lo = 0
hi = len(nums)
while lo < hi:
mid = lo + (hi - lo) / 2
if nums[mid] > target:
hi = mid
elif nums[mid] < target:
lo = mid + 1
else:
return mid
return lo
- Count and Say(e-12)-------没看懂，以后补
The count-and-say sequence is the sequence of integers with the first five terms as following: - Maximum Subarray(e-13)
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
class Solution:
def maxSubArray(self, nums):
if len(nums) == 0:
return 0
presums=maxsums=nums[0]
for i in range(1,len(nums)):
presums=max(presums+nums[i], nums[i])
maxsums=max(presums, maxsums)
return maxsums
- Length of Last Word(e-14)
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
class Solution:
def lengthOfLastWord(self, s):
"""
:type s: str
:rtype: int
"""
while len(s):
s=s.split()
if len(s) > 0:
return len(s[-1])
return 0
- Plus One(e-15)
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
class Solution:
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
digits[-1]=digits[-1]+1
print(digits)
- Add Binary(e-16)
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
return bin(int(a, 2) + int(b, 2))[2:]
- Sqrt(x)(e-17)
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
lo = 0
hi = x
while lo <= hi:
mid = (hi + lo) / 2
v = mid * mid
if v < x:
lo = mid + 1
elif v > x:
hi = mid - 1
else:
return mid
return hi
- Climbing Stairs(e-18)
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
class Solution(object):
def climbStairs(self, n):
if n<=1:
return 1
pre=1
ppre=1
for i in range(2,n+1):
tmp=pre
pre=ppre+pre
ppre=tmp
return pre
- Remove Duplicates from Sorted List(e-19)
Given a sorted linked list, delete all duplicates such that each element appear only once.
class ListNode:
def __init__(self,x):
self.val=x
self.next=None
class Solution(object):
def deleteDuplicates(self,head):
dummy=ListNode(None)
dummy.next=head
p=dummy
while p and p.next:
if p.val == p.next.val:
p.next=p.next.next
else:
p=p.next
return dummy.next
- Merge Sorted Array(e-20)
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
end = m + n - 1
m -= 1
n -= 1
while end >= 0 and m >= 0 and n >= 0:
if nums1[m] > nums2[n]:
nums1[end] = nums1[m]
m -= 1
else:
nums1[end] = nums2[n]
n -= 1
end -= 1
while n >= 0:
nums1[end] = nums2[n]
end -= 1
n -= 1
