leetcode补全计划-20180828

1. 287 Find the Duplicate Number
   输入：vector<int>& nums
   输出：int
   题意：有n+1个数字，每个数字范围是0-n，其中只有一个数字有重复，找到这个数字。
   要求：空间复杂度O(1)，时间复杂度O(n)
   思路：将数组变化成链表，那么这个问题就可以转化成求链表中环的起始点。比如{1,3,4,2,2}可以转换成1->3->2->4->2，其中环的起始点就是2。另外一个思路就是使用bitset，但是因为题意要求了空间复杂度，所以不是最优解。但是这种情况下所使用的空间并不多，而且可以大大降低运行时间，我觉得这是实际生产中的最优解。

• 转换成链表

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int size = nums.size();
        if(size < 1) return -1;
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        fast = 0;
        while(fast != slow){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

• bitmap解法

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        bitset<32000> bit;
        for (int a : nums) {
            if (bit[a]) return a;
            bit[a] = 1;
        }
        return -1;
    }
};

2. 299 Bulls and Cows
   输入：string secret, string guess
   输出：string
   题意：secret和guess中数字大小和位置完全匹配的是bull，大小匹配但是位置不匹配的是cow。返回bull和cow各自的数量。
   思路：hashtable

class Solution {
public:
    string getHint(string secret, string guess) {
        int bull = 0;
        int cow = 0;
        int size = secret.size();
        vector<int> table(10,0);
        for(int i = 0;i < size;++ i){
            if(secret[i] == guess[i]) bull++;
            else table[secret[i] - '0']++;
        }
        for(int i = 0;i < size;++ i) if(secret[i] != guess[i]){
            if(table[guess[i] - '0'] --> 0) {
                cow++;
            }
        }
        string ret = to_string(bull) + 'A' + to_string(cow) + 'B';
        return ret;
    }
};

3. 300 Longest Increasing Subsequence
   输入：数组
   输出：int
   题意：最长增长子数列长度
   思路：front&&now

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int size = nums.size();
        if(size == 0 || size == 1) return size;
        int ret = 1;
        for(int i = 0;i < size - 1;++ i){
            ret = max(ret, help(nums, i));
        }
        return ret;
    }
    int help(vector<int>& nums, int begin){
        int ret = 0;
        int size = nums.size();
        int front = INT_MIN;
        int now = INT_MIN;
        for(int i = begin;i < size;++ i){
            if(nums[i] > now){
                ret ++;
                front = now;
                now = nums[i];
            }
            else if(nums[i] > front){
                now = nums[i];
            }
            // cout<<front<<' '<<now<<endl;
        }
        return ret;
    }
};