Dayx7:剑指offer

2024-06-23 23:38

文章标签 dayx7 offer

本文主要是介绍Dayx7:剑指offer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

发散思维系列

求 1+2+…+n 牛客网
要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

#递归
class Solution:def getSum(self, n):return n and n+self.getSum(n-1)#知识点之and
3 and 8  Out:8 last
3 and 0  Out:0 有一个0输出0
0 and 8  Out:0

不用加减乘除做加法 leetcode 371
不使用运算符 + 和 - ，计算两整数 a 、b 之和。

求出无进制加法结果 s1
求出进位 s2
s = s1 + s2

def getSum(self, a, b): #偷懒return sum([a,b])位运算
#Python 中，整数不是 32 位的,会一直变长，不会发生溢出；故需处理
def getSum(num1, num2):    import numpy as npwhile num2:  #等价 while nums!=0sumv=np.int32(num1 ^num2)   #无进位相加carry=np.int32((num1 & num2) <<1)  #进位相加#!!! 此时应该返回 sumv + carry，但是不能用加法# 所以循环，直到没有进位，也就不需要相加num1, num2= sumv, carry  #!!!return int(num1)

构建乘积数组 AcWing
给定一个数组A[0, 1, …, n-1]，请构建一个数组B[0, 1, …, n-1]，其中B中的元素B[i]=A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。

分析

def multiply(self, A):n=len(A)if not n: return []B=[1]for i in range(1,n):B.append(B[-1]*A[i-1])tmp=1for j in range(n-1,-1,-1):B[j]*=tmptmp*=A[j]return B

案例

67 . 字符串转化为整数 AcWing
写一个函数StrToInt，实现把字符串转换成整数这个功能。

注意:
你的函数应满足下列条件：

忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
整数后可能有任意非数字字符，请将其忽略；
如果整数长度为0，则返回0；
如果整数大于INT_MAX(2^31 − 1)，请返回INT_MAX；如果整数小于INT_MIN(−2^31) ，请返回INT_MIN；

思路

class Solution:def strToInt(self, s):self.input_valid=Trueif not s:self.input_valid=Falsereturn 0k=0while k<len(s) and s[k]==' ':k+=1is_mins=Falseif s[k]=='+': k+=1elif s[k]=='-':k+=1is_mins=Truenumber=0while k<len(s) and '0'<=s[k]<='9':number=number*10+ int(s[k])k+=1#收尾if is_mins: #等价于is_mins==Truenumber*=-1if number>2**31-1: return 2**31-1if number<-2**31: return -2**31return number

$\bf{拓展}$

$\bullet$ 知识点– $\color{blue}{进制}$
B:二进制 D:十进制 H：十六进制

十六进制中F表示15，那么G将在二十进制中表示16，依此类推…Z在三十六进制中表示35
e.g;：字符串 0x 可以出现在十六进制中，视作十六进制的符号，
$\,$ $\,$ $\,$ $\,$ $\,$ $\,$ 同理 0b 可以出现在二进制中，除此之外视作数字 0 和字母 x

Python函数-int()

最低公共祖先 leetcode 236
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

分析

经典code片段: $\textcolor{blue}{找到根节点到节点的路径}$

#解法一：搜出路径，再判断。
def lowestCommonAncestor_1(self, root, p, q):"""先找到两条根节点到节点的路径再找到最后一个公共字子节点，则为最近公共祖先"""if not root or not p or not q: returnpath_1 = []path_2 = []res = []self.dfs(root, p, path_1, res) #!!!执行完，path_1 !=[]self.dfs(root, q, path_2, res)  #!!!故重新设置path_2path_1, path_2 = res[0], res[1]  # !!!res里的eles是listn = min(len(path_1), len(path_2))for i in range(n):if path_1[i] != path_2[i]:return path_1[i - 1]if i == n - 1:return path_1[i]def dfs(self, root, q, path, res):  # 递归获取根节点到某一节点的路径if not root: returnpath.append(root)if root == q:res.append(path[:])return  # !!!self.dfs(root.left, q, path, res)self.dfs(root.right, q, path, res)path.pop()

思路

#解法二：直接在递归的过程中判断。
#不能短时间想到的解法，理解思路就OK
def lowestCommonAncestor(self, root, p, q):self.ans=Noneself.dfs(root,p,q)return self.ansdef dfs(self,root,p,q):if not root: return False #等价returnleft=self.dfs(root.left,p,q)right = self.dfs(root.right, p, q)# If the current node is one of p or qm= root==p or root==q# 左右子树和自身只要任意两个存在则返回答案if m+left+right>=2: self.ans=rootreturn m or left or right      #True+True+True>2  Out: True