ACM——刷题时应该注意的一些关键问题

持续更新

位运算

用移位代替乘除法

移位的效率远高于乘除法
除以2时一般直接右移一位即可
乘以2时一般直接左移一位即可

用位运算判断奇偶性

将整数与1做与运算,值为1表示为奇数,为0表示为偶数

判断二进制数中1的个数

方法一: n=(n-1)&n

n = (n-1) & n 可以将二进制数n中的最后一位1变成0
不停执行该语句,知道n为0,执行次数即二进制数n中1的数量

方法二: result=n&flag

flag初始化为与n相同的类型(二进制位数一致)
flag从1,2,4….,为2的次方数,即初始化为1,每次向左移动一位,直到flag为0为止(此时说明flag移位溢出了,n的每一位都进行过比较了)
累计result为1的次数就是二进制数n中1的数量

错误方法: result=n&1

这种方法不设置flag变量,每次将n左移一位,直到n为0
当n为负数时会引发无线循环,所以此方法是错的

小数的精度

比较两个小数是否相等

无论a,b类型是否相等(float, double),都不能直接使用==符号直接比较

定义以下函数实现比较即可|a-b| < \(\epsilon\) (\(\epsilon\)是一个误差允许的极小值)

bool Equal(double num1, double, num2){
	if(num1-num2 < 0.0000001 && num1-num2 > -0.0000001)
		return true;
	return flase;
}

为什么存在精度问题

因为十进制的小数存到内存时是二进制,此时有很多无线循环,但是二进制位数有限,所以有误差
一般来说,double类型足以满足我们日常计算的精度,在无需很高精度时使用float可以减少内存占用
实例:
1
2
3
4
5
6
7
8
double a = 0.9;
float b = 0.9;
if(a == (double)b)
printf("a==b is true")
else
printf("a==b is flase")
# output:
a==b is false
- 对于小数0.9,表示为二进制后小数部分是无线循环小数,在float类型时与double类型时由于保留的小数位不同,所以值不同

最大最小整数

最小负数

# int
int INT_MIN = 0x80000000; //32位
# long
long LONG_MIN = 0x8000000000000000; //64位

最大正数

# int
int INT_MAX = 0x7FFFFFFF; //32位
# long 
long LONG_MAX = 0x7FFFFFFFFFFFFFFF; //64位

第一要务:输入检查

无论何时,函数实现的第一步都应该是检查输入是否合法

常见的检查

指针:是否为空
整数:是否满足条件(大于0,小于0等)
多个整数之间的关系:是否满足大小关系等

访问数组时必须首先确认

数组已初始化
访问的Index没有超过数组

关于折半搜索和查找

一般来说low从0开始,high从数组长度开始(注意，有时候high如果从len-1开始则可能造成无法访问到最后一个位置？)
- 相关题目：LeetCode 35题 Search Insert Position

mid定义为(low + high)/2

如果mid的定义如下
1
mid = (low + high) / 2
那么每次查找结束时更新时应该作如下更新
1
2
low = mid + 1
high = mid
或者
1
2
low = mid + 1
high = mid - 1
如果此时使用下面的语句作为更新
1
low = mid
- low == high - 1有low == mid,上面的式子将造成死循环

mid定义为(low + high + 1)/2

如果mid的定义如下
1
mid = (low + high + 1) / 2
那么每次查找结束时更新时应该作如下更新
1
2
low = mid
high = mid - 1
或者
1
2
low = mid + 1
high = mid - 1
如果使用下面的语句作为更新
1
high = mid
- low == high - 1有high == mid,上面的式子将造成死循环
二分查找相等的数时往往可以使用
1
2
low = mid + 1
high = mid - 1
但是查找的是当前数组不存在的节点的存放位置时要注意查找时
1
2
low = mid + 1
high = mid
- 这样确保i和j退出时相等
- 相关题目：LeetCode 35 Search Insert Position

深度优先遍历和回溯法的异同

深度优先方法(DFS, Depth First Search)使用栈实现,广度优先方法(BFS, Breadth First Search)使用队列实现
一般来说在树中遍历时才有深度优先搜索这种说法，不然比如数组的全部组合遍历都叫做回溯法，而不是DFS
对于树而言，回溯法也是遵循深度优先遍历原则实现的
回溯法可以访问已经访问过的节点，而深度优先一般来说不会再访问已经访问过的节点

DFS是把所有可能的情况考虑到就行了，但回溯法可能会重视访问节点的顺序[LeetCode 79 Word Search]

