給定一個整數(shù)數(shù)組?nums?和一個目標值?target感猛，請你在該數(shù)組中找出和為目標值的那?兩個?整數(shù)七扰，并返回他們的數(shù)組下標。
你可以假設(shè)每種輸入只會對應一個答案陪白。但是颈走，你不能重復利用這個數(shù)組中同樣的元素。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解：
class Solution:
????def twoSum(self, nums: List[int], target: int) -> List[int]:
????????res = {}
for index, num in enumerate(nums):
#enumerate() 函數(shù)用于將一個可遍歷的數(shù)據(jù)對象(如列表咱士、元組或字符串)組合為一個索引序列立由，同時列出數(shù)據(jù)和數(shù)據(jù)下標轧钓，一般用在 for 循環(huán)當中。
????????????another_num = target - num
????????????if another_num in res:
????????????????return [res[another_num], index]
????????????res[num] = index
????????return None
給出一個 32 位的有符號整數(shù)锐膜，你需要將這個整數(shù)中每位上的數(shù)字進行反轉(zhuǎn)毕箍。
示例?1:
輸入:123
輸出:321
?示例 2:
輸入:-123
輸出:-321
示例 3:
輸入:120
輸出:21
注意:
假設(shè)我們的環(huán)境只能存儲得下 32 位的有符號整數(shù)，則其數(shù)值范圍為?[?231,? 231?? 1]道盏。請根據(jù)這個假設(shè)而柑，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0。
解：
class Solution:
????def reverse(self, x: int) -> int:
????????if x==0:
????????????return 0
str_x = str(x)? #轉(zhuǎn)換成字符串str
????????x = ''
if str_x[0] == '-':? #如果是負數(shù)
????????????x += '-'
????????x += str_x[len(str_x)-1::-1].lstrip("0").rstrip("-")?
#str[len(str) -1::-1]：字符串[開始點荷逞，結(jié)束點媒咳，步長]，步長為負种远，從右到左
#lstrip() 方法用于截掉字符串左邊的空格或指定字符涩澡；rstrip()方法用于截掉字符串右邊的空格或指定字符。
x = int(x) #變回整數(shù)int
if -2**31
????????????return x
????????return 0
判斷一個整數(shù)是否是回文數(shù)坠敷∶钔回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。
示例 1:
輸入:121
輸出:true
示例?2:
輸入:-121
輸出:false
解釋:從左向右讀, 為 -121 膝迎。 從右向左讀, 為 121- 粥帚。因此它不是一個回文數(shù)。
示例 3:
輸入:10
輸出:false
解釋:從右向左讀, 為 01 弄抬。因此它不是一個回文數(shù)茎辐。
解：
class Solution:
????def isPalindrome(self, x: int) -> bool:
????????if x<0:
????????????return False
????????else:
res = str(x)[::-1] #逆序
????????????if res == str(x):
????????????????return True
????????????else:
????????????????return False
羅馬數(shù)字包含以下七種字符:?I，?V掂恕，?X拖陆，?L，C懊亡，D?和?M依啰。
字符數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫做?II?店枣，即為兩個并列的 1速警。12 寫做?XII?，即為?X?+?II?鸯两。 27 寫做??XXVII, 即為?XX?+?V?+?II?闷旧。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊钧唐。但也存在特例忙灼，例如 4 不寫做?IIII，而是?IV。數(shù)字 1 在數(shù)字 5 的左邊该园，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 酸舍。同樣地，數(shù)字 9 表示為?IX里初。這個特殊的規(guī)則只適用于以下六種情況：
I?可以放在?V?(5) 和?X?(10) 的左邊啃勉，來表示 4 和 9。
X?可以放在?L?(50) 和?C?(100) 的左邊双妨，來表示 40 和?90淮阐。?
C?可以放在?D?(500) 和?M?(1000) 的左邊，來表示?400 和?900斥难。
給定一個羅馬數(shù)字枝嘶，將其轉(zhuǎn)換成整數(shù)。輸入確保在 1?到 3999 的范圍內(nèi)哑诊。
示例?1:
輸入:"III"
輸出:3
示例?2:
輸入:"IV"
輸出:4
示例?3:
輸入:"IX"
輸出:9
示例?4:
輸入:"LVIII"
輸出:58
解釋:L = 50, V= 5, III = 3.
示例?5:
輸入:"MCMXCIV"
輸出:1994
解釋:M = 1000, CM = 900, XC = 90, IV = 4.
解：
class Solution:
????def romanToInt(self, s: str) -> int:
????????a = {'I':1,'V':5,'X':10,'L':50, 'C':100, 'D':500, 'M':1000}
????????ans = 0
????????for i in range(len(s)):
????????????if i<len(s)-1 and a[s[i]]<a[s[i+1]]:
????????????????ans -= a[s[i]]
????????????else:
????????????????ans += a[s[i]]
????????return ans
編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴。
如果不存在公共前綴及刻，返回空字符串?""镀裤。
示例?1:
輸入:["flower","flow","flight"]
輸出:"fl"
示例?2:
輸入:["dog","racecar","car"]
輸出:""
解釋:輸入不存在公共前綴。
解：
class Solution:
????def longestCommonPrefix(self, strs: List[str]) -> str:
????????if not strs:
????????????return ""
ss = list(map(set, zip(*strs)))#ss = [{'f'}, {'l'}, {'i', 'o'}, {'w', 'g'}]
????????res = ""
????????for i, x in enumerate(ss):
????????????x = list(x)
????????????if len(x) > 1:
????????????????break
????????????res = res + x[0]
????????return res
給定一個只包括?'('缴饭，')'暑劝，'{'，'}'颗搂，'['担猛，']'?的字符串，判斷字符串是否有效丢氢。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合傅联。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串疚察。
示例 1:
輸入:"()"
輸出:true
示例?2:
輸入:"()[]{}"
輸出:true
示例?3:
輸入:"(]"
輸出:false
示例?4:
輸入:"([)]"
輸出:false
示例?5:
輸入:"{[]}"
輸出:true
解：
class Solution:
????def isValid(self, s: str) -> bool:
????????stack = []
????????mapping = {")": "(", "}": "{", "]": "["}
????????for char in s:
????????????if char in mapping:
????????????????top_element = stack.pop() if stack else '#'
????????????????if mapping[char] != top_element:
????????????????????return False
????????????else:
????????????????stack.append(char)
????????return not stack
將兩個有序鏈表合并為一個新的有序鏈表并返回蒸走。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。?
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
解：
class Solution:
????def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 == None:? #注意判斷鏈表為空的情況
????????????return l2
????????elif l2 == None:
????????????return l1
lN = None? ? ?#設(shè)置新鏈表
if l1.val
????????????lN = l1
????????????lN.next = self.mergeTwoLists(l1.next,l2)
????????else:
????????????lN = l2
????????????lN.next = self.mergeTwoLists(l1,l2.next)
????????return lN
給定一個排序數(shù)組貌嫡，你需要在原地刪除重復出現(xiàn)的元素比驻，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度岛抄。
不要使用額外的數(shù)組空間别惦，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
示例?1:
給定數(shù)組nums=[1,1,2],
函數(shù)應該返回新的長度2, 并且原數(shù)組nums的前兩個元素被修改為1,2夫椭。
你不需要考慮數(shù)組中超出新長度后面的元素掸掸。
示例?2:
給定nums=[0,0,1,1,1,2,2,3,3,4],
函數(shù)應該返回新的長度5, 并且原數(shù)組nums的前五個元素被修改為0,1,2,3,4。
你不需要考慮數(shù)組中超出新長度后面的元素益楼。
說明:
為什么返回數(shù)值是整數(shù)猾漫，但輸出的答案是數(shù)組呢?
請注意点晴，輸入數(shù)組是以“引用”方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的悯周。
你可以想象內(nèi)部操作如下:
//nums是以“引用”方式傳遞的粒督。也就是說，不對實參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的禽翼。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中該長度范圍內(nèi)的所有元素屠橄。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解：
class Solution:
????def removeDuplicates(self, nums: List[int]) -> int:
if nums == []:? ?#判斷列表為空的情況
????????????return None
????????else:
????????????a = nums[0]
????????????for i in nums[1:]:?
if i == a:? ? ? ? ?#后一個數(shù)值與前一個比較
nums.remove(i) #相同的數(shù)刪除
????????????????else:
????????????????????a = i
????????return len(nums)
給定一個數(shù)組?nums?和一個值?val，你需要原地移除所有數(shù)值等于?val?的元素闰挡，返回移除后數(shù)組的新長度锐墙。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成长酗。
元素的順序可以改變溪北。你不需要考慮數(shù)組中超出新長度后面的元素。
示例 1:
給定nums=[3,2,2,3],val=3,
函數(shù)應該返回新的長度2, 并且nums中的前兩個元素均為2夺脾。
你不需要考慮數(shù)組中超出新長度后面的元素之拨。
示例?2:
給定nums=[0,1,2,2,3,0,4,2],val=2,
函數(shù)應該返回新的長度5, 并且nums中的前五個元素為0,1,3,0,4。
注意這五個元素可為任意順序咧叭。
你不需要考慮數(shù)組中超出新長度后面的元素蚀乔。
解：
class Solution:
????def removeElement(self, nums: List[int], val: int) -> int:
if nums == []:? ?#判斷列表為空的情況
????????????return None
????????else:
????????????for i in range(len(nums)):
????????????????if val in nums:
????????????????????nums.remove(val)
????????return len(nums)
實現(xiàn)?strStr()?函數(shù)。
給定一個?haystack 字符串和一個 needle 字符串菲茬，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)吉挣。如果不存在，則返回??-1婉弹。
示例 1:
輸入:haystack = "hello", needle = "ll"
輸出:2
示例 2:
輸入:haystack = "aaaaa", needle = "bba"
輸出:-1
說明:
當?needle?是空字符串時睬魂，我們應當返回什么值呢？這是一個在面試中很好的問題马胧。
對于本題而言汉买，當?needle?是空字符串時我們應當返回 0 。這與C語言的?strstr()?以及 Java的?indexOf()?定義相符佩脊。
解：
class Solution:
????def strStr(self, haystack: str, needle: str) -> int:
????????if not needle:
????????????return 0
????????else:
????????????l1 = len(needle)
????????????l2 = len(haystack)
????????????i = 0
????????????for x in haystack:
????????????????if x == needle[0] and i+l1 <= l2 and haystack[i:i+l1] == needle:
????????????????????return i
????????????????i +=1????????????????
????????????return -1
給定一個排序數(shù)組和一個目標值蛙粘，在數(shù)組中找到目標值，并返回其索引威彰。如果目標值不存在于數(shù)組中出牧，返回它將會被按順序插入的位置。
你可以假設(shè)數(shù)組中無重復元素歇盼。
示例 1:
輸入:[1,3,5,6], 5
輸出:2
示例?2:
輸入:[1,3,5,6], 2
輸出:1
示例 3:
輸入:[1,3,5,6], 7
輸出:4
示例 4:
輸入:[1,3,5,6], 0
輸出:0
解：
class Solution:
????def searchInsert(self, nums: List[int], target: int) -> int:
????????if target > nums[-1]:
????????????return len(nums)
????????if target < nums[0]:
????????????return 0
????????if nums[0] <= target <= nums[-1]:
????????????for i in range(len(nums)):
????????????????if nums[i] == target:
????????????????????return i
????????????????elif nums[i] < target < nums[i+1]:
????????????????????return i+1??
給定一個整數(shù)數(shù)組?nums?舔痕，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。
示例:
輸入:[-2,1,-3,4,-1,2,1,-5,4],
輸出:6
解釋:連續(xù)子數(shù)組 [4,-1,2,1] 的和最大伯复，為 6慨代。
解：
class Solution:
????def maxSubArray(self, nums: List[int]) -> int:
????????for i in range(1, len(nums)):
????????????nums[i]= nums[i] + max(nums[i-1], 0)
????????return max(nums)
給定一個僅包含大小寫字母和空格?' '?的字符串，返回其最后一個單詞的長度啸如。
如果不存在最后一個單詞侍匙，請返回 0?。
說明：一個單詞是指由字母組成叮雳，但不包含任何空格的字符串想暗。
示例:
輸入:"Hello World"
輸出:5
解：
class Solution:
????def lengthOfLastWord(self, s: str) -> int:
#s =?"Hello World"
????????l = s.split()
#l =?['Hello', 'World']
????????if len(l)==0:
????????????return 0
????????return len(l[-1])
給定一個由整數(shù)組成的非空數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎(chǔ)上加一帘不。
最高位數(shù)字存放在數(shù)組的首位说莫， 數(shù)組中每個元素只存儲一個數(shù)字。
你可以假設(shè)除了整數(shù) 0 之外寞焙，這個整數(shù)不會以零開頭储狭。
示例?1:
輸入:[1,2,3]
輸出:[1,2,4]
解釋:輸入數(shù)組表示數(shù)字 123。
示例?2:
輸入:[4,3,2,1]
輸出:[4,3,2,2]
解釋:輸入數(shù)組表示數(shù)字 4321棺弊。
解：
class Solution:
????def plusOne(self, digits: List[int]) -> List[int]:
????????num = ''.join(map(str, digits))
?print(num)? ? # 123?
????????result = map(int, str(int(num) + 1))
return list(result)? #[1,2,4]
給定兩個二進制字符串晶密，返回他們的和（用二進制表示）。
輸入為非空字符串且只包含數(shù)字?1?和?0模她。
示例?1:
輸入:a = "11", b = "1"
輸出:"100"
示例?2:
輸入:a = "1010", b = "1011"
輸出:"10101"
解：
class Solution:
????def addBinary(self, a: str, b: str) -> str:
x = int(a,2) #二進制轉(zhuǎn)換成十進制
????????y = int(b,2)
z = bin(x+y)[2:]?#十進制轉(zhuǎn)換成二進制
????????return z
實現(xiàn)?int sqrt(int x)?函數(shù)。
計算并返回?x?的平方根懂牧，其中?x?是非負整數(shù)侈净。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分僧凤，小數(shù)部分將被舍去畜侦。
示例 1:
輸入:4
輸出:2
示例 2:
輸入:8
輸出:2
說明:8 的平方根是 2.82842...,
由于返回類型是整數(shù)，小數(shù)部分將被舍去躯保。
解：
class Solution:
????def mySqrt(self, x: int) -> int:
????????if x <= 1:
????????????return x
????????else:
????????????for i in range(x+1):
????????????????if i*i > x:
????????????????????return i-1
假設(shè)你正在爬樓梯旋膳。需要?n?階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階途事。你有多少種不同的方法可以爬到樓頂呢验懊？
注意：給定?n?是一個正整數(shù)。
示例 1：
輸入：2
輸出：2
解釋：有兩種方法可以爬到樓頂尸变。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入：3
輸出：3
解釋：有三種方法可以爬到樓頂义图。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
解：
class Solution:
????def climbStairs(self, n: int) -> int:
????????a =1
????????b =1
????????for i in range(n):
????????????a,b = b,a+b
????????return a
給定一個排序鏈表，刪除所有重復的元素召烂，使得每個元素只出現(xiàn)一次碱工。
示例?1:
輸入:1->1->2
輸出:1->2
示例?2:?
輸入:1->1->2->3->3
輸出:1->2->3
解：
class Solution:
????def deleteDuplicates(self, head: ListNode) -> ListNode:
????????ans = head
????????while head != None:
????????????if head.next != None and head.val == head.next.val:
????????????????head.next = head.next.next
????????????else:
????????????????head = head.next
????????return ans
給定兩個有序整數(shù)數(shù)組?nums1?和?nums2，將?nums2?合并到?nums1?中，使得?num1?成為一個有序數(shù)組怕篷。
說明:
初始化?nums1?和?nums2?的元素數(shù)量分別為?m?和?n历筝。
你可以假設(shè)?nums1?有足夠的空間（空間大小大于或等于?m + n）來保存?nums2?中的元素。
示例:
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出:[1,2,2,3,5,6]
解：
class Solution:
????def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
????????"""
????????Do not return anything, modify nums1 in-place instead.
????????"""
????????res1 = nums1[0:m]
????????res2 = nums2[0:n]
????????nums1[0:m+n]= sorted(res1+res2)
解：（二）
res1 = nums1[0:m]
res2 = nums2[0:n]
res1.extend(res2)
nums1[0:m+n]=sorted(res1)
給定兩個二叉樹廊谓，編寫一個函數(shù)來檢驗它們是否相同梳猪。
如果兩個樹在結(jié)構(gòu)上相同，并且節(jié)點具有相同的值蹂析，則認為它們是相同的舔示。
示例?1:
輸入: 1? ? 1
? ? ? ? / \? ? / \
? ? ? 2? 3? 2? 3
[1,2,3], [1,2,3]
輸出:true
示例 2:
輸入:? 1? ?1
? ? ? ? ? /? ? ? \
? ? ? ?2? ? ? ? ? 2
[1,2], [1,null,2]
輸出:false
示例?3:
輸入:? 1? ? ? 1
? ? ? ? ?/? \? ? /? \
? ? ? ?2? ?1? 1? ? 2
[1,2,1], [1,1,2]
輸出:false
解：
class Solution:
????def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
????????if p == None and q == None:
????????????return True
????????elif p and q:
????????????if p.val == q.val:
????????????????return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
????????????else:
????????????????return False
????????else:
????????????return False
