Dayx5:剑指offer

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

56.1. 数组中只出现一次的两个数字 leetcode 260
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素

哈希表  Time:O(2n)  Space:O(n)
#记录(每个数字出现次数)   筛选
def singleNumber(self, nums: List[int]) -> List[int]:dict={}for x in nums:if x not in dict:dict[x]=1else:dict[x]+=1res=[]for x in nums:if dict[x]==1: res.append(x)return res

新Thing

位运算--异或
def singleNumber(self, nums):mask=0for num in nums:mask ^=numk=0  # 找到为1的一位while not mask>>k&1:  #while ...!=0k+=1first=0for x in nums:if x>>k&1: first ^=xreturn first, first^mask

在python中 None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元组()都相当于False while not ; if not

---

位运算知识

$\text{分解得到各二进制位的值}$

*位运算-小总结(都先将各个数 转换为二进制，再计算)
$\cdot$ 数a&1 \,
#[一]结果为1， 数a是奇数；结果为0，a是偶数
#[二] $\text{\&}$s.t 可记录a的二进制$last位数上是否是1或者0$
#[三]拓展： 记录数a的$\text{各}$二进制位的1出现次数[对于一个数a,次数only=1或者0]

$\cdot$ a>>1 移位–$二进制位数移动$

$\text{恢复各二进制位的值，得到数a}$

$\cdot$ 左移操作 和 或运算
\, 各二进位的值恢复到数字res上

1. python 内部自带大整数运算能力，整数运算不会溢出，只要内存足够，就oK
   为了模拟溢出的效果，必须人工的进行位运算，~运算符除了求反，还是二进制的补运算符，运算过后的二进制数字按照补码解释，例如 ~（0011 1100） = （1100 0011） = -61
   越界
2. 0xffffffff
   0x16进制 \, 一个f代表4个1, 二进制的32个1
   -1表示
   -1

-____________________________________________-

56.2. 数组中唯一只出现一次的数字 leetcode 137
一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

哈希法

异或法
def singleNumber(self, nums):#记录所有数字的各二进制位的 1 的出现次数bitCount=[0]*32for num in nums:for j in range(32):bitCount[j] += num&1num>>=1res,m=0,3for i in range(32):res<<=1res |= bitCount[31-i]% mreturn res if bitCount[31]% m ==0 else ~(res ^0xffffffff)#或者return self.convert(res)def convert(self,x):if x >=2**31:x -=2**32return x

57.1 和为 s 的数字 AcWing
输入一个数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
如果有多对数字的和等于s，输出任意一对即可。
你可以认为每组输入中都至少含有一组满足条件的输出。

#两指针
def FindNumbersWithSum(self, nums, target):nums.sort()   #!!!l, r = 0, len(nums) - 1while l < len(nums) - 1:    #or l<rif (nums[l] + nums[r]) == target:return [nums[l], nums[r]]elif (nums[l] + nums[r]) < target:l = l + 1else:r = r - 1

57.2. 和为 s 的连续正数序列 AcWing
输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。

#两指针 比57.1多了计算序列和cur_sum
def findContinuousSequence(self, sum):l, r, cur_sum = 1, 2, 3  # !!!与57.1区别，r是逐步增大，不是减小；[现prob是输出序列]mid = sum >> 1  # 等价sum//2 ##至少两个数，所以小的那个数不可能大于和的一半res = []while l <= mid:if cur_sum < sum:r = r + 1cur_sum += relif cur_sum > sum:cur_sum -= ll = l + 1else:res.append(list(range(l, r + 1)))cur_sum -= ll = l + 1return res

字符串系列

58.1. 翻转字符串里的单词
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

#!!! split()运用
def reverseWords(self, s: str) -> str:return ' '.join(reversed(s.split()))

58.2. 左旋转字符串
输入字符串"abcdefg"和数字2，该函数将返回左旋转2位得到的结果"cdefgab"。

def leftRotateString(self, s, n):return s[n:]+s[:,n]

---

---

python 命令

$\bullet$知识点
a.reverse() #a被改变 #无返回值 #$输入值不能是str$
reversed(a) #a不变 #返回一个迭代器，需用循环输出 #$输入值nolimit$

a.sort() #a被改变 #无返回值
sorted(a)#a不变 #返回输出 $区别$

str.strip() 移除字符串头尾指定的字符（默认为空格或换行符）或字符序列

这篇关于Dayx5:剑指offer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---