学习目标：
- 刷完面试经典150题
- 链接: 面试经典150题
学习内容：
-
- 全排列（中等）→回溯
-
- 组合总和（中等）→回溯
-
- 同构字符串（简单）→哈希表
-
- 合并两个有序链表（简单）→链表
学习时间：
4.2-4.6
抱歉啦，这两天亲人住院了，所以晚了几天
会慢慢回复更新的！
知识点
205. 同构字符串（简单）→哈希表
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = “egg”, t = “add”
输出：true
示例 2：
输入：s = “foo”, t = “bar”
输出：false
示例 3：
输入：s = “paper”, t = “title”
输出：true
先虐个菜
秒了，但是名次低了点奥。。。。
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dict1={}
n= len(s)
for i in range(n):
if t[i] not in dict1.values():
dict1[s[i]]=t[i]
str=''
for i in range(n):
if s[i] in dict1.keys():
str+=dict1[s[i]]
if str==t:
return True
else:
return False
if __name__=="__main__":
a=Solution()
s = "32674"
t = "65535"
print(a.isIsomorphic(s,t))
21. 合并两个有序链表（简单）→链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：输入：l1 = [], l2 = [] 输出：[]
示例 3：输入：l1 = [], l2 = [0] 输出：[0]
秒了！！！
但是出现了小插曲，出现了返回值错误
查了查，原来是因为这部分代码没有注释掉，注释掉就好了~~
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
代码：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
if not list1 and not list2:
return list1
if not list1:
return list2
if not list2:
return list1
head=ListNode()
node=head
while list1 and list2:
if list1.val<list2.val:
node.next=ListNode(list1.val)
node=node.next
list1=list1.next
else:
node.next = ListNode(list2.val)
node = node.next
list2 = list2.next
if list1:
node.next=list1
if list2:
node.next=list2
return head.next
46. 全排列（中等）→回溯
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
回溯确实有点难，上次看了那个视频感觉还是模棱两可，然后后来我又补习了一下，然后我做了个小总结
初始节点为空
路径添加节点1
递归到下一层
路径添加节点2和3
回溯到节点2
回溯到节点1
阿西，果然描述起来好恶心，大家看这里的时候，结合我做的图,再多用pycharm进行调试，弄懂了后还是不难的。加油！！！！！
完整代码：
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans=[]
n=len(nums)
path = []
choices=nums
def dfs(i):
if i ==n:
ans.append(list(path))
return
for item in choices:
if item in path: #如果这个数字已经在已排列的组合中
continue # ，那么跳过这个循环，即剪枝
path.append(item)
dfs(i+1)
path.pop()
dfs(0)
return ans
if __name__ == "__main__":
a=Solution()
nums=[1,2,3]
print(a.permute(nums))
39.组合总和（中等）→回溯
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
哎，正确输出是不难的，可是这个超时，我真是吐了！！！
怎么说呢，上一题是基础，这道题就是剪枝是重点了
加了个剪枝条件
先把数组降序排列，然后如果数组元素相加大于target就剪枝的条件，就通过啦！
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
ans=[]
path=[] #存每个路径上的数字组合
candidates.sort(reverse=True)
def dfs(i):
for item in candidates:
path.append(item)
if sum(path)==target:
path1=sorted(path)
if path1 not in ans:
ans.append(path1)
path.pop()
continue
elif sum(path)>target:
path.pop()
continue
dfs(i+1)
path.pop()
dfs(0)
return ans
if __name__ == "__main__":
a=Solution()
candidates = [2,3,5]
target = 8
print(a.combinationSum(candidates,target))
学习内容：
最后成果
- 46. 全排列（中等）→回溯
- 39. 组合总和（中等）→回溯
- 205. 同构字符串（简单）→哈希表
- 21. 合并两个有序链表（简单）→链表
结论
加油加油，我会抽时间，等过段时间时间松了，我一定会更快更新的！！！
同志们一起努力!!!