做短视频的网站,网站功能优化的方法,建站平台 discuz,商铺营销推广方案题目链接
翻转数位
题目描述 注意点
可以将一个数位从0变为1找出能够获得的最长的一串1的长度#xff08;必须是连续的#xff09;
解答思路
参照题解使用动态规划解决本题#xff0c;对于任意一个位置i#xff0c;dp[i][0]表示到达且包含第i位不翻转0最长1的长度必须是连续的
解答思路
参照题解使用动态规划解决本题对于任意一个位置idp[i][0]表示到达且包含第i位不翻转0最长1的长度dp[i][1]表示到达且包含第i位翻转一个数位0最长1的长度如果位置idx的数位是0那么如果不翻转0该位置dp[idx][0] 0如果翻转0该位置dp[idx][1] dp[idx - 1][0] 1如果位置i的数位是1那么如果不翻转0该位置dp[idx][0] dp[idx - 1][0] 1如果翻转0该位置dp[idx][1] dp[idx - 1][1] 1观察规律可得任意位置idx的dp值只与idx - 1位置有关所以并不需要存储所有位置的dp值只需要保存前一个位置的dp值并实时更新res的值即可
代码
class Solution {public int reverseBits(int num) {int res 0;// dp[i][0]表示到达且包含第i位不翻转0最长1的长度// dp[i][1]表示到达且包含第i位翻转一个数位0最长1的长度int[][] dp new int[33][2];// int idx 1;for (int idx 1; idx 32; idx) {if ((num 1) 1) {dp[idx][0] dp[idx - 1][0] 1;dp[idx][1] dp[idx - 1][1] 1;} else {dp[idx][0] 0;dp[idx][1] dp[idx - 1][0] 1;}res Math.max(res, Math.max(dp[idx][0], dp[idx][1]));num 1;}return res;}
}关键点
动态规划的思想根据前一个位置的状态推出现在位置的状态
