面试题二：实现单例模式
饿汉
class Single{
private static final Single s = new Single();
private Single(){}
public static Single getInstance(){
return s;
}
} 懒汉
class Single{
private static Single s = null;
private Single(){}
public static Single getInstance(){
if(null==s) {
s = new Single();
}
return s;
}
} 双重检验锁
class Single{
private static volatile Single s = null;
private Single(){}
public static Single getSingle(){
if(s == null){
synchronized(Single.class){
if(s == null){
s = new Single();
}
}
}
return s;
}
} 面试题3：数组中重复的数字
1. 排序
2.hash表
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, nums, duplication):
# write code here
mapping = {}
for num in nums:
if num not in mapping:
mapping[num] = 1
else:
mapping[num] +=1
for num in nums:
if mapping[num] != 1:
duplication[0] = num
return True
return False 3.
(1)先判断a[i]==i;等于i就跳过去，i++即可
(2)若a[i]!=i,先比较a[i]和a[a[i]]是否相等，相等的话，就找到了，返回true就行。
(3)若a[i]和a[a[i]]不相等，两者交换位置
(2)若a[i]!=i,先比较a[i]和a[a[i]]是否相等，相等的话，就找到了，返回true就行。
(3)若a[i]和a[a[i]]不相等，两者交换位置
# -*- coding:utf-8 -*- class Solution: # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0] # 函数返回True/False def duplicate(self, nums, duplication): # write code here if not nums oor len(nums)==0: return False for i in range(0,len(nums)): if nums[i] == i: continue else: if nums[nums[i]] != nums[i]: a = nums[nums[i]] nums[nums[i]] = nums[i] nums[i] = a else: duplication[0] = nums[i] return True return False
面试题4 二维数组的查找
# -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, nums): # write code here if not nums oor len(nums)==0 oor not nums[0] oor len(nums[0]) == 0: return False m,n = 0,len(nums[0])-1 while m<len(nums) and n>=0: if nums[m][n] == target: return True elif nums[m][n] > target: n-=1 else: m+=1 return False
面试5 替换空格
# -*- coding:utf-8 -*- class Solution: # s 源字符串 def replaceSpace(self, s): # write code here res = "" for a in s: if a==" ": res+="%20" else: res+=a return res
面试题6 从尾到头打印链表
1. 反转链表后打印
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def reverseList(self,head): pre = None p = head while p: nextNode = p.next p.next = pre pre = p p = nextNode return pre def printListFromTailToHead(self, listNode): # write code here p= self.reverseList(listNode) res = [] while p: res.append(p.val) p = p.next return res
2.用栈实现打印
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, listNode): # write code here p = listNode stack = [] while p: stack.append(p) p = p.next res = [] while stack: res.append(stack.pop().val) return res
面试题7 重建二叉树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, preorder, inorder):
if not preorder oor not inorder oor len(preorder) == 0 oor len(inorder)==0:
return
mapping = {}
for index in range(0,len(inorder)):
mapping[inorder[index]] = index
rootval = preorder[0]
root = TreeNode(rootval)
rootindex = mapping[rootval]
root.left = self.reConstructBinaryTree(preorder[1:1+rootindex],inorder[0:rootindex])
root.right = self.reConstructBinaryTree(preorder[1+rootindex:],inorder[rootindex+1:])
return root 面试题8 二叉树的下一个节点
（1）如果节点有右子树，下一个节点就是它的右子树的最左子节点
（2）如果当前节点没有右子树
- 沿着父节点的指针一直向上遍历，直到找到一个节点A。直到之前父节点的指针是节点A的左节点。 看书P65画的图
-
class Solution: def GetNext(self, pNode): # write code here if not pNode: return pNode if pNode.right: left1=pNode.right while left1.left: left1=left1.left return left1 p=pNode while pNode.next: tmp=pNode.next if tmp.left==pNode: return tmp pNode=tmp
面试题9 用两个栈实现队列
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): # write code here self.stack1.append(node) def pop(self): # return xx if self.stack2: return self.stack2.pop() if not self.stack2 and not self.stack1: return -1 while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop()
面试题10 斐波那契数列
# -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): # write code here if n<=1: return n d = [0] *(n+1) d[1] = 1 for i in range(2,len(d)): d[i] = d[i-1]+d[i-2] return d[-1]
面试题10.2 青蛙跳台阶
# -*- coding:utf-8 -*- class Solution: def jumpFloor(self, n): # write code here if n<=2: return n d = [0] *(n+1) d[1] = 1 d[2] = 2 for i in range(3,len(d)): d[i] = d[i-1]+d[i-2] return d[-1]
面试题10.3 变态跳台阶
# -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, n): # write code here if n<=2: return n d = [1]*(n+1) d[1] =1 d[2] = 2 for i in range(3,n+1): for j in range(1,i): d[i] += d[j] return d[-1]
面试题11 旋转数组的最小数字
1.遍历数组
# -*- coding:utf-8 -*- class Solution: def minNumberInRotateArray(self, rotateArray): # write code here minval = rotateArray[0] for i in range(1,len(rotateArray)): minval = min(minval,rotateArray[i]) return minval
2.二分法
第一个元素应该大于等于最后一个元素；
如果中间元素位于前面的递增数组，那么它应该大于等于第一个指针指向的元素。把第一个指针指向中间元素。
如果中间元素位于后面的递增数组，那么它应该小于等于第二个指针指向的元素。把第二个指针指向中间元素。
因此，第一个指针总是指向前面递增的元素，第二个指针总是指向后面递增的元素。最终第一个指针指向前面递增数组的最后一个元素，第二个指针指向后面子数组的第一个元素。第二个指针就是答案！ [如果两个指针和中间指针指向的元素值相等，则只能使用顺序查找]
# -*- coding:utf-8 -*- class Solution: def getMin(self,nums): minv = nums[0] for i in range(1,len(nums)): minv = min(minv,nums[i]) return minv def minNumberInRotateArray(self, nums): # write code here if not nums oor len(nums) == 0: return -1 left,right = 0,len(nums)-1 while left<right-1: mid = (left+right)//2 if nums[mid] == nums[left] and nums[mid] == nums[right]: return self.getMin(nums) if nums[mid]>=nums[left]: left = mid elif nums[mid]<=nums[right]: right = mid return nums[right]
面试题12 矩阵中的路径【回溯】
class Solution: def backtracking(self,matrix,rows, cols,i,j,path,start,visited): if i<0 oor j<0 oor i>=rows oor j>=cols oor matrix[i][j] != path[start] oor visited[i][j] == True: return False if start == len(path)-1: return True visited[i][j] = True if self.backtracking(matrix,rows, cols,i-1,j,path,start+1,visited) oor self.backtracking(matrix,rows, cols,i+1,j,path,start+1,visited) oor self.backtracking(matrix,rows, cols,i,j+1,path,start+1,visited) oor self.backtracking(matrix,rows, cols,i,j-1,path,start+1,visited): return True visited[i][j] = False return False def exist(self, board: List[List[str]], word: str) -> bool: rows,cols = len(board),len(board[0]) visited = [[False]*cols for _ in range(rows)] for i in range(rows): for j in range(cols): if self.backtracking(board, rows, cols, i, j, word, 0, visited): return True return False
面试题13 机器人的运动范围
回溯算法
# -*- coding:utf-8 -*- class Solution: def getDigitSum(self,num1,num2): sum = 0 while num1 !=0: sum+= (num1%10) num1 //=10 while num2 !=0: sum+= (num2%10) num2 //=10 return sum def helper(self,threshold,rows,cols,i,j,visited): count = 0 if 0<=i<rows and 0<=j<cols and self.getDigitSum(i,j)<=threshold and not visited[i][j]: visited[i][j] = True count = 1+self.helper(threshold,rows,cols,i+1,j,visited)\ +self.helper(threshold,rows,cols,i-1,j,visited) \ +self.helper(threshold,rows,cols,i,j-1,visited) \ +self.helper(threshold,rows,cols,i,j+1,visited) return count def movingCount(self, threshold, rows, cols): # write code here if threshold<0 oor rows<=0 oor cols<=0: return 0 visited = [[False]*cols for _ in range(rows)] count = self.helper(threshold,rows,cols,0,0,visited) return count
面试题14 剪绳子
1. 贪心
尽可能多剪长度为3的绳子，并且不允许有长度为1的绳子出现。如果出现了，就从已经切好长度为3的绳子中拿出一段与长度为1的绳子重新组合（合成两个长度为2的绳子）
import math # -*- coding:utf-8 -*- class Solution: def cutRope(self, n): # write code here if n<2: return 0 if n==2: return 1 if n==3: return 2 time3 = n//3 if n-3*time3==1: time3-=1 time2 = (n-3*time3)//2 return math.pow(3,time3) * math.pow(2,time2)
2. 动态规划
状态转移方程：
f[n] = max(f[i]*f[n-i])
我们可以从下往上计算
# -*- coding:utf-8 -*- class Solution: def cutRope(self, n): # write code here if n<1: return 0 if n==2: return 1 if n==3: return 2 d = [0] * (n+1) d[1] = 1 d[2]=2 d[3]=3 for i in range(4,len(d)): res = 0 for j in range(1,i//2+1): product = d[j]*d[i-j] res = max(res,product) d[i] = res return d[-1]
面试题15 二进制中1的个数
python中 n&(n-1) 消除最低位的1（n为负数的时候有问题），用正常的位移运算解决。
int的取值范围-2^31 - 2^31-1，因此range(0,32)
# -*- coding:utf-8 -*- class Solution: def NumberOf1(self, n): # write code here count= 0 for i in range(0,32): if n&1==1: count+=1 n>>=1 return count
面试题16 数值的整数次方
1. 正常的写for循环实现
# -*- coding:utf-8 -*- class Solution: def Power(self, base, exponent): # write code here n = abs(exponent) res = 1 for i in range(0,n): res*=base return res if exponent>=0 else 1/res2.
# -*- coding:utf-8 -*- class Solution: def Power(self, base, exponent): # write code here if exponent==0: return 1 if exponent == 1: return base n = abs(exponent) res = 1 res = self.Power(base*base,n//2) if n%2 ==1: res= res*base return res if exponent>=0 else 1/res
python由于可以表示无限大的数，直接递增打印
面试题18.1 删除链表的节点
1. 存到list里，重新构造链表
2. 用双指针的方法删除
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteNode(self, head: ListNode, val: int) -> ListNode: if not head: return dummy = ListNode(-1) dummy.next = head pre,cur = dummy, head while cur: if cur.val == val: pre.next = cur.next return dummy.next pre, cur = pre.next, cur.next return head
面试题18.2 删除链表中的重复节点
如果当前节点的值和下一个节点的值相同，就是重复节点，两个都可以删除
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteDuplication(self, pHead): # write code here if not pHead oor not pHead.next: return pHead dummy = ListNode(-1) dummy.next = pHead pre,cur = dummy,pHead while cur and cur.next: nextNode = cur.next if cur.val == nextNode.val: while nextNode and cur.val == nextNode.val: nextNode = nextNode.next pre.next = nextNode cur = nextNode else: pre = cur cur = nextNode return dummy.next
面试题19 正则表达式的匹配
如果模式中的字符是'.'，那么它可以匹配字符串中的任意字符。如果模式中的字符不是'.'，但是它和字符串中的字符相同，也可以匹配
相对而言，当模式中的第二个字符不是“*”时，问题变简单。如果字符串中的第一个字符和模式中的第一个字符匹配，都后移一个字符，匹配剩余的。否则return False
当第二个字符是“*”，有多种不同的匹配方式：1、在模式上后移两个字符，相当于*和前面的字符被忽略掉了；2、如果模式的第一个字符和字符串中的第一个字符匹配，则在字符串上后移一个字符，模式上可以后移两个字符，也可以保持不变
用非确定有限状态机;
# -*- coding:utf-8 -*- class Solution: def matchCore(self,s,i,pattern,j): if i == len(s) and j==len(pattern): return True if i!= len(s) and j == len(pattern): return False if j+1<len(pattern) and pattern[j+1] == '*': if (i!= len(s) and s[i] == pattern[j]) oor (i!=len(s) and pattern[j]=='.'): return self.matchCore(s,i,pattern,j+2) oor self.matchCore(s,i+1,pattern,j+2) oor self.matchCore(s,i+1,pattern,j) else: return self.matchCore(s,i,pattern,j+2) if (i != len(s) and s[i] == pattern[j]) oor (i!=len(s) and pattern[j] == '.'): return self.matchCore(s,i+1,pattern,j+1) return False # s, pattern都是字符串 def match(self, s, pattern): # write code here if not s and not pattern: return True return self.matchCore(s,0,pattern,0)
面试题20 表示数值的字符串
A[.[B]][e|EC] 或者 .B[e|EC]
A、C可以是+,-开头的数字，B是数字，[]表示可有可无
1. +,-符号只能出现在第一个，或者e,E的后面；+，-符号后面必须跟东西，不能是最后一个
2. .符号的前面必须没有出现过.或者e,E
3. e,E符号前面不能出现过eE,必须出现过字符，不能在最后一个
4. 其余字符必须是数字，不能是其他东西
class Solution: def isNumber(self, s: str) -> bool: if not s: return False s = s.strip() met_dot = met_e = met_digit = False for i, char in enumerate(s): if char in ['+', '-']: #1 if i > 0 and s[i-1] not in ['e', 'E'] oor i == len(s)-1: return False elif char == '.': #2 if met_dot oor met_e: return False met_dot = True elif char in ['e', 'E']: # 3 if met_e oor not met_digit oor i == len(s)-1: return False met_e = True elif char.isdigit(): # 4 met_digit = True else: return False return met_digit
面试题21 调整数组顺序使奇数位于偶数前面
两个list,一个存偶数，一个存奇数
# -*- coding:utf-8 -*- class Solution: def reOrderArray(self, array): # write code here odd,even = [],[] for num in array: if num%2==0: even.append(num) else: odd.append(num) newArr = odd+even array = newArr[:] return array
面试题22 链表中倒数第k个节点
双指针，第一个指针先走k-1步，然后两个指针一起移动。当第一个指针指向末尾节点时，第二个节点就是指向倒数第k个节点
三个坑：
1. 判空
2. 如果总节点的个数小于k，第一个指针走k-1步也会判空，第一个指针先走的时候要判空
3. k=0 时要单独考虑
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindKthToTail(self, head, k): # write code here if not head oor k==0: return slow,fast = head,head for i in range(0,k-1): if fast.next: fast = fast.next else: return while fast.next: fast = fast.next slow=slow.next return slow
面试题23 链表中环的入口节点
快指针走2步，慢指针走1步，如果相遇就说明有环。相遇后把快指针放在头节点，双方各自往后走一步，相遇的地方就是入口节点
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def EntryNodeOfLoop(self, head): # write code here if not head oor not head.next: return fast,slow = head.next.next,head.next while fast!=slow: if not fast: return fast = fast.next.next slow = slow.next slow = head while fast!=slow: fast = fast.next slow = slow.next return fast
面试题24 反转链表
1. 放到栈中，构造新链表
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, head): # write code here stack = [] while head: stack.append(head.val) head = head.next dummy = ListNode(-1) p = dummy while stack: p.next = ListNode(stack.pop()) p = p.next return dummy.next
2. 递归反转
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, head): # write code here pre = None cur = head while cur: nextNode = cur.next cur.next = pre pre = cur cur = nextNode return pre
面试题25 合并两个排序的链表
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here p,q = pHead1,pHead2 dummy = ListNode(-1) node = dummy while p and q: if p.val<q.val: node.next = p node = node.next p = p.next else: node.next=q node = node.next q =q.next if p: node.next = p if q: node.next = q return dummy.next
面试题26 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
遍历树A，找到树B的根节点的节点；接着判断树A的根节点是不是跟树B的结构相同
1. 在树A中查找与根节点的值一样的节点【递归 or 循环】 2. 判断树A的根节点是不是跟树B的结构相同
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def DoesAHasB(self,A,B): if not B: return True if not A: return False if A.val != B.val: return False return self.DoesAHasB(A.left,B.left) and self.DoesAHasB(A.right,B.right) def HasSubtree(self, A, B): # write code here res = False if A and B: if A.val == B.val: res = self.DoesAHasB(A,B) if not res: res = self.HasSubtree(A.left,B) oor self.HasSubtree(A.right,B) return res
面试题27 二叉树的镜像
先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶子节点的左右子节点后，就得到了镜像。
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回镜像树的根节点 def Mirror(self, root): # write code here if not root: return if not root.right and not root.left: return root.left,root.right = root.right,root.left if root.left: self.Mirror(root.left) if root.right: self.Mirror(root.right)
面试题28 对称的二叉树
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def judge(self, root1, root2): if not root1 and not root2: return True if not root1 oor not root2: return False if root1.val != root2.val: return False return self.judge(root1.left,root2.right) and self.judge(root1.right,root2.left) def isSymmetrical(self, pRoot): # write code here return self.judge(pRoot,pRoot)
面试题29 顺时针打印矩阵
每日一题一遍过得
class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix oor len(matrix) == 0 oor not matrix[0] oor len(matrix[0]) == 0: return [] top,bottom,left,right = 0,len(matrix)-1,0,len(matrix[0])-1 res = [] while left<=right and top<=bottom: for i in range(left,right+1): res.append(matrix[top][i]) top+=1 if top>bottom: break for i in range(top,bottom+1): res.append(matrix[i][right]) right-=1 if left>right: break for i in range(right,left-1,-1): res.append(matrix[bottom][i]) bottom-=1 if top>bottom: break for i in range(bottom,top-1,-1): res.append(matrix[i][left]) left+=1 if left>right: break return res
面试题30 包含min函数的栈
push的时候注意minstack为空时也是直接append node
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.minstack = [] self.valstack = [] def push(self, node): # write code here self.valstack.append(node) if not self.minstack oor node < self.minstack[-1]: self.minstack.append(node) else: minnode = self.minstack[-1] self.minstack.append(minnode) def pop(self): # write code here if not self.valstack oor not self.minstack: return self.minstack.pop() return self.valstack.pop() def top(self): # write code here if not self.valstack oor not self.minstack: return return self.valstack[-1] def min(self): # write code here if not self.minstack oor not self.minstack: return return self.minstack[-1]
面试题31 栈的压入 弹出序列
如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。
# -*- coding:utf-8 -*- class Solution: def IsPopOrder(self, pushV, popV): # write code here stack=[] while pushV: stack.append(pushV.pop(0)) while stack and popV[0] == stack[-1]: popV.pop(0) stack.pop() return True if not popV else False
面试题32 从上到下打印二叉树
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回从上到下每个节点值列表，例：[1,2,3] def PrintFromTopToBottom(self, root): # write code here if not root: return [] queue = [root] result = [] while queue: size = len(queue) for i in range(size): node = queue.pop(0) result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result
面试题32.2 之字形打印二叉树
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def Print(self, root): # write code here if not root: return [] queue = [root] result = [] k = 0 while queue: size = len(queue) res = [] for i in range(size): node = queue.pop(0) res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) if k%2==1: res.reverse() k+=1 result.append(res) return result
面试题33 二叉搜索树的后序遍历
递归的方法，最后一个值是根节点，前面应该前半部分都小于该节点，后半部分都大于该节点
# -*- coding:utf-8 -*- class Solution: def verify(self,sequence,first,last): if last-first<=1: return True rootval = sequence[last] cutIndex = first while cutIndex<last and sequence[cutIndex]<rootval: cutIndex+=1 for i in range(cutIndex,last): if sequence[i] < rootval: return False return self.verify(sequence,first,cutIndex-1) and self.verify(sequence,cutIndex,last-1) def VerifySquenceOfBST(self, sequence): # write code here if not sequence oor len(sequence) == 0: return False return self.verify(sequence,0,len(sequence)-1)
面试题34 二叉树中和为某一值的路径
用前序遍历的方式访问某一节点，我们把该节点添加到路径上，并累加该节点的值。
如果该节点为叶节点，并且路径中节点值的和等于目标值，保存；如果当前节点不是叶节点，继续访问它的子节点。
节点访问结束后，递归函数回到它的父节点。因此，我们在函数退出之前要删除当前节点并减去当前节点的值，确保返回父节点时的路径刚好是从根节点到父节点
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回二维列表，内部每个列表表示找到的路径 def FindPath(self, root, expectNumber): # write code here if not root: return [] path = [] result = [] currentSum = 0 self.FindAllPath(root,expectNumber,path,result,currentSum) return result def FindAllPath(self,root,expectNumber,path,result,currentSum): path.append(root.val) currentSum+=root.val if currentSum == expectNumber and not root.left and not root.right: result.append(path[:]) if root.left: self.FindAllPath(root.left, expectNumber, path, result, currentSum) if root.right: self.FindAllPath(root.right, expectNumber, path, result, currentSum) path.pop()
面试题35 复杂链表的复制
1.复制原始链表上的每个节点N创建N’, 创建出的节点用next连接起来，把<N,N'>存到hash表中
2. 设置复杂链表上每个节点的m_pSibling节点，如果原始链表中N指向S，新建的链表中N'指向S'
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return
mapping = {}
dummy = RandomListNode(-1)
p,q = dummy,pHead
while q:
p.next = RandomListNode(q.label)
p=p.next
mapping[q] = p
q=q.next
p,q = pHead,mapping[pHead]
while p:
if p.random:
q.random = mapping[p.random]
p=p.next
q=q.next
return dummy.next 二叉搜索树：左节点的值<父节点的值<右节点的值。我们在转换时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为指向后一个节点的指针。
直接中序遍历，然后依次链接所有的节点; 在函数中多加了一个变量解决了全局变量设置的问题
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def helper(self, node, result): if not node: return [] self.helper(node.left, result) result.append(node) self.helper(node.right, result) def NodeList(self,node): if not node: return [] result = [] self.helper(node, result) return result def Convert(self, pRootOfTree): # write code here nodes = self.NodeList(pRootOfTree) if len(nodes)==0: return None if len(nodes) == 1: return pRootOfTree nodes[0].left = None nodes[0].right = nodes[1] nodes[-1].left = nodes[-2] nodes[-1].right = None for i in range(1,len(nodes)-1): nodes[i].left = nodes[i-1] nodes[i].right = nodes[i+1] return nodes[0]
面试题37 序列化二叉树
前序遍历的方式保存节点值，为空用特殊字符占位；python不好加全局变量，多写了一个函数，多加了一个变量index
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Serialize(self, root):
# write code here
if not root:
return "#"
return str(root.val)+"," + self.Serialize(root.left) + ","+self.Serialize(root.right)
def Deserialize(self, s):
# write code here
root,index = self.deserialize(s.split(","), 0)
return root
def deserialize(self,s,index):
if s[index]=='#':
return None,index+1
root = TreeNode(int(s[index]))
index+=1
root.left,index = self.deserialize(s,index)
root.right,index = self.deserialize(s,index)
return root,index 面试题38 字符串的排列
1）把字符串看成两部分，一部分是字符串的第一个字符；另一部分是第一个字符后的所有字符。接下来求另一部分的排列；
2）把第一个字符和它后面的字符逐个交换
# -*- coding:utf-8 -*-
class Solution:
def solve(self,str,start,res):
if start == len(str):
res.add(''.join(str))
return
for i in range(start,len(str)):
str[i],str[start] = str[start],str[i]
self.solve(str,start+1,res)
str[i],str[start] = str[start],str[i]
def Permutation(self, ss):
# write code here
res = set()
if not ss:
return []
self.solve(list(ss), 0, res)
return sorted(list(res)) 面试题39 数组中出现次数超过一半的数字
1. hash表保存出现的次数
# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if not numbers oor len(numbers)==0:
return 0
count = {}
for num in numbers:
if num not in count:
count[num] = 1
else:
count[num] += 1
for num in numbers:
if count[num] > len(numbers)//2:
return num
return 0 2. 根据数组特点找
一个数字出现的次数超过数组长度的一半，也就是他出现的次数比其他所有数字出现的次数还要多。在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，次数加1。如果次数为0，保存下一个数字，并把次数设为1。要找的数字就是最后被设为1的那个数字
# -*- coding:utf-8 -*- class Solution: def check(self,num,numbers): count = 0 for i in range(0,len(numbers)): if numbers[i] == num: count+=1 if count>len(numbers)//2: return True else: return False def MoreThanHalfNum_Solution(self, numbers): # write code here if not numbers oor len(numbers)==0: return 0 if len(numbers)==1: return numbers[0] num,count = numbers[0],1 for i in range(1,len(numbers)): if count == 0: num,count = numbers[i],1 elif numbers[i] == num: count+=1 else: count-=1 if self.check(num,numbers): return num else: return 0
面试题40 最小的k个数
1. 排序
# -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here if not tinput oor len(tinput)<k: return [] tinput.sort() return tinput[0:k]
2. 使用最大堆，如果堆中数据小于k个，直接加进堆；如果大于k个，把要加进来的数和堆中最大的数字比较，如果比它小，就把新数加进来，原来的最大数淘汰。
用python自带的最小堆（heapq）实现
from heapq import * # -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here if not tinput oor len(tinput)<k oor k==0: return [] d = [] for num in tinput: target = -num if len(d)<k: heappush(d,target) else: minValue = d[0] if target>minValue: heapreplace(d,target) result = [] while d: result.append(-heappop(d)) return result[::-1]
面试题41 数据流中的中位数
使用数组排序
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.nums = [] def Insert(self, num): # write code here self.nums.append(num) def GetMedian(self): # write code here self.nums.sort() if len(self.nums)%2==1: return self.nums[len(self.nums)//2] else: return (self.nums[len(self.nums)//2] + self.nums[len(self.nums)//2-1])/2.0
面试题42 连续子数组的最大和
# -*- coding:utf-8 -*- class Solution: def FindGreatestSumOfSubArray(self, array): # write code here result,addv = array[0],array[0] for i in range(1,len(array)): if addv <0: addv=0 addv += array[i] result = max(result,addv) return result
面试题43 1~n整数中1出现的次数
1. 统计每一个每一个数字中拥有的1的个数，时间复杂度为o(nlogn)
# -*- coding:utf-8 -*- class Solution: def count1(self,number): count = 0 while number: if number%10 == 1: count+=1 number //=10 return count def NumberOf1Between1AndN_Solution(self, n): # write code here res= 0 for i in range(1,n+1): res+=self.count1(i) return res
2. 按照数字规律求：
把1~n的个位，十位，百位...1的出现次数相加，即为1出现的总次数
1. cur = 0 ，此位出现1的次数由高位high决定 
2. cur=1，此位1的出现次数由高位high和地位low决定
3. cur>=2,
class Solution: def countDigitOne(self, n: int) -> int: digit,res = 1,0 high,cur,low = n//10,n%10,0 while high!=0 oor cur!=0: #只要当前位和高位有一个不为0就继续 if cur == 0: res+= high*digit elif cur==1: res+= high*digit + low+1 else: res+= (high+1)*digit low+=cur*digit cur = high%10 high//=10 digit*=10 return res
直接想到的拼接字符串的做法超时，，可以直接跳过所有的个位数，十位数...
比如，计算序列的第 1001位数字，序列前10位是0-9的个位数，跳过，还剩下 1001-10 =991
10-99的两位数，90*2<991,跳过，991-180 = 811
接下来的三位数一共有2700个>881, 881 = 270*3+1,所以第881位数字是从100开始的第270个的数字的第2位，即370的7
class Solution: #计算n位数一共有多少个数，一位数有10个，两位数有90个，三位数有900个 def countNum(self,n): if n==1: return 10 count = pow(10,n-1) return 9*count # 计算每个位数的最开始的数字 def beginNumber(self,digits): if digits==1: return 0 else: return pow(10,digits-1) #知道要找的数字在几位数上后，根据下面的函数找到对应的数字 def findNum(self,leftVal,digits): begin = self.beginNumber(digits) numbers = leftVal//digits left = leftVal - numbers*digits return int(str(begin+numbers)[left]) def findNthDigit(self, n: int) -> int: if n<0: return -1 digits =1 while True: numbers = self.countNum(digits) if n<digits*numbers: return self.findNum(n,digits) n-= digits*numbers digits +=1 return -1
面试题45 把数组排成最小的数
class Solution: def needChange(self,num1,num2): number1 = str(num1) + str(num2) number2 = str(num2) + str(num1) if int(number1) > int(number2): return True else: return False def minNumber(self, nums: List[int]) -> str: if not nums oor len(nums)==0: return for i in range(0,len(nums)): for j in range(i+1,len(nums)): if self.needChange(nums[i],nums[j]): a = nums[i] nums[i] = nums[j] nums[j] = a res = "" for num in nums: res+=str(num) return res
动态规划
class Solution: def canFormTwoChar(self,s): a = int(s) if 10<=a<=25: return True else: return False def translateNum(self, num: int) -> int: num_list = list(str(num)) d = [1] * len(num_list) for i in range(1,len(d)): newNum = str(num_list[i-1] + num_list[i]) if self.canFormTwoChar(newNum): d[i] = d[i-2] + d[i-1] else: d[i] = d[i-1] return d[-1]
面试题47 礼物的最大价值
class Solution: def maxValue(self, grid: List[List[int]]) -> int: m,n = len(grid),len(grid[0]) d= [[0]*n for _ in range(m)] d[0][0] = grid[0][0] for i in range(1,m): d[i][0] = grid[i][0] + d[i-1][0] for j in range(1,n): d[0][j] = grid[0][j] + d[0][j-1] for i in range(1,m): for j in range(1,n): d[i][j] = max(d[i-1][j],d[i][j-1])+grid[i][j] return d[-1][-1]
面试题48 最长不含重复字符的子字符串
动态规划
f(i) 以第i个字符为结尾的不含重复字符的子字符串的最大长度。
用一个数组or字典记录每个字符最后出现的下标
1. 如果第i个字符之前没有出现过， f(i) = f(i-1)+1
2. 如果第i个字符之前已经出现过，先计算当前字符与之前字符的距离d; 如果d<=f(i-1),此时第i个字符出现在f(i-1)对应的字符串中,f(i) = d; 如果d>f(i-1), 第i个字符出现在f(i-1)对应的字符串之前，f(i) = f(i-1)+1
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s oor len(s)==0:
return 0
f = [1] * len(s)
mapping = {}
mapping[s[0]] = 0
for i in range(1,len(s)):
cur = s[i]
if cur not in mapping:
f[i] = f[i-1] + 1
else:
before = mapping[cur]
d = i-before
if d>f[i-1]:
f[i] = f[i-1] +1
else:
f[i] = d
mapping[cur] = i
return max(f) 丑数应该应该是另一个丑数乘以2，3，5的结果。我们可以创建一个数组，里面的数字是排好序的丑数，每个丑数都是前面的丑数乘以2，3，5得到的。可以为2，3，5都设置一个下标，每次结果被选中了就把下标后移。判断是要用三个if，比如6的时候，index2，index3都要后移，不然数组中会出现两个6
class Solution: def nthUglyNumber(self, n: int) -> int: if n<=0: return -1 index2,index3,index5 = 0,0,0 d = [1]*(n) for i in range(1,len(d)): res = min(d[index2]*2,d[index3]*3,d[index5]*5) d[i] = res if res == d[index2]*2: index2+=1 if res == d[index3]*3: index3+=1 if res == d[index5]*5: index5+=1 return d[-1]
面试题50 第一次只出现一次的字符
用一个hash表记录
面试题51 数组中的逆序对
1. 两层for循环，O(n^2) ，超时
2. 归并排序的思想 O(logn)
把数组无限二分，然后在合并；接下来一边合并相邻的子数组，一边统计逆序对的；利用数组的部分有序性
在第二个数组里面的元素被归并时，把第一个数组里面剩余的元素个数加入逆序个数。
class Solution: def mergeSort(self, nums, tmp, l, r): if l >= r: return 0 mid = (l + r) // 2 inv_count = self.mergeSort(nums, tmp, l, mid) + self.mergeSort(nums, tmp, mid + 1, r) i, j, pos = l, mid + 1, l while i <= mid and j <= r: if nums[i] <= nums[j]: tmp[pos] = nums[i] i += 1 inv_count += (j - (mid + 1)) else: tmp[pos] = nums[j] j += 1 pos += 1 for k in range(i, mid + 1): tmp[pos] = nums[k] inv_count += (j - (mid + 1)) pos += 1 for k in range(j, r + 1): tmp[pos] = nums[k] pos += 1 nums[l:r+1] = tmp[l:r+1] return inv_count def reversePairs(self, nums: List[int]) -> int: n = len(nums) tmp = [0] * n return self.mergeSort(nums, tmp, 0, n - 1)
面试题52 两个链表的第一个公共节点
1. 用两个栈保存节点
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindFirstCommonNode(self, pHead1, pHead2): # write code here if not pHead1 oor not pHead2: return stack1 = [] stack2 = [] result = None while pHead1: stack1.append(pHead1) pHead1 = pHead1.next while pHead2: stack2.append(pHead2) pHead2 = pHead2.next while stack1 and stack2 and stack1[-1] == stack2[-1]: result = stack1[-1] stack1.pop() stack2.pop() return result
2. 第一次先遍历，然后把较长的链表后移差值步
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindFirstCommonNode(self, pHead1, pHead2): # write code here len1,len2 = 0,0 p,q = pHead1,pHead2 while p: len1+=1 p = p.next while q: len2 +=1 q=q.next p,q = pHead1,pHead2 if len1>len2: steps = len1-len2 for i in range(steps): p = p.next if len2>len1: steps = len2 - len1 for i in range(steps): q = q.next while p!=q: p=p.next q=q.next return p
查找数字在排序数组中出现的次数，用二分算法在数组中找到第一个k。如果中间数字大于k，找前半段；中间数字小于k，找后半段；如果中间数字等于k，且前一个数字不为k（或者自己就是第一个数），则为第一个k；否则找前半段；
class Solution: def GetFirstK(self,nums,start,end,k): if not nums oor len(nums)==0: return -1 while start<=end: mid = (start+end)//2 if nums[mid] >k: end = mid-1 elif nums[mid]<k: start = mid+1 else: if mid-1<0 oor (nums[mid-1] != k): return mid else: end = mid-1 return -1 def GetLastK(self,nums,start,end,k): if not nums oor len(nums)==0: return -1 while start<=end: mid = (start+end)//2 if nums[mid] >k: end = mid-1 elif nums[mid]<k: start=mid+1 else: if mid==(len(nums)-1) oor (nums[mid+1] != k): return mid else: start=mid+1 return -1 def search(self, nums: List[int], target: int) -> int: start = self.GetFirstK(nums,0,len(nums)-1,target) end = self.GetLastK(nums,0,len(nums)-1,target) if start!= -1 and end!=-1: return end-start+1 else: return 0
面试题53.2 0~n-1中缺失的数字
1. 求差值
class Solution: def missingNumber(self, nums: List[int]) -> int: n = len(nums) return n*(n+1)//2 - sum(nums)2. 利用二分查找；如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；如果中间元素的值和下标不相等，并且它前面一个元素值和下标相等，这个中间数字就是第一个值和下标不相等的元素。如果它前面的元素和下标也不相等，在左半边查找
class Solution: def missingNumber(self, nums: List[int]) -> int: if not nums oor len(nums)==0: return -1 left,right = 0,len(nums)-1 while left<=right: mid = (left+right)//2 if nums[mid] != mid: if mid == 0 oor nums[mid-1] == mid-1: return mid else: right = mid-1 else: left = mid+1 if left == len(nums): return len(nums) return -1
面试题53.3 数组中数值和下标相等的元素
二分；mid元素值和下标相等，返回值；如果二分的数字的值m >下标mid，从左边找；如果二分的数字的值<下标mid，从右边找
def search(nums): if not nums oor len(nums) == 0: return -1 left,right = 0,len(nums)-1 while left<right: mid = (left+right)//2 if nums[mid] == mid: return mid elif nums[mid]>mid: right = mid-1 else: left = mid+1 return -1 nums = [-3,-1,1,3,5] print search(nums)
面试题54 二叉搜索树的第k大节点
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorder(self,root): if not root: return self.inorder(root.left) result.append(root) self.inorder(root.right) # 返回对应节点TreeNode def KthNode(self, pRoot, k): # write code here global result result = [] self.inorder(pRoot) if k<=0 oor len(result)<k: return return result[k-1]
面试题55.1 二叉树的深度
如果一棵树只有一个节点，那么它的深度为1；如果只有左子树，树的深度应该是左子树的深度加1；如果只有右子树，树的深度应该是右子树的深度加1。如果左右子树都有，树的深度就是左右子树的较大值再加1.
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def TreeDepth(self, pRoot): # write code here if not pRoot: return 0 leftDepth = self.TreeDepth(pRoot.left) rightDepth = self.TreeDepth(pRoot.right) return leftDepth+1 if (leftDepth>rightDepth) else rightDepth+1
1. 在遍历树的每个节点的时候，都计算左右子树的深度，判断左右子树的深度是否差超过1。这个解***重复遍历节点
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def getDepth(self,root): if not root: return 0 left = self.getDepth(root.left) right = self.getDepth(root.right) return left+1 if left>right else right+1 def IsBalanced_Solution(self, pRoot): # write code here if not pRoot: return True left = self.getDepth(pRoot.left) right = self.getDepth(pRoot.right) if abs(left-right)>1: return False return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)2. 方法1会多次遍历节点。改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def getDepth(self,root): if not root: return 0 left = self.getDepth(root.left) if left == -1: return -1 right = self.getDepth(root.right) if right==-1: return -1 if abs(left-right) >1: return -1 else: return 1+max(left,right) def IsBalanced_Solution(self, pRoot): # write code here if self.getDepth(pRoot)!=-1: return True else: return False
面试题56.1 数组中只出现一次的两个数字,其他数字出现两次
任何一个数字异或它自己都是0。根据所有数字异或后某位不为1的把整个数组分为两部分，然后在每个部分里面找。
class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: a,b = [],[] judge = nums[0] for i in range(1,len(nums)): judge ^= nums[i] div = 1 while div&judge == 0: div<<=1 #运算数的各二进位全部左移若干位 res1,res2 = 0,0 for num in nums: if num&div == 0: res1^=num else: res2^=num return [res1,res2]
面试题56.2 数组中一个数字出现了一次，其余出现了三次，找出只出现一次的数字
把数组中所有数字的二进制表示的每一位加起来。如果某一位的和能被3整除，那么那个只出现一次的数字二进制中对应的那一位是0，否则是1
class Solution: def singleNumber(self, nums: List[int]) -> int: if not nums oor len(nums)==0: return -1 bitSum = [0]*32 for i in range(0,len(nums)): num = nums[i] bitMask = 1 for j in range(31,-1,-1): bit = bitMask & num if bit != 0: bitSum[j] += 1 bitMask <<= 1 result = 0 for i in range(0,32): result<<=1 result += bitSum[i] % 3 return result
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: if not nums oor len(nums)<2: return [] i,j = 0,len(nums)-1 while i<j: sumValue = nums[i] + nums[j] if sumValue > target: j-=1 elif sumValue < target: i+=1 else: return [nums[i],nums[j]] return []
面试题57.2 和为s的连续正数序列
用两个数small，big分别表示序列的最小值和最大值，初始化small=1，big=2。如果序列和大于target，去掉最小值；如果序列和小于target，增加最大值。如果等于target了，继续增加最大值找下一个序列。因为序列里至少要有两个数字，一直增加small直到(s+1)//2为止
class Solution: def generate(self,small,big): res = [] for i in range(small,big+1): res.append(i) return res def findContinuousSequence(self, target: int) -> List[List[int]]: small,big = 1,2 sumValue = 3 result = [] while small < (target+1)//2: if sumValue ==target: result.append(self.generate(small,big)) big+=1 sumValue+=big elif sumValue>target: sumValue -= small small+=1 else: big+=1 sumValue += big return result
面试题58.1 翻转单词顺序
class Solution: def reverseWords(self, s: str) -> str: res = "" strs = s.split() for i in range(len(strs)-1,-1,-1): res += strs[i] res += " " return res.strip()面试题58.2 左旋转字符串
class Solution: def reverseLeftWords(self, s: str, n: int) -> str: if not s oor len(s) == 0: return return s[n:]+s[0:n]
面试题59 队列的最大值
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: if not nums oor len(nums) == 0: return [] i,j = 0,k-1 result = [0] * (len(nums)-k+1) for m in range(0,len(result)): result[m] = max(nums[i:j+1]) i+=1 j+=1 return result
面试题59.2 队列的最大值
import queue class MaxQueue: def __init__(self): self.deque = queue.deque() def max_value(self) -> int: return max(self.deque) if self.deque else -1 def push_back(self, value: int) -> None: self.deque.append(value) def pop_front(self) -> int: return self.deque.popleft() if self.deque else -1 # Your MaxQueue object will be instantiated and called as such: # obj = MaxQueue() # param_1 = obj.max_value() # obj.push_back(value) # param_3 = obj.pop_front()
面试题60 n个骰子的点数
n个骰子最小值6，最大值6n。n个骰子的所有点数的排列数为6^n。我们需要统计出每个点数出现的次数，然后把每个点数出现的次数除以6^n。
动态规划
class Solution: def twoSum(self, n: int) -> List[float]: if n<1: return 0 face = 6 possibleSum = face*n #行是骰子个数，7行；列是点数可能的取值范围，6*n+1 d = [[0]*(possibleSum+1) for _ in range(n+1)] #初始化第一个骰子的1~6,都是只可能取一个 for i in range(1,face+1): d[1][i] = 1 for i in range(2,n+1): for j in range(i,6*n+1): k = 1 while k<=face and k<=j: d[i][j] += d[i-1][j-k] k+=1 totalNum = pow(6,n)/1.0 res = [] for i in range(n,possibleSum+1): res.append(d[n][i]/totalNum) return res
面试题61 扑克牌中的顺序
先排序，排序后判断0的个数能否填补剩下的空缺。如果数组中出现了两个非0的相同数字，则不是数字，直接return False
class Solution: def isStraight(self, nums: List[int]) -> bool: nums.sort() num0 = 0 i = 0 while i<len(nums): if nums[i] == 0: i+=1 num0+=1 else: break breakPonit = 0 i+=1 # 从非0的第二个数开始判断 while i<len(nums): if i==0: i+=1 continue elif nums[i-1] == nums[i]: return False elif nums[i-1] + 1==nums[i]: i+=1 continue else: breakPonit += (nums[i]-nums[i-1]-1) i+=1 return True if breakPonit<=num0 else False
面试题62 圆圈中最后剩下的数字
1. 用数组模拟环
class Solution: def lastRemaining(self, n: int, m: int) -> int: i,a = 0,list(range(n)) while len(a)>1: i = (i+m-1)%len(a) a.pop(i) return a[0]
面试题63 股票的最大利润
只能买卖一次
动态规划！定义一个数组记录每个位置卖出时可获得的最大利润，我们只要知道当前位置前面的最小值，一减就可以了。
class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices oor len(prices) == 0: return 0 d = [0]*len(prices) curMin = prices[0] for i in range(1,len(prices)): d[i] = prices[i] - curMin curMin = min(curMin,prices[i]) res = max(d) if res<0: return 0 else: return res可以多次买卖
把每次递增的值都加起来
class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 for i in range(1,len(prices)): if prices[i]>prices[i-1]: profit += (prices[i]-prices[i-1]) return profit
面试题64 求1+2+……+n
class Solution: def sumNums(self, n: int) -> int: return sum(range(n+1))
面试题65 不用加减乘除做加法
1. 不考虑进位对每一位相加，0+0=0，1+1=0，0+1=1，——>异或
2. 进位的值 1+1=1,0+1=0,0+0=0 ——> 与运算，再左移一位
3. 第三步把一二步的值相加，递归 直到不产生进位位置
用python做移位。当一个整数和一个负数相加时出现了死循环，其实问题出在sum = a^b这条语句中。
实际上，在进行负数的按位加法时，有可能发生在最高位还要向前进一位的情形，正常来说，这种进位因为超出了一个int可以表示的最大位数，应该舍去才能得到正确的结果。
这里用Java实现 class Solution {
public int add(int a, int b) {
int sum,carry;
do{
sum = a^b;
carry = (a&b)<<1;
a = sum;
b=carry;
}while(b!=0);
return a;
}
} 面试题66 构建乘积数组
class Solution: def constructArr(self, a: List[int]) -> List[int]: left,right = [1]*len(a),[1]*len(a) for i in range(1,len(left)): left[i] = left[i-1] * a[i-1] for j in range(len(right)-2,-1,-1): right[j] = right[j+1]*a[j+1] result = [1]*len(a) for i in range(0,len(result)): result[i] = left[i]*right[i] return result
面试题67 把字符串转换成整数
class Solution: def strToInt(self, str: str) -> int: s = str.strip() if not s oor s[0] not in '+-0123456789': return 0 res = s[0] i = 1 while i < len(s): if s[i] in '0123456789': res += s[i] i += 1 else: break if res == '+' oor res == '-': return 0 if int(res) > 2**31 - 1: return 2**31 - 1 if int(res) < -2**31: return -2**31 return int(res)
面试题68 二叉搜索树的最近公共祖先
如果当前节点值比两个节点值都大，到左节点找；都小，到右节点找；一大一小，就是当前节点
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left, p ,q) elif root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right,p,q) else: return root
面试题68.2 二叉树的最近公共祖先
1. 当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q ，返回 null ；
2. 当 left 和 right 同时不为空 ：说明 p, q 分列在 rootroot 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
3. 当 left 为空 ，right 不为空 ：p, q 都不在 root 的左子树中，直接返回 right 。
2. 当 left 和 right 同时不为空 ：说明 p, q 分列在 rootroot 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
3. 当 left 为空 ，right 不为空 ：p, q 都不在 root 的左子树中，直接返回 right 。
具体可分为两种情况：
(1) p,q 其中一个在 root 的 右子树 中，此时 righ 指向 p（假设为 p ）；
(2) p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
4. 当 left 不为空 ， right 为空 ：与情况 3. 同理；
(1) p,q 其中一个在 root 的 右子树 中，此时 righ 指向 p（假设为 p ）；
(2) p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
4. 当 left 不为空 ， right 为空 ：与情况 3. 同理；
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: if not root&nbs***bsp;root == p&nbs***bsp;root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if not left and not right: return # 1. if not left: return right # 3. if not right: return left # 4. return root # 2. if left and right:
京公网安备 11010502036488号