def solution(nums):
	path, result = [], []
	* 如果nums含有重复元素，需要重新排序
	def backtrace(index):
	    if 满足存储条件:
	    	result.append(path[:])
		if 不需要继续迭代:
			return
	    * 迭代访问内部节点(不同情况访问方式不同，详情看下面)
	    * 一种简单的可能是
	    for i in range(*视具体情况变化):
	    	* 如果nums含有重复元素，需要判断是否跳过(如果nums当前节点与上一个节点重复，则跳过)
	    	path.append(nums[i])
	    	* 不同情况不同回溯方式
	    		* 当path里面不能重复访问同一元素时
	    			* backtrace(i+1)
	    		* 当path里面能重复访问同一元素时
	    			* backtrace(i)
	    	path.pop()
	backtrace(0)
	return result

特殊情况，如果path不能访问同一元素而且不同顺序相同元素算是不同路径的时候，我们可能必须使用rest对象在迭代中记录当前未被访问的对象
- 此时由于不同顺序相同元素算是不同路径，所以我们不能用每次只能向前访问的方法来实现去除重复(及[index:], 这种每次只能向前访问的方法会将先[a, b], [b, a]视为重复而去除，只保留[a, b]当(a < b时))

关于递归函数内部的节点访问方式

其实在使用回溯法访问一个数组时，可以考虑这个我们在访问一棵树，从空节点开始，然后每次迭代所有符合的子节点

| 路径是否可以访问同一节点多次 | 顺序不同节点相同是否算不同路径 | 原始数组中是否包含重复元素 | 预处理 |每一层迭代代码 |
| :——: | :——: | :——: | :——: |
| 是 | 是 | 是 | data.sort() | for i in [:]:
if与前一个相等:
continue
visit(i)
backtrace()
最后移除重复路径|
| 是 | 是 | 否 | - | for i in [:]:
visit(i)
backtrace() [待更新]|
| 是 | 否 | 是 | data.sort() | for i in [index:]:
if与前一个相等:
continue
visit(i)
backtrace(i)
最后移除重复路径|
| 是 | 否 | 否 | - | for i in [index:]:
visit(i)
backtrace(i)|
| 否 | 是 | 是 | data.sort()
rest存储剩余元素| for i in rest:
if与前一个相等:
continue
visit(i)
backtrace(rest-i)|
| 否 | 是 | 否 | rest存储剩余元素 | for i in rest:
visit(i)
backtrace(rest-i) |
| 否 | 否 | 是 | data.sort() | for i in [index:]:
if与前一个相等:
continue
visit(i)
backtrace(i+1) |
| 否 | 否 | 否 | - | for i in [index:]:
visit(i)
backtrace(i+1)|

对列表中数字列表的排序

1	List[List[number]]

找出所有列表的所有数中最大的数M
定义一个函数,用一个M+1进制的数对每个内层列表进行映射表示
- 系数:
  - 需要递增排序的位前面系数为1
  - 需要递减排序的位前面系数为-1
  - 无需排序的位前面系数为0
- 示例:
  1
  2
  def key(x):
  return x[0]*(M+1)**3 - x[1]*(M+1)**2 - x[2]*(M+1) + x[3]
  - 对第一和第四位按照递增排序,第二和第三位按照递减排序
映射函数定义后可以使用sort函数排序
1
l.sort(key=key)

也可以使用lambda函数定义

1	l.sort(key=lambda x: x[0](M+1)3 - x[1](M+1)*2 - x[2](M+1) + x[3])

使用 memo 存储中间结果

memo可理解为备忘录,但是和传统的备忘录设计模式有一定区别,后者的目标是恢复对象之前的某个状态,前者的目标更应该理解为动态规划的思想dp存储计算中间值

对某些可能会多次被求解的子空间(子数组,子集等), 且子空间能够独立的情况
- 这种题目对应一般可以使用DFS求解,但是由于子空间能够独立,使用DFS会多次求解子空间,从而产生超时的情况
- 子空间能够独立的就应该使用memo
如果能够唯一标识(能作为字典的Key值)这些空间数据,即可使用memo存储
memo 为一个已子空间唯一标识为 Key, 子空间的对应求解结果为Value
相关题目: LeetCode 140, Word Break II

在使用特殊字符节省空间

在使用DFS搜索空间中的路径时,往往需要记录访问过的点,不能重复访问
常用的做法是开辟一个新的相同大小的visited数组,记录是否访问过当前结点
一种更好的做法是每次记录当前结点的值, 然后修改为一个特殊字符, DFS 完成后恢复成原始字符, 这种做法无需开辟新的空间

位运算