算法刷题篇

二维前缀和

二维前缀和

 //目标数组设定为arr[n+1][m+1]，留意标题数组是从1下标开始
如果我们使用暴力解法，每次前缀和都遍历数组那么时间复杂度就是O(m*n*q)如许的时间复杂度必然是会超时的
所以我们必须转换思绪，首先创建一个前缀和数组dp[n+1][m+1]，这个数组里的每个元素都是arr[1][1]到arr[j]这个范围的矩阵的所有元素的和，好比以上图输入为例。
dp[2][2]就是arr数组的arr[1][1]到arr[2][2]的矩阵的和，即1+2+3+2=8。

求前缀和数组
 如果直接求的话并欠好求，可以将区间矩阵分为四个区域

我们要求的就是dp[j] = a+b+c+d，但是b和c区域并欠好求，可以变动一下方法表达式也可以写成
dp[j] = (a+b) + (a+c) + d - a，b区域可以看作a+b区域再减去一个a区域，c区域可以看作a+c区域再减去一个a区域。a+b区域就是dp[i-1][j]，a+c区域就是dp[j-1]，a区域就是dp[i-1][j-1]，d区域就是arr[j]所以最后可以得到
dp[j] = dp[i-1][j] + dp[j-1] + arr[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]
代码

1. public class Main {
2.     public static void main(String[] args) {
3.         Scanner in = new Scanner(System.in);
4.         // 注意 hasNext 和 hasNextLine 的区别
5.         //输入
6.         int n = in.nextInt();
7.         int m = in.nextInt();
8.         int q = in.nextInt();
9.         int[][] arr = new int[n+1][m+1];
10.         for(int i = 1;i<=n;i++){
11.             for(int j = 1;j<=m;++j){
12.                 arr[i][j] = in.nextInt();
13.             }
14.         }
15.         //创建前缀和数组
16.         long[][] dp = new long[n+1][m+1];
17.         for(int i = 1;i<=n;i++){
18.             for(int j = 1;j<=m;++j){
19.                 dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];
20.             }
21.         }
22.         //使用前缀和数组
23.         while(q > 0){
24.             int x1 = in.nextInt() ,y1 = in.nextInt();
25.             int x2 = in.nextInt() ,y2 = in.nextInt();
26.             System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
27.             q--;
28.         }
29.     }

复制代码

和为k的子数组

和为k的子数组

首先我们可以想到暴力解法遍历nums每一个元素，判断从这个元素开始到数组末尾一共有几个和为k的子数组，但是如许的时间复杂度为O(n^2)，很可能就超时了。
然后因为是找子数组，所以很容易就想到使用滑动窗口，但是仔细思索就会发现，这个方法行不通，因为数组元素可以为负数，所以即使在窗口内的元素和大于k那么继续向右增加窗口长度最后仍然可能便是k。
最厥后绘图分析一下。

//sum是i位置的前缀和
如果我们想要知道i位置火线有几个和为k的子数组只需要找到，i位置前面有几个和为sum-k的前缀和就行。每次遍历都会找到以i下标结尾的和为k的子数组有几个，当遍历完nums数组时就能找到所有子数组了。
既然要统计个数，我们就可以用到hash表，将nums的前缀和放到hash表里，并统计个数所以我们需要一个<Integer,Integer>的hash表，表示值为xx的前缀和出现了xx次。
//如果如果整个数组的和正好为k的话，就需要一个为0的前缀和，也就是sum-k=0，所以应该提前插入插入一个hash[0] = 1;
代码

1. class Solution {
2.     public int subarraySum(int[] nums, int k) {
3.         int n = nums.length;
4.         Map<Integer,Integer> hash = new HashMap();
5.         hash.put(0,1);
6.         int sum = 0;
7.         int ret = 0;
8.         for(int i = 0;i < n;++i){
9.                 sum += nums[i];//计算前缀和
10.                 ret += hash.getOrDefault(sum-k,0);//统计结果个数
11.                 hash.put(sum,hash.getOrDefault(sum,0)+1);//将前缀和放到hash表
12.         }
13.         return ret;
14.     }
15. }

复制代码

两整数之和 

两整数之和

这个标题描述很简单，求两个数之和，但是不能用加号和减号，那么就天然想到使用位运算。
举例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
代码

1. class Solution {
2.     public int getSum(int a, int b) {
3.         while(b != 0){
4.             int m = a;
5.             a = a ^ b;//无进位相加
6.             b = (m & b) << 1;//进位
7.         }
8.         return a;
9.     }
10. }

复制代码

只出现一次的数

只出现一次的数

 如果如今我们给数组中每个元素的第一个比特位的数加起来，因为除了目标元素其他元素都是三个三个的出现，所以如果这一位是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，就能找到我们的目标元素
代码 

1. class Solution {
2.     public int singleNumber(int[] nums) {
3.         int ret = 0;
4.         for(int i = 0;i < 32;++i){
5.             int sum = 0;
6.             for(int x: nums){
7.                sum += (x >> i) & 1;//将所有元素第i位的数相加
8.             }
9.             sum = sum % 3;
10.             if(sum == 0){
11.                 ret &= (~(1 << i));//将i位置置为0
12.             }else {
13.                 ret |= (1 << i);//将i位置置为1
14.             }
15.         }
16.         return ret;
17.     }
18. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。