# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
最簡單的方法
def fib(n):
if n==0:
return 1
if n==1:
return 1
else:
return fib(n-1)+fib(n-2)
print(fib(8))
Top down
m=dict()
m[0]=1
m[1]=1
def fib(n):
if n not in m:
m[n]=fib(n-1)+fib(n-2)
return m[n]
print(fib(8))
Botton up
def fib(n):
if n==0:
return 1
if n==1:
return 1
l=[1,1]
for i in range(2,n+1):
l.append(l[i-1]+l[i-2])
return l[-1]
print(fib(8))
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3] Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]解: 逐步檢查: 誰一超過一半 就馬上輸出
這樣也滿快的
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
m=len(nums)
l={}
for i in nums:
if i in l:
l[i]+=1
else:
l[i]=1
if l[i]>m//2:MOore 投票法:
速度上更快一些 O(n) linear time and O(1) space
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count=1
num=nums[0]
for i in nums:
if i==num:
count+=1
if i!=num:
count=count-1
if count==0:
num=i
count=1
return num
return i
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]
Note:
Follow up:
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: J = "aA", S = "aAAbbbb" Output: 3
Example 2:
Input: J = "z", S = "ZZ" Output: 0
Note:
S and J will consist of letters and have length at most 50.J are distinct.
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1:
Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Example 2:
Input: nums = [6,5,4,8] Output: [2,1,0,3]
Example 3:
Input: nums = [7,7,7,7] Output: [0,0,0,0]
