LC1523.在区间范围内统计奇数数目

一开始没审题，居然构造了一个数组去做…

• 然后重新看，首先先想到的暴力解就是遍历low到high，然后每一个数都对二取余。但是这样的暴力解就没什么锻炼

• 那肯定再想一个思路，Low和high都有两种情况，要么是奇数，要么是偶数。
  那么一共就四种情况然后又因为奇数是偶数相邻的，所以说我们很大概率可以研究其中一种情况，然后把其他情况转化成那个情况。

• 思路和代码如下

  int countOdds(int low, int high) {// [low，high] 共 high -low + 1个数字// 开区间的话是 high - low - 1个数字//可以分为几种情况//两个端点分别可能是奇数和偶数，那么2x2=4种// 端点是奇偶和偶奇则是一样的，开区间有偶数个数字// 其中奇数个数便是 (high-low - 1)/2个int addOfEdge = low + high;if(addOfEdge % 2 == 1)return (high - low - 1)/2 + 1;else// 端点之和是偶数，端点是奇奇和偶偶，如果再分类也可以，但是可以同意变成上面的情况{// 偶偶的话，可以low+1 high-1 先变成奇奇的情况)// 那就统一成了奇奇的情况：如果high再+1,又变成了奇偶的情况，且不增加奇数个数if(low % 2 ==0){low +=1;high -=1;}high += 1;return (high - low - 1)/2 + 1;}

• 继续优化，还有个很常见的思路：大的减去小的，考研数学里面分区域也常用
  我们可以找一个相同的起点：0
  区间可以划分为[0,high]和[0,low-1]
  先统一成[0,x]研究
  [0,x]有多少奇数呢？
  我们纠结的点无非在于奇数偶数，那么就先找两个相邻的来研究
  比如说[0,3]是1,3
  [0,4]是1,3
  [0,5]是1,3,5
  [0,6]是1,3,5
  肯定会想到除以2(是向下取整的)，那就看看什么情况
  3/2=1,4/2=2,5/2=2,6/2=3
  所以如果x是偶数，可以不加1，但是加1没影响，如果x是奇数，x要+1才能得到正确的结果，所以可以统一成 (x+1 )/2
  因此就是(high+1)/2 - (low-1+1)/2

  int countOdds(int low, int high) {// 计算区间内的奇数个数return (high + 1) / 2 - low / 2;}
  

  上面有些啰嗦，让AI精炼我的表达
  

• 官方题解：位运算，应该是更高效一些

  int pre(int x) {return (x + 1) >> 1; // 意思是 x + 1 除以 2，即 x 除以 2 向上取整}// 计算区间 [low, high] 内的奇数个数
  int countOdds(int low, int high) {return pre(high) - pre(low - 1);
  }
  

• 和copilot聊聊，让它评价一下暴力解