从零开始的刷LeetCode生活 第28期 281-290

class Solution {
public:
    vector<string> res;
    vector<string> addOperators(string num, int target) {
        dfs(num, "", 0, 0, 0, target);
        return res;
    }

    void dfs(string &num, string path, int pos, long long sum, long long mul, int target)
    {
        if(pos == num.size())
        {
            if(sum == target) res.push_back(path);
            return;
        }
        for(int i = pos; i < num.size(); i ++)
        {
            if(i > pos && num[pos] == '0') break;
            long long v = 0;
            for(int j = pos; j <= i; j ++) v = v * 10 + num[j] - '0';
            string number = num.substr(pos, i - pos + 1);
            if(!pos)
                dfs(num, number, i + 1, v, v, target);
            else
            {
                dfs(num, path + '+' + number, i + 1, sum + v, v, target);
                dfs(num, path + '-' + number, i + 1, sum - v, -v, target);
                dfs(num, path + '*' + number, i + 1, sum - mul + mul * v, mul * v, target);
            }
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0, j = 0;
        for(i = 0; i < nums.size(); i ++)
        {
            if(nums[i] != 0)
                nums[j ++] = nums[i];
        }
        while(j < nums.size())
            nums[j ++] = 0;
    }
};

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.

class Iterator {
    struct Data;
	Data* data;
public:
	Iterator(const vector<int>& nums);
	Iterator(const Iterator& iter);
	virtual ~Iterator();
	// Returns the next element in the iteration.
	int next();
	// Returns true if the iteration has more elements.
	bool hasNext() const;
};


class PeekingIterator : public Iterator {
public:
    int _next;
    bool _hax_next;
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
        _hax_next = Iterator::hasNext();
        if(_hax_next)
            _next = Iterator::next();
	    
	}

    // Returns the next element in the iteration without advancing the iterator.
	int peek() {
        return _next;
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() {
	    int res = _next;
        _hax_next = Iterator::hasNext();
        if(_hax_next)
            _next = Iterator::next();
        return res;
	}

	bool hasNext() const {
	    return _hax_next;
	}
};

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

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int n = board.size(), m = board[0].size();
        int new_x, new_y, live;
        int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}; //八个方向左上角开始
        int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
            {
                live = 0;
                for(int k = 0; k < 8; k ++)
                {
                    new_x = i + dx[k];
                    new_y = j + dy[k];
                    if(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m)
                        if(board[new_x][new_y] & 1) live ++;
                }
                //二进制10表示由0变成1，即10进制2 死变活
                //二进制11 表示由1变成1 ，即10进制3 活变活
                //二进制01表示由1变成0，即10进制1 活变死
                if(board[i][j] & 1 && live < 2) board[i][j] = 1;
                if(board[i][j] & 1 && (live == 2 || live == 3)) board[i][j] = 3;
                if(board[i][j] & 1 && live > 3) board[i][j] = 1;
                if(!(board[i][j] & 1) && live == 3) board[i][j] = 2;
            }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j ++)
                board[i][j] = board[i][j] >> 1;
    }
};

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        stringstream raw(str);
        vector<string> words;
        string word;
        while(raw >> word) words.push_back(word);
        unordered_map<char, string> PS;
        unordered_map<string, char> SP;
        if(pattern.size() != words.size()) return false;
        for(int i = 0; i < words.size(); i ++)
        {
            char p = pattern[i];
            string s = words[i];
            if(!PS.count(p)) PS[p] =s;
            if(!SP.count(s)) SP[s] = p;
            if(PS[p] != s || SP[s] != p) return false;
        }
        return true;
    }
};