Easy to understand: dynamic programming


  • -2
    Y

    I should have added some explanations. We use the same idea for Single Number I. We compute each bit modulo 3. For each bit, 1 can appear for 3k+1, 3k+2, or 3k times. Eventually, we use the 3k+1-type bits. So we want to record three sets of data dynamically: the bits on those positions 1 has appeared 3k+1 times; the bits on those positions 1 has appeared 3k+2 times, and the bits on those positions 1 has appeared 3k times. I use three integers to record these 3 sets of bits, where I call them: one, two, three.

    Using the idea of Dynamic Programming, we can give the recursion formula. The bits of 1 in the new number will change 3k+1-type bits to 3k+2-type bits, and 3k+2-type bits to 3k-type bits. Similarly, the bits of 0 in the new number will remain 3k+1-type bits to 3k+1-type bits. One can many different ways to write the recursion formula. I just give one as follows.

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int one=nums[0], two=0, three=~nums[0], temp1, temp2;
            for (int i=1; i<nums.size(); i++){
                temp1= (one & nums[i])|(two & (~nums[i])) ;//two
                temp2= (three &  nums[i])|(one & (~nums[i]));//one
                one=temp2;
                two=temp1;
                three=~(one|two);
            }
            return one;
        }
    };

Log in to reply
 

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