Code – 第154页

LeetCode 464. Can I Win

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:
maxChoosableInteger = 10
desiredTotal = 11

Output:
false

Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

题目大意：两个人玩游戏，从1～maxChoosableInteger中任选一个数字，第一个人先选，第二个人后选，每个人选过的数字就不能再选了～两个人谁先加起来总和超过desiredTotal谁就赢，问给出数字，第一个人能否赢得比赛～

分析：两个特殊情况：1.如果能够选的最大数字大于等于desiredTotal，第一个人又不傻肯定选最大的值～那样他就赢啦～即：
if(maxn >= desiredTotal) return true;
2.如果所有能够选的数字的总和都小于desiredTotal，再怎么选两个人都不可能赢，所以肯定输～：
总和就是首项加末项的和乘以项数除以2～：if((1 + maxn) * maxn / 2 < desiredTotal) return false;
然后建立一个canWin函数，需要用visited标记某个数字是否被选过～因为可选的数字最大不超过20，则可以用一个整型数组标记，因为整型有32位～如果1被选过就把第1位（不是第0位哦～当然也可以从0开始啦～）标记为1，如果2被选过就把第2位标记为1～这样保证所有数字不重复～
所以传入两个值，一个是想要达到（或者说超过，也就是大于等于啦）的目标数字target，另一个是visited数字标记哪些数字被选过了～
用map标记当前情况在map表中是否存在，存在的话结果保存在map里面～如果我们发现这个visited也就是这个数字选择的情况已经被保存过了，就直接返回在map里面保存的结果～
遍历i从1到maxn（maxn是可以选择的最大值，即maxChoosableInteger），表示考虑选择i的情况，用mask = 1 << i，如果mask和visited进行与运算，如果等于0说明当前的visited没有被访问过，就可以考虑这个i的情况，如果要选的这个i大于target，不傻的这个人就会选择i因为肯定能赢啦～还有种情况自己能赢，就是对方输了，即：canWin(target – i, mask | visited) == false，（mask | visited表示把i那位也标记为1～）这个时候把visited情况存起来并且return true，表示赢了～如果所有数字都遍历完还是没有return true，那就最后return false～return false之前不要忘记把当前状态存储起来～也就是m[visited] = false; ～
注意：调了两个小时的bug后来才发现！(mask & visited) == 0一开始忘记加括号了，写成了mask & visited == 0，但是&运算符比==优先级低，所以==会先运算。。所以就gg了～注意注意～号外号外～

class Solution {
private:
    int maxn;
    map<int, bool> m;
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        maxn = maxChoosableInteger;
        if(maxn >= desiredTotal) return true;
        if((1 + maxn) * maxn / 2 < desiredTotal) return false;
        return canWin(desiredTotal, 0);
    }
    bool canWin(int target, int visited) {
        if(m.find(visited) != m.end()) return m[visited];
        for(int i = 1; i <= maxn; i++) {
            int mask = (1 << i);
            if((mask & visited) == 0 && (i >= target || canWin(target - i, mask | visited) == false)) {
                m[visited] = true;
                return true;
            }
        }
        m[visited] = false;
        return false;
    }
};

