1. 題目列表

• 兩句話中的不常見單詞（模擬hashmap）
• 螺旋矩陣 III（二維網(wǎng)格行走模擬）
• 可能的二分法（判斷二分圖劈伴，BFS染色法）
• 雞蛋掉落（二維dp，或公式推導(dǎo)）

2. 兩句話中的不常見單詞

hashmap按條件查詢單詞啊胶。

代碼：

class Solution {
    public String[] uncommonFromSentences(String A, String B) {
        List<String> res = new ArrayList<String>();
        HashMap<String, Integer> map1 = new HashMap<String, Integer>();
        HashMap<String, Integer> map2 = new HashMap<String, Integer>();
        String[] s1 = A.split(" ");
        String[] s2 = B.split(" ");
        for (String s : s1){
            // System.out.println(s);
            if (map1.get(s) == null){
                map1.put(s, 1);
            }else{
                map1.put(s, map1.get(s) + 1);
            }
        }
        for (String s : s2){
            if (map2.get(s) == null){
                map2.put(s, 1);
            }else{
                map2.put(s, map2.get(s) + 1);
            }
        }
        for (String s : s1){
            if (map1.get(s) == 1 && map2.get(s) == null)
                res.add(s);
        }
        for (String s : s2){
            if (map2.get(s) == 1 && map1.get(s) == null)
                res.add(s);
        }
        return res.toArray(new String[res.size()]);
    }
}

3. 螺旋矩陣 III

定義移動的步長S，當(dāng)前的方向direct睬涧，分情況討論當(dāng)前的方向蝌诡。 步長的移動規(guī)律是每次移動兩次相同的步長S后，S++看疙。

代碼：

class Solution {
public:
    
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        int r = r0, c = c0, direct = 1, step = 1, prestep = 0;
        int cnt = 1;
        vector< vector<int> > res;
        vector<int> init(2);
        init[0] = r0, init[1] = c0;
        res.push_back(init);
        while (cnt < R * C){
            vector<int> coor(2);
            if (direct == 1){
                // 遍歷的每一個步都需要判斷是否是答案路徑
                for (int i = 1; i <= step; i++){
                    c++;
                    if (judge(r, c, R, C)){
                        coor[0] = r, coor[1] = c;
                        res.push_back(coor);
                        cnt++;
                    }
                }
                direct = 2;
            }else if (direct == 2){
                for (int i = 1; i <= step; i++){
                    r++;
                    if (judge(r, c, R, C)){
                        coor[0] = r, coor[1] = c;
                        res.push_back(coor);
                        cnt++;
                    }
                }
                direct = 3;
            }else if (direct == 3){
                for (int i = 1; i <= step; i++){
                    c--;
                    if (judge(r, c, R, C)){
                        coor[0] = r, coor[1] = c;
                        res.push_back(coor);
                        cnt++;
                    }
                }
                direct = 0;
            }else if (direct == 0){
                for (int i = 1; i <= step; i++){
                    r--;
                    if (judge(r, c, R, C)){
                        coor[0] = r, coor[1] = c;
                        res.push_back(coor);
                        cnt++;
                    }
                }
                direct = 1;
            }
            if (prestep == step){
                step++;
            }else{
                prestep = step;
            }
        }
        return res;
    }
    
    bool judge(int r, int c, int R, int C){
        if (r < 0 || r >= R || c < 0 || c >= C)
            return false;
        else return true;
    }
};

4. 可能的二分法

BFS染色法判斷是否是二分圖豆拨，如果存在相鄰的結(jié)點顏色相同，則返回false能庆，否則返回true施禾。

代碼：

class Solution {
public:
    /*
        BFS染色法判斷是否是二分圖，如果存在相鄰的結(jié)點顏色相同搁胆，則返回false弥搞，否則返回true
    */
    bool visited[2010];
    int g[2010][2010], color[2010];
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        memset(visited, false, sizeof(visited));
        memset(color, 0, sizeof(color));
        fill(g[0], g[0] + 2010 * 2010, 0x7fffffff);
        for (int i = 0; i < dislikes.size(); i++){
            g[dislikes[i][0]][dislikes[i][1]] = g[dislikes[i][1]][dislikes[i][0]] = 1;
        }
        bool flag = true;
        for (int i = 1; i <= N; i++){
            if (!visited[i] && !BFS(i, 1, N)){
                flag = false;
                break;
            }
        }
        return flag;
    }
    
    bool BFS(int s, int c, int n){
        queue< pair<int, int> > q;
        q.push(make_pair(s, c));
        visited[s] = true;
        while (!q.empty()){
            pair<int, int > u = q.front();
            q.pop();
            color[u.first] = u.second;
            for (int i = 1; i <= n; i++){
                // 如果存在鄰接點染色相同
                if (g[u.first][i] == 0x7fffffff) continue;
                if (color[i] == u.second) return false;
                if (!visited[i]){
                    q.push(make_pair(i, -u.second)); // 染成相反的顏色
                    visited[i] = true;
                }
            }
        }
        return true;
    }
    
};