数字范围与
Brian Kernighan 算法
n&(n-1) 会将n的二进制表示中的最低位为1的改为0
题目描述: 给定两个整数，计算在范围[m,n]内所有数字的按位与，包括m和n
本质就是计算n和m的二进制表示的公共前缀,利用上面的算法,每次将n的最低位为1的改为0,直到n < m此时n就是公共前缀
int rangeBitwiseAnd(int m, int n) {
while(m<n){
n&=(n-1);
}
return n;
}
或者同时右移,直到m==n
int rangeBitwiseAnd(int m, int n) {
int shift = 0;
while (m < n) {
m >>= 1;
n >>= 1;
++shift;
}
return m << shift;
}
跳跃游戏II
题目描述: 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
题目保证可以到达最后一个位置，贪心选择可以跳跃得最远的位置进行跳跃
这题的关键是在一次遍历中根据已有信息维护得到当前能跳到的最远位置
class Solution {
public:
int jump(vector<int>& nums) {
int maxpos = 0;//当前能跳到的最远位置
int end = 0;//上一次跳跃的边界
int step = 0;
for(int i = 0;i<nums.size()-1;i++){
maxpos = max(maxpos,i+nums[i]);//更新最远边界
if(i == end){ //到达上次最远边界
end = maxpos;
step++;
}
}
return step;
}
};
H指数
题目描述: 给定一位研究者的论文被引用次数数组（被引用次数是非负整数），编写一个方法计算出研究者的 h 指数。h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次。”
排序的方法就不写了，这里主要记录一下二分查找答案的思路
由于要找的h是一个0-n的整数，可以二分查找这个值，得到一个mid之后去验证是否满足条件
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int l = 0,r = n;
while(l<r){
int mid = l+(r-l)/2;
if(check(citations,mid)){
l = mid+1;
}else{
r = mid;
}
}
return l-1;
}
bool check(vector<int>& citations,int h){
int cnt = 0;
for(int i = 0;i<citations.size();i++){
if(citations[i]>=h) cnt++;
if(cnt>=h) return true;
}
return cnt>=h;
}
};
加油站
[题目描述](!https://leetcode-cn.com/problems/gas-station/]: 一条环路上有N个加油站，其中第i个加油站有gas[i]升汽油。你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i)升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
题目保证答案唯一，假设从i出发最远能到j，则i到j之间的任意一个加油站都不可能到达j，因为如果i最远能到j那i能到达i与j之间的任意一个加油站k，而到达时油箱剩余的油量肯定大于等于0，相当于从k出发再自带大于等于0的油量也只能到j，所以i到j之间的任意一个加油站都不可能到达j
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int sum = 0;
int sum2 = 0;
int start = 0;
for(int i = 0;i<n;i++){
sum += gas[i]-cost[i];
sum2 += gas[i]-cost[i];
if(sum2<0){
start = i+1;
sum2 = 0;
}
}
return sum<0?-1:start%n;
}
};
分糖果
题目描述: 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必顶得多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？
两边遍历思想，先只看左边，再只看右边，取两次遍历的最大值
int candy(int* ratings, int ratingsSize) {
int *left = malloc(ratingsSize*sizeof(int));
for(int i=0;i<ratingsSize;i++){
if(i>0&&ratings[i]>ratings[i-1]){
left[i] = left[i-1]+1;
}else{
left[i] = 1;
}
}
int re = 0;
int right = 1;
for(int i=ratingsSize-1;i>=0;i--){
if(i<=ratingsSize-2&&ratings[i]>ratings[i+1]){
right = right+1;
}else{
right = 1;
}
re += fmax(right,left[i]);
}
return re;
}
长度最小的子数组
题目描述: 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
滑动窗口比较容易想到，这里记录一下利用前缀和+二分查找的思想
由于所给数组都是正数，所以前缀和是一个递增序列，从0开始遍历下标，确定下标后二分查找target+pre[i]的位置，这个位置就是最小的j使得pre[j]-pre[i]>=target
int lowerbound(int arr[],int low,int high,int target){
while(low<high){
int mid = low+(high-low)/2;
if(arr[mid]<target){
low = mid+1;
}else{
high = mid;
}
}
return arr[low]>=target?low:-1;
}
int minSubArrayLen(int target, int* nums, int numsSize){
int *pre = malloc((numsSize+1)*sizeof(int));
pre[0] = 0;
for(int i = 1;i<=numsSize;i++){
pre[i] = pre[i-1]+nums[i-1];
}
int re = INT_MAX;
for(int i = 0;i<numsSize;i++){
int j = lowerbound(pre,i,numsSize,target+pre[i]);
if(j!=-1){
re = fmin(re,j-i);
}
}
return re==INT_MAX?0:re;
}
对称二叉树
题目描述: 给定一个二叉树，检查它是否是镜像对称的。
这个题一个比较有意思的地方在于写出比较两颗树是否镜像对称的函数之后，然后判断自身是否与自身镜像对称即可
bool isSymmetric2(struct TreeNode* root1,struct TreeNode* root2){
if(root1&&root2){
if(root1->val!=root2->val)
return false;
return isSymmetric2(root1->left,root2->right) && isSymmetric2(root1->right,root2->left);
}
if(!root1&&!root2)
return true;
return false;
}
bool isSymmetric(struct TreeNode* root){
return isSymmetric2(root,root);
}
三数之和
题目描述: 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
暴力列举i,j,k需要O(n^3)的复杂度,可以先排序，列举i,j,因为nums[i]和nums[j]确定之后剩下的值是确定的,由于
两数之和
题目描述: 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回它们的数组下标。
一种思路是先确定答案的第一个值然后找第二个值，这样需要O(n^2)的复杂度，另一种思路是先找到答案的第二个值，然后找第一个值，在遍历过程中哈希记录已经遍历过的值这样可以加快查找的效率
# O(n^2)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
try:
j = nums.index(target-nums[i],i+1)
return [i,j]
except:
continue
# O(n)
class Solution:
def twoSum(self,nums,target):
hashmap = {}
for i in range(len(nums)):
if target-nums[i] in hashmap:
return [hashmap[target-nums[i]],i]
hashmap[nums[i]] = i
有效数独
题目描述: 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
关于块的规律是board[i][j]所在的块可以看作sub[i/3][j/3]，可以用一个sub[3][3][9]的数组来记录每个块的数字出现情况
然后用两个二维数组row[9][9]和col[9][9]来记录每一行和每一列的数字情况，row[i][x]表示第i行数字x的出现次数，col[j][x]表示第j列数字x的出现次数，另外由于只是1-9的数字，可以数位哈希压缩空间
bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
int row[9]={0};
int col[9]={0};
int sub[3][3]={0};
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]!='.'){
//x的二进制表示中第i位为1表示数字i出现过
int x = (1<<(board[i][j]-'0'));
if(row[i]&x||col[j]&x||sub[i/3][j/3]&x)
return false;
row[i] |= x;
col[j] |= x;
sub[i/3][j/3] |= x;
}
}
}
return true;
}
完全二叉树的节点个数
题目描述: 给出一个完全二叉树，求出该树的节点个数。
爬楼梯
题目描述: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
简单的递归和动态规划都可以解决，这里记录一下矩阵快速幂的解法
对于一个齐次线性递推式，可以用矩阵快速幂来解决，$f(n)=\sum_{i=1}^{m}a_if(n-i)$可以表示为一个矩阵的形式如下:
$$
\begin{bmatrix}f(n)\
f(n-1)\
f(n-2)\
\vdots\
f(n-m+1)
\end{bmatrix}
=
\begin{bmatrix}a_1&a_2&a_3&\cdots&a_m\
1&0&0&\cdots&0\
0&1&0&\cdots&0\
\vdots&\vdots&\vdots&\ddots&\vdots\
0&0&0&\cdots&1
\end{bmatrix}
\begin{bmatrix}f(n-1)\
f(n-2)\
f(n-3)\
\vdots\
f(n-m)
\end{bmatrix}
$$
右边的矩阵可以继续展开，直到f(1)为止，然后就可以用矩阵快速幂来求解，此题的递推式为f(n)=f(n-1)+f(n-2),初始条件为f(1)=1,f(2)=2，最终的矩阵为
$$
\begin{bmatrix}f(n)\
f(n-1)
\end{bmatrix}
=
\begin{bmatrix}1&1\
1&0
\end{bmatrix}^{n-1}
\begin{bmatrix}2\
1
\end{bmatrix}
$$
void matrix_quick_pow(int a[2][2],int n){
//单位矩阵
int ans[2][2] = {{1,0},{0,1}};
int base[2][2];
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
base[i][j] = a[i][j];
}
}
while(n){
if(n&1){
int c[2][2] = {{0,0},{0,0}};
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
c[i][j] += ans[i][k]*base[k][j];
}
}
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans[i][j] = c[i][j];
}
}
}
int c[2][2]= {{0,0},{0,0}};
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
c[i][j] += base[i][k]*base[k][j];
}
}
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
base[i][j] = c[i][j];
}
}
n >>= 1;
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
a[i][j] = ans[i][j];
}
}
int climbStairs(int n){
int a[2][2] = {{1,1},{1,0}};
matrix_quick_pow(a,n-1);
return 2*a[0][0]+a[1][0];
}
负二进制转换
题目描述: 给出数字 N，返回由 “0” 和 “1” 组成的字符串，该字符串是 N 的负二进制（base -2）表示。
- 进制转换
首先明确负二进制的定义，负二进制的权值是-2的幂次方，即-2^0,-2^1,-2^2…，所以一个数的负二进制表示是将这个数分解为-2的幂次方的和，如果像正二进制数一样用除-2取余的方法来求负二进制数，会发现余数会出现0,1,-1三种情况，所以需要将余数为-1的情况转换为0,1的情况，如果n = x*(-2)-1那n也可以表示为n = (x+1)*(-2)+1，这样就可以将余数为-1的情况转换为1的情况
class Solution:
def baseNeg2(self, N: int) -> str:
ans = ""
while N:
x = N // -2
r = N % -2
if r < 0:
x += 1
r += 2
ans += str(r)
N = x
return ans[::-1] if ans else "0"
- 位运算
举一个例子10，它的原码表示为1010，为8+2，负二进制下表示为11110，为16-8+4-2==8+2。一个想法是针对原码的二进制表示来进行运算得到结果。如果直接将原码作为答案只有部分数字是正确的，比如5在两边都表示为101，原因是它的二进制不包含奇数位的1，如果原码包含奇数位的1就需要进行处理，处理的方式就是向前进1位，因为原码表示中此处的1表示正数，如果想要它表示它原来的数值只要将该位前面一位进1那就相当于它还是原来的数值。比如10(十进制)的二进制表示1010里面的两个1都是奇数位上的，向前进位得到11110，但如果是7这样原码表示为111，进位之后得到1011但是最高位的1仍然是奇数位所以继续进位得到11011，这样就得到了正确的负二进制表示。
class Solution:
def baseNeg2(self, N: int) -> str:
if N == 0:
return "0"
ans = ""
for i in range(1,32,2):
if N & (1 << i):
N += (1 << (i+1))
while N:
ans = str(N & 1) + ans
N >>= 1
return ans if ans else "0"
吃掉N个橘子的最少天数
题目描述: 厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
简化描述：从n开始，每天可以选择将n变为n-1,n/2,n/3(后面两种情况需要能整除)，问将n变为0的最少天数
第一比较直观的想法是从1开始递推到n，如果知道f(1)~f(n-1)的所有值，则
f(n) = f(n-1)+1
if n%2==0:
f(n) = min(f(n),f(n/2)+1)
if n%3==0:
f(n) = min(f(n),f(n/3)+1)
但是这样是O(n)的复杂度，对于题目来说会超时
一个很直观的想法就是应该尽量减少只吃1个橘子的操作，尽量用2和3来减少橘子的数量，假设连续进行了k次只吃1个橘子之后进行了一次吃2个橘子，那么这k+1天的操作，剩余的橘子为:
$(n-k)/2$
令k0 = n%2,则
$(n-k0)/2 - (k-k0)/2 = (n-k)/2$
也就是先进行k0次-1操作然后折半然后再进行(k-k0)/2次-1操作可以达到与原来一样的效果，而现在进行的-1操作次数为
$k0+(k-k0)/2$
容易证明小于等于k，同理可以证明对于3的情况也是一样的，所以可以用下面的方式来解决，总结起来就是-1操作尽量为/2与/3服务，由于k0=n%2与k0=n%3，连续的-1操作不会超过2。
int minDays(int n){
if(n<=1)
return n;
return min(n%2+1+minDays(n/2),n%3+1+minDays(n/3));
}
由上述公式可以得到时间复杂度公式:
$T(n) = T(n/2) + T(n/3) + 1$
将$T(n) = O(n^t)$代入得到:
$O(n^t) = O(n^t/2) + O(n^t/3) + 1$
两边同时除以O(n^t)得到:
$1 = 1/2^t + 1/3^t$
可以解出t≈0.78
由于递归会有重复计算，可以用记忆化搜索来解决
class Solution {
private:
unordered_map<int,int> umap;
public:
int minDays(int n) {
if(n<=1)
return 1;
if(umap.count(n))
return umap[n];
umap[n] = min(minDays(n>>1)+1+n%2,minDays(n/3)+1+n%3);
return umap[n];
}
};
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2128099421@qq.com