class Solution {

private:

int maxn;

map<int, bool> m;

public:

bool canIWin(int maxChoosableInteger, int desiredTotal) {

maxn = maxChoosableInteger;

if(maxn >= desiredTotal) return true;

if((1 + maxn) * maxn / 2 < desiredTotal) return false;

return canWin(desiredTotal, 0);

}

bool canWin(int target, int visited) {

if(m.find(visited) != m.end()) return m[visited];

for(int i = 1; i <= maxn; i++) {

int mask = (1 << i);

if((mask & visited) == 0 && (i >= target || canWin(target - i, mask | visited) == false)) {

m[visited] = true;

return true;

}

m[visited] = false;

return false;

}

};

LeetCode 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.

题目大意：给一个二叉树，判断这个二叉树是不是合法的二叉搜索树～

分析：既然是二叉搜索树，那么按照左根右遍历后的结果一定是增序～所以只需要中序遍历一遍，判断遍历结果的数组是不是后面数一定大于前面数就可以了～

class Solution {
private:
    vector<int> v;
public:
    bool isValidBST(TreeNode* root) {
        if(root == NULL ||(root->left == NULL && root->right == NULL)) return true;
        inorder(root);
        for(int i = 1; i < v.size(); i++)
            if(v[i] <= v[i-1]) return false;
        return true;
    }
    void inorder(TreeNode* root) {
        if(root == NULL) return;
        inorder(root->left);
        v.push_back(root->val);
        inorder(root->right);
    }
};

class Solution {

private:

vector<int> v;

public:

bool isValidBST(TreeNode* root) {

if(root == NULL ||(root->left == NULL && root->right == NULL)) return true;

inorder(root);

for(int i = 1; i < v.size(); i++)

if(v[i] <= v[i-1]) return false;

return true;

}

void inorder(TreeNode* root) {

if(root == NULL) return;

inorder(root->left);

v.push_back(root->val);

inorder(root->right);

}

};

LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

题目大意：给一个整数数组，找到是否存在两个不同的下标i和j，使得nums[i]和nums[j]的差的绝对值不超过t并且i和j的差的绝对值不超过k～

分析：建立一个map，对应的是元素的值到元素的下标的映射。指针i将nums数组从头遍历到尾，j指针一开始指向0。i向右走的时候如果i和j之差大于k，且m中有nums[j]，就将nums[j]从m中移除，且j向前走一步～这样就保证了m中所有的元素满足第一个条件：i和j的差的绝对值不超过k～

接下来考虑nums[i]和nums[j]的差的绝对值不超过t，abs(num[i] – nums[j]) <= t 则 nums[j]的最小可能满足条件的值为>=nums[i] – t的，所以使用map中的lower_bound，寻找第一个大于等于nums[i] – t的地方，找到后标记为a，此时的a只是取到了可能满足的最小的a，但(a – nums[i])不一定满足，所以检验a是否存在于map中且是否abs(a->first – nums[i]) <= t。如果都满足说明可以return true～

为什么要循环的最后写map的插入呢，因为比较的是i之前的所有元素～为了防止找到的是nums[i]本身，然后让nums[i]自己本身和自己比较差值了，这样结果就不对了～
如果到最后都没有能够return true，则return false～

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        map<long, int> m;
        int j = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i - j > k && m[nums[j]] == j) m.erase(nums[j++]);
            auto a = m.lower_bound((long)nums[i] - t);
            if (a != m.end() && abs(a->first - nums[i]) <= t) return true;
            m[nums[i]] = i;
        }
        return false;
    }
};

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

map<long, int> m;

int j = 0;

for (int i = 0; i < nums.size(); ++i) {

if (i - j > k && m[nums[j]] == j) m.erase(nums[j++]);

auto a = m.lower_bound((long)nums[i] - t);

if (a != m.end() && abs(a->first - nums[i]) <= t) return true;

m[nums[i]] = i;

}

return false;

}

};

LeetCode 127. Word Ladder

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

题目大意：给出beginWord、endWord和一个字典，找到从beginWord到endWord的最短转换序列，转换要求是：1.每次只能改变一个字母～ 2.变换过程中的中间单词必须在字典中出现～（第一个beginWord不需要出现，最后一个endWord需要在字典中出现～）

分析：用广度优先搜索～先将beginWord放入队列中，然后将队列中的每一个单词从头到尾换26个字母一遍～如果换后的单词在字典中能找到～而且没有被访问过～（如果每次都找访问过的就死循环啦，不停的变来变去变同一个咋办～）那就将这个单词放入队列中继续变换～直到有一次发现在字典中找到单词的时候，这个单词恰好是endWord为止～
因为要返回路径长度～所以在队列中放一个string和int组成的pair一对～这样的话用string表示单词，int表示变换到当前单词的路径～比如startWord就是1～之后每次加1～因为题目给的是vector～把他们所有单词先放到dict的set集合中查找单词会方便很多～visit标记当前单词是否被访问过～

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        set<string> dict, visit;
        for(int i = 0; i < wordList.size(); i++)
            dict.insert(wordList[i]);
        queue<pair<string, int>> q;
        q.push(make_pair(beginWord, 1));
        while(!q.empty()) {
            pair<string, int> temp = q.front();
            q.pop();
            string word = temp.first;
            for(int i = 0; i < word.length(); i++) {
                string newword = word;
                for(int j = 0; j < 26; j++) {
                    newword[i] = 'a' + j;
                    if(dict.find(newword) != dict.end() && visit.find(newword) == visit.end()) {
                        if(newword == endWord)
                            return temp.second + 1;
                        visit.insert(newword);
                        q.push(make_pair(newword, temp.second + 1));
                    }
                }
            }
        }
        return 0;
    }
};

