Share my c# dp solution


  • 0
    T
    public class Solution {
        
        public int FindIntegers(int num) {
            if(num == 0){
                return 1;
            }else if(num == 1){
                return 2;
            }
            
            string s = Convert.ToString(num,2);
            
            int len = s.Length;
            
            var dp1 = new int[len];
            var dp0 = new int[len];
            dp0[len-1] = 1;
            dp1[len-1] = 1;
            
            for(int i = len-2;i>=0;i--){
                dp0[i] = dp0[i+1]+dp1[i+1];
                dp1[i] = dp0[i+1];
            }
            
            int result = dp1[0]+dp0[0];
            
            for(int i = 1;i<len;i++){
                if(s[i] == '1'){
                    if(s[i-1] == '1'){
                        break;
                    }
                }else if(s[i-1] == '0'){
                    result -= dp1[i];
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.