哈希表
- 看到数组或者可以转换成数组的题目，会先想一遍暴力，然后在 会考虑
哈希表是不是可以帮助降低时间复杂度 - 就像看到
二叉树或很自然的想到 DFS 和 BFS (概率很高) - 169. 多数元素
- 面试题56 - I. 数组中数字出现的次数
- 136. 只出现一次的数字
1095. 山脉数组中查找目标值
- 难度：
困难 - 本题涉及算法：
二分查找 - 思路：
二分查找找到峰顶分割数组 - 类似题型:
题目1095. 山脉数组中查找目标值
(这是一个 交互式问题 ）
给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。
何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
首先，A.length >= 3
其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
A[0] < A[1] < ... A[i-1] < A[i]A[i] > A[i+1] > ... > A[A.length - 1]
你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
- MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
- MountainArray.length() - 会返回该数组的长度
注意：
- 对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
- 为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。
示例 1：
输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
示例 2：
输入：array = [0,1,2,4,2,1], target = 3
输出：-1
解释：3 在数组中没有出现，返回 -1。
提示：
3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9
方法一
解题思路
- 搜索指定值 二分查找
- 对于这种 可以分成左右数组来获取值
- 先寻找峰值
class Solution(object):
# 搜索指定值 二分查找
# 对于这种 可以分成左右数组来获取值
# 先寻找峰值
def findInMountainArray(self, target, mountain_arr):
res = [-1,-1]
lo = 0
hi = mountain_arr.length()
top=0
# 判断最高峰
while lo<hi:
mid = lo+ (hi-lo)//2
if mountain_arr.get(mid) > mountain_arr.get(mid-1):
lo = mid + 1
else:
hi = mid
top = lo -1
lo = 0
hi = top
# 左半
while lo<hi:
mid = lo+ (hi-lo)//2
if mountain_arr.get(mid) == target:
res[0] = mid
if mountain_arr.get(mid) > target:
hi = mid
else:
lo = mid + 1
lo = top
hi = mountain_arr.length()
# 右半
while lo<hi:
mid = lo+ (hi-lo)//2
if mountain_arr.get(mid) == target:
res[1] = mid
if mountain_arr.get(mid) > target:
lo = mid + 1
else:
hi = mid
if res[0]==-1:
return res[1]
return res[0]
// java版会超时
public int findInMountainArray(int target, MountainArray mountainArr) {
int lo =0,hi = mountainArr.length(),top=0;
int[] res = new int[]{-1,-1};
// 判断最高峰
while(lo<hi) {
int mid = lo+ (hi-lo)/2;
if (mountainArr.get(mid]>mountainArr.get(mid-1))
lo = mid+1;
else if(mountainArr.get(mid]<mountainArr.get(mid-1))
hi = mid;
}
top = lo-1;
lo = 0;
hi = top;
// 左半
while(lo<hi){
int mid = lo+ (hi-lo)/2;
if (mountainArr.get(mid)==target)
res[0] = mid;
if (mountainArr.get(mid)>target)
hi = mid;
else
lo = mid+1;
}
hi = mountainArr.length();
lo = top;
// 右半
while(lo<hi){
int mid = lo+ (hi-lo)/2;
if (mountainArr.get(mid)==target)
res[1] = mid;
if (mountainArr.get(mid)>target)
lo = mid+1;
else
hi = mid;
}
if (res[0]==-1)
return res[1];
return res[0];
}
欧几里得算法(辗转相除法)
- 相关题目
1. 欧几里得算法(辗转相除法)
这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。
欧几里得法(辗转相除法) 通过举例说明1
举例： 105和85的最大公约数
- 第一轮计回算 105÷85=1…20
- 第二轮计算 85÷20=4…5
- 第三轮计算 20÷5=4
- 第三轮没有余数， 因此 105和85的最大公约数就是第三轮计算的被除数 5
欧几里得法(辗转相除法) 通过举例说明2
举例： 21和17的最大公约数
- 第一轮计回算 21÷17=1…4
- 第二轮计算 17÷4=4…1
- 第三轮计算 4÷1=4
- 第三轮没有余数， 因此 105和85的最大公约数就是第三轮计算的被除数 1
- 基于这条定理：
首先，我们先计算出a除以b的余数c，把问题转化成求出b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求出c和d的最大公约数；再然后计算出c除以d的余数e，把问题转化成求出d和e的最大公约数……以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。
贴代码：
def first_way(a, b):
"""
第一种方法：欧几里得算法----辗转相除法
:param a: 第一个数
:param b: 第二个数
:return: 最大公约数
"""
# 如果最终余数为0 公约数就计算出来了
while(b!=0):
temp = a % b
a = b
b = temp
return a
2. 穷举法(一个一个除)
这个比较好理解。因为a,b两个数的最大公因数肯定小于等于相对更小的那个数，所以从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。代码如下：
def second_way(a, b):
"""
第二种方法：一个一个除
:param a: 第一个数
:param b: 第二个数
:return: 最大公约数
"""
# 保证a>b
if(a<b):
a,b = b,a
for i in range(1,b+1):
if (a%i==0) and (b%i==0):
value = i;
return value
3. stein算法
看下面这两个结论
- gcd(a, a) = a， 也就是一个数和他自己的公约数是其自身。
- gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。
def third_way(a,b):
"""
第三种方法思想：stein算法
gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。
当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个偶数
和一个奇数的最大公约数时，可以先将偶数除以2。
:param a: 第一个数
:param b: 第二个数
:return: 最大公约数
"""
#保证b比a小
if a < b:
a, b = b, a
if (0 == b):
return a
# a,b都是偶数 除2右移一位即可
if a % 2 == 0 and b % 2 == 0:
return 2 * third_way(a >> 1, b >> 1)
# a是偶数
if a % 2 == 0:
return third_way(a >> 1, b)
# b是偶数
if b % 2 == 0:
return third_way(a, b >> 1)
# 都是奇数
return third_way((a + b) >> 1, (a - b) >> 1)
求出a,b的最大公约数后，利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数的 最小公倍数：
# 求两个数的最小公倍数
def lcm(a,b):
return a * b / third_way(a, b)
4. 三个数的最大公约数和最小公倍数
计算三个数的最大公约数时，我是利用之前写好的计算2个数的最大公约数的方法，先算出a,b的公约数，再用a,b的公约数与c再代入方法，此时返回的值就是三个数的最大公约数了。
同样，在计算三个数的最小公倍数时，多次嵌套，先求出两个数的最小公倍数，再求其与第三个数的最小公倍数。
def three_num(a,b,c):
"""
求三个数的最大公约数
:param a: 第一个数
:param b: 第二个数
:param c: 第三个数
:return: 这三个数的最大公约数
"""
# 多次嵌套，返回3个数的最大公约数
return first_way(first_way(a,b),c)
按位与、或、异或等运算方法
按位与运算符（&）
参加运算的两个数据，按二进制位进行“与”运算。
运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;
即：两位同时为“1”，结果才为“1”，否则为0
例如：3&5 即 0000 0011 & 0000 0101 = 0000 0001 因此，3&5的值得1。
另，负数按补码形式参加按位与运算。
“与运算”的特殊用途：
- 清零。如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
- 取一个数中指定位
- 方法：找一个数，对应X要取的位，该数的对应位为1，其余位为零，此数与X进行“与运算”可以得到X中的指定位。
例：设X=10101110，
取X的低4位，用 X & 0000 1111 = 0000 1110 即可得到；
还可用来取X的2、4、6位。
- 判断 是否为 基数
if ((nums & 1) == 1){ // 基数 } if ((nums & 1) == 0){ // 偶数 } - 求交集
a = set([1,2,3,5,4,5,6,5]) b = set([1,2,4,23]) print(a&b) 输出：1，2，4
按位或运算符（|）
参加运算的两个对象，按二进制位进行“或”运算。
运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1；
即 ：参加运算的两个对象只要有一个为1，其值为1。
例如:3|5 即 0000 0011 | 0000 0101 = 0000 0111 因此，3|5的值得7。
另，负数按补码形式参加按位或运算。
“或运算”特殊作用：
- 常用来对一个数据的某些位置1。 方法：找到一个数，对应X要置1的位，该数的对应位为1，其余位为零。此数与X相或可使X中的某些位置1。
例：将X=10100000的低4位置1 ，用 X | 0000 1111 = 1010 1111即可得到。
异或运算符（^）
参加运算的两个数据，按二进制位进行“异或”运算。
运算规则：0^0=0； 0^1=1； 1^0=1； 1^1=0；
即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。
“异或运算”的特殊作用：
- 使特定位翻转找一个数，对应X要翻转的各位，该数的对应位为1，其余位为零，此数与X对应位异或即可。
例：X=10101110，使X低4位翻转，用X ^ 0000 1111 = 1010 0001即可得到。
- 与0相异或，保留原值 ，X ^ 0000 0000 = 1010 1110。
从上面的例题可以清楚的看到这一点。
取反运算符（~）
参加运算的一个数据，按二进制位进行“取反”运算。
运算规则：~1=0； ~0=1；
即：对一个二进制数按位取反，即将0变1，1变0。
使一个数的最低位为零，可以表示为：a&~1。
~1的值为1111111111111110，再按“与”运算，最低位一定为0。因为“~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。
左移运算符（«）
将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。
例：a = a << 2 将a的二进制位左移2位，右补0，
左移1位后a = a * 2;
若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。
右移运算符（»）
将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
操作数每右移一位，相当于该数除以2。
例如：a = a >> 2 将a的二进制位右移2位，
左补0 or 补1 得看被移数是正还是负。
>> 运算符把 expression1 的所有位向右移 expression2 指定的位数。expression1 的符号位被用来填充右移后左边空出来的位。向右移出的位被丢弃。
例如，下面的代码被求值后，temp 的值是 -4：
-14 （即二进制的 11110010）右移两位等于 -4 （即二进制的 11111100）。
var temp = -14 >> 2
无符号右移运算符（»>）
>>> 运算符把 expression1 的各个位向右移 expression2 指定的位数。右移后左边空出的位用零来填充。移出右边的位被丢弃。
例如：var temp = -14 >>> 2
变量 temp 的值为 -14 （即二进制的 11111111 11111111 11111111 11110010），向右移两位后等于 1073741820 （即二进制的 00111111 11111111 11111111 11111100）。
复合赋值运算符
位运算符与赋值运算符结合，组成新的复合赋值运算符，它们是：
&= 例：a &= b 相当于a=a & b
|= 例：a |= b 相当于a=a | b
>>= 例：a >>= b 相当于a=a >> b
<<= 例：a <<= b 相当于a=a << b
^= 例：a ^= b 相当于a=a ^ b
运算规则：和前面讲的复合赋值运算符的运算规则相似。
-
|=：两个二进制对应位都为0时，结果等于0，否则结果等于1；
-
&=：两个二进制的对应位都为1时，结果为1，否则结果等于0；
-
^=：两个二进制的对应位相同，结果为0，否则结果为1。
不同长度的数据进行位运算
如果两个不同长度的数据进行位运算时，系统会将二者按右端对齐，然后进行位运算。
以“与”运算为例说明如下：我们知道在C语言中long型占4个字节，int型占2个字节，如果一个long型数据与一个int型数据进行“与”运算，右端对齐后，左边不足的位依下面三种情况补足，
- 如果整型数据为正数，左边补16个0。
- 如果整型数据为负数，左边补16个1。
- 如果整形数据为无符号数，左边也补16个0。
如：long a=123;int b=1;计算a & b。
如：long a=123;int b=-1;计算a & b。
如：long a=123;unsigned int b=1;计算a & b。
常用技巧
一句话知识点
- 检查数字是否在哈希集(如HashSet)中需要 O(1) 的时间，而对于其他数据结构，则需要 O(n) 的时间
- python divmod() 函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a // b, a % b)
>>divmod(7, 2) (3, 1) - python 数组的 insert 方法可以指定位置插入数据，且元数据后移一位，在java中 listArray.add 同样的功能
- python 循环 range(start, stop[, step])
- python 倒叙 a[::-1]
细节知识点
左右移动运算符
<< : 左移运算符，num << 1，相当于num乘以2
>> : 右移运算符，num >> 1，相当于num除以2
>>> : 无符号右移运算符，num >>> 1，相当于num除以2，忽略符号位，空位都以0补齐
python
tertools.permutations(list）这个库。。自动返回列表的全排列啊
循环
range(start, stop[, step])
start: 计数从 start 开始。默认是从 0 开始。例如range（5）等价于range（0， 5）;
stop: 计数到 stop 结束，但不包括 stop。例如：range（0， 5） 是[0, 1, 2, 3, 4]没有5
step：步长，默认为1。例如：range（0， 5） 等价于 range(0, 5, 1)
小根堆
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
zip()
zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。
divmod()
Python divmod() 函数接收两个数字类型（非复数）参数，返回一个包含商和余数的元组(a // b, a % b)。
最大数 最小数
float("inf") 最大浮点数 对应 Integer.MAX_VALUE
float("-inf") 最小浮点数 对应 Integer.MIN_VALUE
队列 堆
stack 栈是Vector的一个子类，它实现了一个标准的 后进先出 的栈。
queue 先进先出
PriorityQueue 优先队列 (最大的先出)
给二维数组排序
- java 使用Arrays对二维数组个性化排序
- Arrays.sort(people, Comparator.comparingInt(o -> o[0])); 按照index0 排序
- Arrays.sort(people, Comparator.comparingInt(o -> o[1])); 按照index1 排序
- Arrays.copyOf() 用法
StringBuffer
StringBuffer.reverse() 参数反转
collections.defaultdict(int)
tree_dict = collections.defaultdict(int) 生成默认的字典 相当于 java中的 Map.getOrDefault(key,0)
通过 tree_dict.items() 遍历出字典中的key 和 value
python中取摸 和需要注意 和java不一样
python 中 -1%10 = 9 ， -1//10=-1
java 中 -1%10 = 1 ， -1//10=0
判断是否为数字
Character.isDigit(char ch)
python 判断数组中元素是否相等
len(set(nums)) == 1
python 两个数组的交集
set(strs) & set(strs)
339 post articles, 43 pages.