class Solution {

public:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

set<string> dict, visit;

for(int i = 0; i < wordList.size(); i++)

dict.insert(wordList[i]);

queue<pair<string, int>> q;

q.push(make_pair(beginWord, 1));

while(!q.empty()) {

pair<string, int> temp = q.front();

q.pop();

string word = temp.first;

for(int i = 0; i < word.length(); i++) {

string newword = word;

for(int j = 0; j < 26; j++) {

newword[i] = 'a' + j;

if(dict.find(newword) != dict.end() && visit.find(newword) == visit.end()) {

if(newword == endWord)

return temp.second + 1;

visit.insert(newword);

q.push(make_pair(newword, temp.second + 1));

}

return 0;

}

};

LeetCode 307. Range Sum Query – Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

题目大意：给一个整型数组，当调用sumRange(i, j)的时候返回i～j之间的元素的总和，当调用update(i, val)的时候将nums[i]的值更新为val

分析：本来想用sum[]数组标记和，然后更新sum[]直接返回的，结果还是意料之中的超时了。。用树状数组的方法可以解决～

解释：树状数组本质上是按照二分对数组进行分组，维护和查询都是O(lgn)的复杂度
树状数组与线段树：树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多～关于lowbit：lowbit = x & (-x), lowbit(x)也可以理解为能整除x的最大的2的幂次，如果要求[x, y]之内的数的和，可以转换成getsum(y) – getsum(x – 1)来解决～

class NumArray {
public:
    NumArray(vector<int> nums) {
       size = nums.size();
       num = vector<int>(size + 1, 0);
       sum = vector<int>(size + 1, 0);
       for(int i = 0;i < size; i++)
           update(i, nums[i]); 
    }
    
    void update(int i, int val) {
        int old = num[i+1];
        for(int j = i + 1;j <= size; j += (j & (-j)))
            sum[j] = sum[j] - old + val;
        num[i+1] = val;
    }
    
    int sumRange(int i, int j) {
        return getSum(j + 1) - getSum(i);
    }
private:
    int getSum(int k) {
        int result = 0;
        for(int i = k;i > 0;i -= (i & (-i)))
            result += sum[i];
        return result;
    }
    int size;
    vector<int> sum, num;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

class NumArray {

public:

NumArray(vector<int> nums) {

size = nums.size();

num = vector<int>(size + 1, 0);

sum = vector<int>(size + 1, 0);

for(int i = 0;i < size; i++)

update(i, nums[i]);

}

void update(int i, int val) {

int old = num[i+1];

for(int j = i + 1;j <= size; j += (j & (-j)))

sum[j] = sum[j] - old + val;

num[i+1] = val;

}

int sumRange(int i, int j) {

return getSum(j + 1) - getSum(i);

}

private:

int getSum(int k) {

int result = 0;

for(int i = k;i > 0;i -= (i & (-i)))

result += sum[i];

return result;

}

int size;

vector<int> sum, num;

};

/**

* Your NumArray object will be instantiated and called as such:

* NumArray obj = new NumArray(nums);

* obj.update(i,val);

* int param_2 = obj.sumRange(i,j);

LeetCode 130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

题目大意：给一个地图，X表示围墙，找出所有被X围墙包围的O，并且把被包围的O替换成X～

分析：我的方法是与其找被包围的O，不如反过来寻找没有被包围的O～从地图的外围一圈开始寻找～如果当前位置是O～那就找他的上下左右～把与这个O联通的所有O都标记为”*”～标记为*后，所有没有被标记为*的O就是被包围的O～那就将所有剩余的O标记为X，把所有*标记为O～返回这张地图就可以了～

class Solution {
private:
    int m, n;
public:
    void solve(vector<vector<char>>& board) {
        if(board.size() == 0) return ;
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++) {
            dfs(i, 0, board);
            dfs(i, n - 1, board);
        }
        for(int j = 0; j < n; j++) {
            dfs(0, j, board);
            dfs(m - 1, j, board);
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == '*')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
    void dfs(int row, int col, vector<vector<char>>& board) {
        if(board[row][col] != 'O') return;
        board[row][col] = '*';
        if(row - 1 > 0) dfs(row - 1, col, board);
        if(col - 1 > 0) dfs(row, col - 1, board);
        if(row + 1 < m) dfs(row + 1, col, board);
        if(col + 1 < n) dfs(row, col + 1, board);
    }
};

class Solution {

private:

int m, n;

public:

void solve(vector<vector<char>>& board) {

if(board.size() == 0) return ;

m = board.size(), n = board[0].size();

for(int i = 0; i < m; i++) {

dfs(i, 0, board);

dfs(i, n - 1, board);

}

for(int j = 0; j < n; j++) {

dfs(0, j, board);

dfs(m - 1, j, board);

}

for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) {

if(board[i][j] == '*')

board[i][j] = 'O';

else if(board[i][j] == 'O')

board[i][j] = 'X';

}

void dfs(int row, int col, vector<vector<char>>& board) {

if(board[row][col] != 'O') return;

board[row][col] = '*';

if(row - 1 > 0) dfs(row - 1, col, board);

if(col - 1 > 0) dfs(row, col - 1, board);

if(row + 1 < m) dfs(row + 1, col, board);

if(col + 1 < n) dfs(row, col + 1, board);

}

};