Algorithm --- flip digit (kotlin)

subject

Given a 32 An integer num, You can take a digit from 0 Turn into 1. Please write a program , Find the longest string you can get 1 The length of .

Example 1：

Input : num = 1775(110111011112)
Output : 8
Example 2：

Input : num = 7(01112)
Output : 4

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/reverse-bits-lcci
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Solutions

It is easy to solve this problem with dynamic programming ： Use two dynamic programming arrays current[] reverse[]

current[i] Means to include the i The subordinate of the position num Binary low order to i Bitwise continuous 1 The longest length of
reverse[i] Means to include the i Bit from low to i Bits can be flipped at most 1 individual 0->1 Continuity of 1 The longest length of

use num[i] Represents an integer num The first i The value of a

When num[i]=1 when ,current[i] = current[i-1]+1, because current[i-1] It must contain i-1 position , That is to say, he and di i Bitwise continuous , So before i-1 The maximum length of is connected with the i The length of the bit is equal to current[i], Empathy reverse[i] = reverse[i-1]+1;
num[i]=0 when , Continuous interrupt ,current[i]=0, and reverse[i] Allow flipping 1 Time , however reverse[i] It must also include the second i position , In other words, you can only flip the second i position , So there can be no flipping in front , It must be all 1, This length is exactly current[i-1], therefore reverse[i] = current[i-1]+1
Traverse num All digits , That is to say 32 Behind you ,reverse The maximum value in the array is the answer .

Equation of state ：
current[i] = num[i]==1?current[i-1]+1:0
reverse[i] = num[i]==1?reverse[i-1]+1:current[i-1]+1

Reference link ：https://leetcode.cn/problems/reverse-bits-lcci/solution/dong-tai-gui-hua-you-hua-0ms-by-dralamog-egzo/

resolvent

class Solution {
    
    fun reverseBits(num: Int): Int {
    
        var backUp = num
        val dp = Array(33) {
     0 }
        val reverse = Array(33) {
     0 }
        var max = 0
        for (i in 1..32) {
    
            val isNo1 = backUp and 1 == 1
            dp[i] = if (isNo1) dp[i - 1] + 1 else 0

            reverse[i] = if (isNo1) reverse[i - 1] + 1 else dp[i - 1] + 1
            backUp = backUp.shr(1)
            max = max.coerceAtLeast(reverse[i])
        }
        return max
    }
}

summary

1. This uses two dp Array One is used to store the previous current 0 The longest length before Easy to handle problems
I feel more and more why I can't think of it ？ Not clear thinking
2. This question is not simple