当前位置: 首页 > news >正文

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聊聊,让它评价一下暴力解
    在这里插入图片描述


http://www.mrgr.cn/news/53404.html

相关文章:

  • 111 - exercise 5
  • 【时时三省】(C语言基础)函数介绍strncmp
  • Vue详细入门(语法【三】)
  • kafka入门
  • 计算机网络架构实例
  • 阿里商品发布框架如何覆盖海量规则
  • 王牌功能 | 法大大“合同起草”,让合同定稿不再难搞!
  • Java 异步编程——常用线程池 ThreadPoolExecutor
  • 《OpenCV计算机视觉》—— 年龄与性别预测
  • 【服务器部署】Nodejs环境搭建
  • 单例模式(自动加载)
  • 提高效率从编写 init.sh 开始
  • 基于微博评论的自然语言处理情感分析
  • #保持每天更新第一天(1)_文本预处理小技巧_中英文翻译分割技巧_从中文右边空格分割,用rsplit(‘ ‘, 1)
  • YOLO系列入门:1、YOLO V11环境搭建
  • 锅炉水处理历年真题附答案(二)
  • GIT batch的支持中文的方法和系统建议
  • Windows自带录屏工具操作教程和四款录屏神器推荐!
  • 2024.10.18 软考学习笔记
  • HashMap优点总结及源码分析