cpp soulution


  • 0
    H
    class Solution {
    public:
    	int findIntegers(int num) {
    		vector<int> counts;
    		vector<int> sum;
    		if (num == 0)return 1;
    		counts.push_back(1);
    		if (num == 1)return 2;
    		counts.push_back(1);
    		if (num == 2)return 3;
    		counts.push_back(1);
    		if (num == 3)return 3;
    		int p = 2, now = 2, min = 4;
    		while (min * 2 <= num) {
    			counts.push_back(now);
    			now = now + counts[p++];
    			min *= 2;
    		}
    		sum.push_back(1);
    		for (int i = 1; i < counts.size(); i++) {
    			sum.push_back(sum[i - 1] + counts[i]);
    		}
    		int left = num - min, nextfind;
    		if (left >= min / 2) {
    			nextfind = min / 2 - 1;
    		}
    		else {
    			nextfind = left;
    		}
    		return sum[sum.size() - 1] + findIt(nextfind, sum);
    	}
    	int findIt(int num,vector<int>& sum) {
    		if (num == 0)return 1;
    		if (num == 1)return 2;
    		if (num == 2)return 3;
    		if (num == 3)return 3;
    		int p = 2, now = 2, min = 4;
    		while (min * 2 <= num) {
    			p++;
    			min *= 2;
    		}
    		int left = num - min, nextfind;
    		if (left >= min / 2) {
    			nextfind = min / 2 - 1;
    		}
    		else {
    			nextfind = left;
    		}
    		return sum[p] + findIt(nextfind, sum);
    	}
    };
    

Log in to reply
 

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