算法刷题篇

二维前缀和

二维前缀和

 //目标数组设定为arr[n+1][m+1]，注意题目数组是从1下标开始

如果我们使用暴力解法，每次前缀和都遍历数组那么时间复杂度就是O(m*n*q)这样的时间复杂度必然是会超时的

所以我们必须转换思路，首先创建一个前缀和数组dp[n+1][m+1]，这个数组里的每个元素都是arr[1][1]到arr[i][j]这个范围的矩阵的所有元素的和，比如以上图输入为例。

dp[2][2]就是arr数组的arr[1][1]到arr[2][2]的矩阵的和，即1+2+3+2=8。

求前缀和数组

 如果直接求的话并不好求，可以将区间矩阵分为四个区域

我们要求的就是dp[i][j] = a+b+c+d，但是b和c区域并不好求，可以变换一下方法表达式也可以写成

dp[i][j] = (a+b) + (a+c) + d - a，b区域可以看作a+b区域再减去一个a区域，c区域可以看作a+c区域再减去一个a区域。a+b区域就是dp[i-1][j]，a+c区域就是dp[i][j-1]，a区域就是dp[i-1][j-1]，d区域就是arr[i][j]所以最后可以得到

dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]

按照公式就可以以O(n)的效率完成前缀和数组

使用前缀和数组

我们要求的就是[(x1,y1)，(x2,y2)]范围的所有数据的和也就是d区域，那么按照刚刚的方法

d = (a+b+c+d) - (a+b) - (a+c) + a，(a+b+c+d)就是dp[x2][y2]，(a+b)就是dp[x1-1][y2]，(a+c)就是dp[x2][y1-1]，a就是dp[x1-1][y1-1]

所以可以得到公式d = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

代码

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别//输入int n = in.nextInt();int m = in.nextInt();int q = in.nextInt();int[][] arr = new int[n+1][m+1];for(int i = 1;i<=n;i++){for(int j = 1;j<=m;++j){arr[i][j] = in.nextInt();}}//创建前缀和数组long[][] dp = new long[n+1][m+1];for(int i = 1;i<=n;i++){for(int j = 1;j<=m;++j){dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];}}//使用前缀和数组while(q > 0){int x1 = in.nextInt() ,y1 = in.nextInt();int x2 = in.nextInt() ,y2 = in.nextInt();System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);q--;}}

和为k的子数组

和为k的子数组

首先我们可以想到暴力解法遍历nums每一个元素，判断从这个元素开始到数组末尾一共有几个和为k的子数组，但是这样的时间复杂度为O(n^2)，很可能就超时了。

然后因为是找子数组，所以很容易就想到使用滑动窗口，但是仔细思考就会发现，这个方法行不通，因为数组元素可以为负数，所以即使在窗口内的元素和大于k那么继续向右增加窗口长度最后仍然可能等于k。

最后来画图分析一下。

//sum[i]是i位置的前缀和

如果我们想要知道i位置前方有几个和为k的子数组只需要找到，i位置前面有几个和为sum[i]-k的前缀和就行。每次遍历都会找到以i下标结尾的和为k的子数组有几个，当遍历完nums数组时就能找到所有子数组了。

既然要统计个数，我们就可以用到hash表，将nums的前缀和放到hash表里，并统计个数所以我们需要一个<Integer,Integer>的hash表，表示值为xx的前缀和出现了xx次。

//如果如果整个数组的和正好为k的话，就需要一个为0的前缀和，也就是sum[i]-k=0，所以应该提前插入插入一个hash[0] = 1;

代码

class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;Map<Integer,Integer> hash = new HashMap();hash.put(0,1);int sum = 0;int ret = 0;for(int i = 0;i < n;++i){sum += nums[i];//计算前缀和ret += hash.getOrDefault(sum-k,0);//统计结果个数hash.put(sum,hash.getOrDefault(sum,0)+1);//将前缀和放到hash表}return ret;}
}

两整数之和 

两整数之和

这个题目描述很简单，求两个数之和，但是不能用加号和减号，那么就自然想到使用位运算。

举例a=12：01100，b = 21：10101

异或"^"这个符号可以看作无进位加法，比如1^0=1，1^1=0。

那么01100^10101 = 11001，这个数就是12和21的无进位相加，相当于这个数和我们的目标值，就缺失了进的位，那么我们在来分析一下，只有当两个位上都是1时才会产生进位，也就是对应两位相与的结果是1的话就说明这两位产生了进位也就是a&b，但是进位是要进到下一位所以要左移一位，就是(a&b)<<1，(01100&10101)<<1 = 01000，最后我们把a^b的得到的数和这个相加，最后得到的就是目标值。

相加的话还是要用刚刚的方法，也就是现在转换为，11001+01000，再次循环刚刚的方法。

11001^01000 = 10001，（11001&01000）<< 1 = 10000，同理再次循环刚刚的方法.

010001^010000 = 000001，(010001&010000)<<1 = 100000，同理再次循环刚刚的方法.//因为最高位进位了，所以在前面补一位。

000001^100000 = 100001，(000001&100000)<<1 = 000000，此时没有进位的值，也就说明当进位值为0时a^b得到的值就是最终值，32：100001

代码

class Solution {public int getSum(int a, int b) {while(b != 0){int m = a;a = a ^ b;//无进位相加b = (m & b) << 1;//进位}return a;}
}

只出现一次的数

只出现一次的数

 假如现在我们给数组中每个元素的第一个比特位的数加起来，因为除了目标元素其他元素都是三个三个的出现，所以如果这一位是1，那么三个数都是1，如果这个数是0，那么三个数都是0，所以我们相加得到的数一定是一个三的倍数，在加上目标元素的这一位，也就会有两种情况

3n+1或者3n+0，3n代表除目标元素外其余元素这一比特位数值之和，后面的+1和+0这代表目标元素这一比特位的值，那么我们现在令(3n+1)%3 = 1或者(3n+1)%3 = 0，发现此时我们的到的数就是目标元素这一比特位的值，所以可以得到结论

数组中所以元素的任意一比特位之和，再模3(%3)，得到的数就是我们要找的目标元素这一比特位的值

最后我们将所以元素的所有比特位都进行这个操作(3n+1或0)%3，就能找到我们的目标元素

代码 

class Solution {public int singleNumber(int[] nums) {int ret = 0;for(int i = 0;i < 32;++i){int sum = 0;for(int x: nums){sum += (x >> i) & 1;//将所有元素第i位的数相加}sum = sum % 3;if(sum == 0){ret &= (~(1 << i));//将i位置置为0}else {ret |= (1 << i);//将i位置置为1}}return ret;}
}