classSolution(object): defisHappy(self, n:int)->bool: temp = set() while n!=1: # 用于确定计算新的平方和 next = 0 while n!=0: first = n%10 next += first**2 n //=10 ifnextin temp: # 用于检查是否存在，如果存在说明不是快乐数 returnFalse else: temp.add(next) n = next# 记得要更新n的值 returnTrue
classSolution(object): defintersection(self, nums1:List[int], nums2:List[int])->List[int]: set1 = set(nums1) set2 = set(nums2) return [x for x in set1 if x in set2]
由于python的for ... in ...查找操作相当于对hash表的查找操作，所以直接快捷方式结束了
classSolution(object): defisIsomorphic(self, s:str, t:str)->bool: st,ts = {},{} for x,y inzip(s,t): if x in st and st[x] != y or y in ts and ts[y] != x: returnFalse else: st[x],ts[y] = y,x returnTrue
classSolution: deffirstUniqChar(self, s: str) -> int: frequency = collections.Counter(s) for i, ch inenumerate(s): if frequency[ch] == 1: return i return -1
classSolution(object): defstrStr(self, haystack:str, needle:str)->int: next = self.getnext(needle) h,n = 0,0 while h<len(haystack) and n<len(needle): if n==-1or haystack[h] == needle[n]: h += 1 n += 1 else: n = next[n] if n == len(needle): return h-n else: return -1
defgetnext(self,T:str)->List[int]: j=0 k=-1 next = [0for i inrange(len(T))] next[j]=k while j <len(T)-1: if k==-1or T[j]==T[k]: j+=1 k+=1 next[j] = k else: k = next[k] returnnext
deflongestCommonPrefix(self, strs:List(str))->str: min_str = min(strs, key=len) result = "" p = 0 while p < len(min_str): char = strs[0][p] for s in strs: if s[p] != char: return result result += char p += 1 return result
classSolution(object): deflongestPalindrome(self, s:str)->str: ans = "" for i inrange(len(s)): temp = self.search(s,i,i) iflen(temp) > len(ans): ans = temp temp = self.search(s,i,i+1) iflen(temp) > len(ans): ans = temp return ans
defsearch(self,s,first,end): while first>=0and end<len(s) and s[first] == s[end]: first -= 1 end += 1 return s[first+1:end]
classSolution(object): defarrayPairSum(self, nums:List[int])->int: ans = 0 nums = self.quick_sort(nums) print(nums) for i inrange(len(nums)//2): ans += nums[i*2] return ans
defquick_sort(self,array): iflen(array) <= 1: return array else: reference = array[0] small = [s for s in array[1:] if s < reference] equal = [e for e in array if e == reference] large = [l for l in array[1:] if l > reference] returnself.quick_sort(small) + equal + self.quick_sort(large)
deffindMaxConsecutiveOnes(self, nums: List[int]) -> int: a,b = 0,0# 分别存储当前最大连续数与历史最大连续数 for i inrange(len(nums)): if nums[i] == 0: if a > b: b = a a = 0 else: a += 1 returnmax(a,b)
# 快速排序 defquick_sort(array): iflen(array)<=1: # 当子序列长度<=1 return array # 排序完成,停止递归 else: small = [] # 由所有小于基准值的元素组成的子数组 equal = [] # 包括基准值在内并且和基准相等的元素 large = [] # 由所有大于基准值的元素组成的子数组 reference = array[0] # 选择第一个数作为基准值 # 遍历array中的每一个元素 for s in array: # 当前元素小于基准值时 if s < reference: # 当前元素插入small small.append(s) # 当前元素等于基准值 elif s == reference: equal.append(s) # 当前元素大于基准值 else: large.append(s) print(small,equal,large) # 调用自身，即为递归 return quick_sort(small) + equal + quick_sort(large)
实用版：
1 2 3 4 5 6 7 8 9
defquick_sort(array): iflen(array) <= 1: return array else: reference = array[0] small = [s for s in array[1:] if s < reference] equal = [e for e in array if e == reference] large = [l for l in array[1:] if l > reference] return quick_sort(small) + equal + quick_sort(large)
# 希尔排序 defshell_sort(array): # 设定初始增量d=n/2 d = len(array)//2 # 当增量大于0时执行,如果小于0,则退出循环 while d>0: # i 的取值范围为d到n for i inrange(d,len(array)): # 类似直接插入排序，比较当前值与指定增量的值 while i>=d and array[i-d]>array[i]: # 符号条件则交换 array[i],array[i-d] = array[i-d],array[i] # 取前一个指定增量的值，继续下一个判断 i -= d # 将增量取半,回到while循环 d = d//2 return array
# 计数排序 defcount_sort(arr): # 计算序列的最大值和最小值 maximum,minimum = max(arr),min(arr) # 申请额外的空间作为计数数组,大小为最大值减最小值+1 countArr = [0for i inrange(maximum-minimum+1)] # 申请一个存放已排序序列的等长空间 finalArr = [0for i inrange(len(arr))] # 统计各元素出现的次数,并将统计结果存入计数数组 for i in arr: # 出现一次就加1 countArr[i-minimum] += 1# 注意下标index = data - min # 对计数数组进行累加 for i inrange(1,len(countArr)): # 从第二个位置开始,每个每个位置的值等于其本身加上前者 countArr[i] += countArr[i-1] # 开始将元素反向填充到最终的数组中 for i in arr: finalArr[countArr[i-minimum]-1] = i # 填充了一个就减一 countArr[i-minimum] -= 1 return finalArr
# 桶排序 defbucket_sort(arr): maximum,minimum = max(arr),min(arr) # 确定桶的个数 buckets = [[] for i inrange(maximum-minimum)//10+1] for i in arr: # 计算各元素的所属的桶位 index = (i - minimum)//10 # list.append()---添加元素 buckets[index].append(i) # 将原数组清空 arr.clear() for i in buckets: # 桶内排序---堆排序(可以用别的替代) i = heap_sort(i) # 将已排序的桶重新放回已经清空的原数组中 arr.extend(i) return arr
# 基数排序 defradix_sort(arr): maximum = max(arr) # 确定待排序数组中的最大位数 d = 0# 用d记录最大位数 while maximum!=0: maximum = maximum//10 d += 1 # d轮排序 for i inrange(d): # 因为每一位数字都是0~9，所以建十个桶 s = [[] for k inrange(10)] for j in arr: # 从个位数开始注意进行分桶操作 s[int(j/(10**i))%10].append(j) # 用10个桶回填原数组 arr = [a for b in s for a in b] return arr
defrotate(self,matrix: List[List[int]])->List[List[int]]: rlists = list() for j inrange(len(matrix[0])): rlist = list() for i inrange(len(matrix)-1,-1,-1): rlist.append(matrix[i][j]) rlists.append(rlist) return rlists
这个实际上是通过更改读取顺序的方式，重新创建一个矩阵，但是不符合题目不额外使用空间的思想
方法二：
通过矩阵的几何特性来实现
1 2 3 4 5 6 7 8 9
defrotate(self,matrix: List[List[int]]): N = len(matrix) # 对角线互换 for i inrange(N): for j inrange(i): # 这里要仔细理解，因为接下来要进行互换，所以j要随i增大 matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j] # 水平互换 for i inrange(N): matrix[i][:] = matrix[i][::-1]
defsetZeroes(self, matrix:List[List[int]]): M=len(matrix) N=len(matrix[0]) line=[0]*M row=[0]*N for i inrange(M): for j inrange(N): if matrix[i][j]==0: line[i] = 1 row[j] = 1 for i inrange(M): for j inrange(N): if line[i]==1or row[j]==1: matrix[i][j]=0
classSolution(object): deffindDiagonalOrder(self, mat:List[List[int]])->List[int]: ans = [] Xsize = len(mat) Ysize = len(mat[0]) tot = Xsize + Ysize - 1 x,y = 0,0 for i inrange(tot): if i%2==1: while y>=0and x<Xsize: ans.append (mat[x][y]) x += 1 y -= 1 if x<Xsize: y += 1 else: y += 2 x -= 1 else: while x>=0and y<Ysize: ans.append (mat[x][y]) x -= 1 y += 1 if y<Ysize: x += 1 else: x += 2 y -= 1 return ans
int ** pp; int *p; int q; // 数据一般情况下被动态分配 //此时假设p为数据存储的位置，也是p的数据被动态分配，导致数据的位置不确定 p = &q; //但是我们能找到一个二级指针来指向p的位置，pp自身的位置是硬编码，并不会改变 pp = &p; //也就是说只要我们能找到二级指针，就能根据指向，取到q中的数据
（3）那么我们现在进一步的思考，C语言将全局的变量存放在哪里？将局部变量又存放在哪里？每个函数开头的push bp mov bp sp又有什么意义？分析以下代码思考一下
1 2 3 4 5 6 7 8 9 10 11 12
int a1,a2,a3; voidf(void); main(){ int b1,b2,b3; a1=0xa1;a2=0xa2;a3=0xa3; b1=0xb1;b2=0xb2;b3=0xb3; } voidf(void){ int c1,c2,c3; a1=0x0fa1;a2=0x0fa2;a3=0x0fa3; c1=0xc1;c2=0xc2;c3=0xc3; }
image.png
我们看到
SUB SP,+06将栈顶下移了6个字节用来存放局部变量，为什么是存放局部变量而不是全局变量呢，在存储的过程中，我们可以看到对于全局变量，是使用直接定址的方法进行存储在程序的数据段中，而对于局部变量则是以栈底的相对位置进行访问。由此可以看出，局部变量以栈的形式存储在函数的同一个栈中。
在这里我们便可以理解push bp mov bp sp的意义，通俗来讲。这是因为全局变量被存储于数据段中，而局部变量被存储于栈段中，和函数功能存放在一起，而这段指令则是用于创建一个新的函数栈帧。
我在下一篇博客中会详细讲解这个过程。
（4）此时我们进一步思考，函数的返回值被存放在哪里？分析下面的程序
1 2 3 4 5 6 7 8 9 10
intf(void); int a,b,ab; main(){ int c; c=f(); } intf(void){ ab = a+b; return ab; }
而且相较于F程序，M程序的子程序结尾多了
RET PUSH BP MOV BP,SP这一部分的作用是用于函数返回，恢复原栈帧用的
现在我们可以好好分析一下二者的区别：
首先main函数被作为了一个子程序，且在编译时被添加了很多代码
f函数则是作为一个子程序被直接调用却没有返回
因此，问题出在main函数被编译连接的过程中，我们回想f函数编译失败的报错
Linker Error:Undefined symbol _main in module C0S我们可以猜测，在连接的过程中，连接器把main.obj与C0S.obj连接在了一起，得到我们的main.exe函数。此时我们可以进一步的推断，01FA地址以前的程序都是来自COS.obj中。接下来我们对此进行验证：
