首页 > 其他分享 >数位dp

数位dp

时间:2024-03-28 21:55:05浏览次数:27  
标签:dp2 dp1 int max ++ num dp 数位

数位dp

https://leetcode.cn/problems/reverse-bits-lcci/description/

public int reverseBits(int num) {
        int max = 0;
        int dp1 = 0;
        int dp2 = 0;
        for (int i = 0; i < 32; i++) {
            if ((num & 1) == 1){
                dp1++;
                dp2++;
            }else {
                dp2 = dp1 + 1;
                dp1 = 0;
            }
            if (dp2 > max) max = dp2;
            num = num >> 1;
        }
        return max;
    }

总结:动态规划的题 从低位向高位走, num & 1用来判断当前最后一位是不是1,也可以判断当前的数字是奇还是偶, dp1代表从低位到当前位全是1的长度,dp2代表从低位到当前位变了1次之后的长度,所以如果当前位是1,dp1,dp2都可以++,如果是0,那dp2等于上一位的dp1,也就是dp1,dp1置为0,。

标签:dp2,dp1,int,max,++,num,dp,数位
From: https://www.cnblogs.com/jeasonGo/p/18102714

相关文章

  • 02-基于STM32F407MAC与DP83848实现以太网通讯六(IPerf网络速度测试)
    一、IPerf2网络测试工具Iperf2是一个用于测试网络带宽的工具。它是Iperf的旧版本,专注于提供基本的带宽测量功能。通过在客户端和服务器之间发送测试数据流并测量其性能,用户可以评估网络连接的速度和稳定性。Iperf2提供了一种简单而有效的方式来评估网络性能。IPerf3已经发布了,但......
  • 状压 dp
    引入先看一道例题:(可能r18)有\(N\)个男生和\(N\)个女生。小A喜欢磕CP,现在小A想要磕\(N\)对CP。不过每一个人都有自己的npy,也不是随随便便就能磕成一对。现在小A找到了你,要你求出有多少种磕CP的方式。我们显然可以暴力枚举每一个男生跟谁组CP然后判断是否合法......
  • 状压DP
    状压就是把几个维度压成一个维度,通常是按\(k\)进制来压缩如dp[(1<<1145141919810)]这样相当于开了\(1145141919810\)个只有\(0/1\)的维度,二进制下每一位表示这个维度运行逝世查询一个集合\(s\)的所有子集合扩散行for(inti=s;i<MAXN;i=(i+1)|s......
  • 设计模式DP-外观模式
    #include<stdio.h>#include<string.h>#include<stdlib.h>//定义子系统AtypedefstructsubsystemA{ void(*operationA)(structsubsystemA*subsystem);}SubsystemA;//定义子系统BtypedefstructsubsystemB{ void(*operationB)(structsubsystem......
  • 设计模式DP-责任链模式
    #include<stdio.h>#include<string.h>#include<stdlib.h>//定义业务处理者抽象类typedefstructHandler{ structHandler*nextHandler; void(*handleRequest)(structHandler*handler,intrequest); void(*setNextHandler)(structHandler*CurHan......
  • 设计模式DP-表驱动模式
    静态结构体数组式构建链表式构建链接式构建#include<stdio.h>#include<stdlib.h>#include<string.h> //加doublefun_add(doubledata_front,doubledata_back){ returndata_front+data_back;}//减doublefun_sub(doubledata_front,doubledata_back)......
  • 设计模式DP-模版模式
    #include<stdio.h>#include<string.h>#include<stdlib.h>typedefstructInterface_t{ /*初始化外设USB、SPI、IIC等*/ void(*init_peripheral)(void*obj); /*初始化硬盘*/ void(*init_disk)(void*obj); /*初始化内存*/ void(*init_memory)(void*obj);......
  • 设计模式DP-原型模式
    #include<stdio.h>#include<string.h>#include<stdlib.h>//定义抽象接口typedefstructinterface_t{ structinterface_t*(*clone)(void*obj); void(*set)(void*obj,constchar*name,intage); void(*show)(void*obj); charname[32];......
  • 一类适合记忆化搜索的区间dp
    https://www.luogu.com.cn/problem/P5752https://codeforces.com/contest/598/problem/Ecf这个题考虑dp预处理,状态是三维的,转移是分割方案和所分块需要获得的巧克力数量。最后题目多次询问可以o(1)快速查询的//Problem:E.ChocolateBar//Contest:Codeforces-Educational......
  • TCP与UDP:传输层协议对比
    ......