【CCL-2019】How to Fine-Tune BERT for Text Classification?

1. Contributions

  • We propose a general solution to fine-tune the pre-trained BERT model, which includes three steps:
    • (1) further pre-train BERT on within-task training data or in-domain data;
    • (2) optional fine-tuning BERT with multi-task learning if several related tasks are available;
    • (3) fine-tune BERT for the target task.
  • We also investigate the fine-tuning methods for BERT on target task, including preprocess of long text, layer selection, layer-wise learning rate, catastrophic forgetting, and low-shot learning problems.
  • We achieve the new state-of-the-art results on seven widely-studied English text classification datasets and one Chinese news classification dataset

2. Methodology

  • Fine-Tuning Strategies
    • Dealing with long texts: head+tail(empirically select the first 128 and the last 382 tokens) is the best
    • Features from Different layers
    • Catastrophic Forgetting: a lower learning rate to overcome
    • Layer-wise Decreasing Layer Rate
  • Further Pre-training
    • Within-task and in-domain(partition the seven English datasets into three domains: topic, sentiment, and question) further pre-training can significantly boost its performance
    • A preceding multi-task fine-tuning is also helpful to the single-task fine-tuning, but its benefit is smaller than further pre-training
    • Cross-domain further pre-training can not bring an obvious benefit in general. It is reasonable since BERT is already trained on a general domain

paper

【DeepLo-2019】Domain Adaptation with BERT-based Domain Classification and Data Selection

Approach:

1. In the first step, we train a domain classifier with the same model architecture on the data from different domains with domain labels.

Bert-classifier

BERT domain adaptation

2. In the second step, we select a subset of source domain data based on the domain probability from the domain classifier, and train the original model on the selected source data.

The trained domain classifier is then used to predict the target domain probability for each data point from the source domain. Source data points with the highest target domain probability are selected for fine-tuning BERT for domain adaptation.

Application:

  • multi-source domain adaptation
  • applied to few-shot learning scenarios in which the selected source domain data can be used to augment the limited target domain training data

paper

DFS

130. 被围绕的区域

给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。

找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后,矩阵变为:

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
public class Onehundred_thirty {
    /**
     * dfs
     * 依次将与边界上O相邻的O全部标记为M,表示他们不会被包围;剩下的O一定是被包围的,所以最终将M节点标记为O,O节点标记为X
     */
    private int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1 && board[i][j] == 'O')
                    dfs(i, j, board);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(int i, int j, char[][] board) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')
            return;
        board[i][j] = 'M';
        for (int[] direction : directions) {
            dfs(i + direction[0], j + direction[1], board);
        }
    }
}
class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    void solve(vector<vector<char>> &board) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1 && board[i][j] == 'O')
                    dfs(board, i, j);
            }
        }
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == 'M')
                    board[i][j] = 'O';
            }
        }
    }

    void dfs(vector<vector<char>> &board, int i, int j) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O')
            return;
        board[i][j] = 'M';
        for (auto direction:directions) {
            dfs(board, i + direction.first, j + direction.second);
        }
    }
};

200. 岛屿数量

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3
package gongel_first;

public class Twohundred {
    /**
     * DFS
     * 极其类似130题
     */
    public void dfs(char[][] grid, int row, int col, int m, int n) {
        if (row >= m || row < 0 || col >= n || col < 0 || grid[row][col] != '1')//一定要加grid[row][col] == '0',避免重复走
            return;
        grid[row][col] = '0';
        dfs(grid, row - 1, col, m, n);//上
        dfs(grid, row + 1, col, m, n);//下
        dfs(grid, row, col - 1, m, n);//左
        dfs(grid, row, col + 1, m, n);//右
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int m = grid.length;
        int n = grid[0].length;
        int numIsland = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {//没有被访问过
                    dfs(grid, i, j, m, n);
                    numIsland++;
                }
            }
        }
        return numIsland;
    }
}
class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    int numIslands(vector<vector<char>> &grid) {
        int num_island = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    num_island++;
                    dfs(grid, i, j);
                }
            }
        }
        return num_island;
    }

    void dfs(vector<vector<char>> &grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1')
            return;
        grid[i][j] = '0';
        for (auto direction:directions) {
            dfs(grid, i + direction.first, j + direction.second);
        }
    }
};

695. 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11,因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。
public class Sixhundred_ninetyFive {
    /**
     * 和200题几乎完全一样,只是该题需要返回值而已
     */
    private int[][] directions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1)
                    maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }

    public int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
            return 0;
        int area = 1;
        grid[i][j] = 0;//不用回溯,下次从别的地方也不用再次访问
        for (int[] direction : directions) {
            area += dfs(grid, i + direction[0], j + direction[1]);
        }
        return area;
    }
}
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        if (grid.empty() || grid[0].empty())
            return 0;
        int max_area = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    int temp = 0;
                    dfs(grid, i, j, temp);
                    if (max_area < temp)
                        max_area = temp;
                }
            }
        }
        return max_area;
    }

    void dfs(vector<vector<int>> &grid, int i, int j, int &temp) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1)
            return;
        temp += 1;//temp也不能回溯,因为主程序是全部遍历
        grid[i][j] = 2;//避免再次访问;不能回溯
        dfs(grid, i + 1, j, temp);
        dfs(grid, i - 1, j, temp);
        dfs(grid, i, j + 1, temp);
        dfs(grid, i, j - 1, temp);
    }
};

547. 朋友圈

班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。
注意:

N 在[1,200]的范围内。
对于所有学生,有M[i][i] = 1。
如果有M[i][j] = 1,则有M[j][i] = 1。
package gongel_first;

public class Fivehundred_fortySeven {
    /**
     * 法一:DFS
     * 求连通图的数量,可以画邻接表
     * 与 200 岛屿问题 有不同的地方,连通图问题和上色问题的区别
     * 本题:[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->1
     * 200题:[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->4
     */
    public void dfs(int[][] M, int i, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < M.length; j++) {
            if (!visited[j] && M[i][j] == 1) {
                dfs(M, j, visited);
            }
        }
    }

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int m = M.length;
        int circleNums = 0;
        boolean[] visited = new boolean[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i]) {
                    circleNums += 1;
                    dfs(M, i, visited);
                }
            }
        }
        return circleNums;
    }

    /**
     * 法二:并查集:https://gongel.cn/?p=312
     */
    private int findFather(int[] father, int son) {
        while (son != father[son]) {//初始化时自己为自己的父亲,如果现在自己不是自己的父亲, 说明自己找到了真正的父亲,那需要一直循环找到祖先
            son = father[son];
        }
        return son;
    }

    public int findCircleNum2(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int[] father = new int[200];
        int numFriends = 0;
        //初始化
        for (int i = 0; i < M.length; i++)
            father[i] = i;
        for (int i = 0; i < M.length; i++) {
            for (int j = i + 1; j < M.length; j++) {//只需要考虑上三角矩阵,因为这是无向图----对称矩阵
                if (M[i][j] == 1) {
                    int fatherI = findFather(father, i);
                    int fatherJ = findFather(father, j);
                    if (fatherI != fatherJ)
                        father[fatherI] = fatherJ;
                }
            }
        }
        for (int i = 0; i < M.length; i++) {
            if (father[i] == i)
                numFriends++;
        }
        return numFriends;
    }
}
给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。

说明:

如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
所有的机场都用三个大写字母表示(机场代码)。
假定所有机票至少存在一种合理的行程。
示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
/**
     * 用DFS回溯需要考虑一堆问题:
     * 1.目的地需要排序
     * 2.使用过的行程不能再使用
     */
    private List<String> ans;
    private Map<String, PriorityQueue<String>> map = new HashMap<>();//保存相同出发地的所有目的地(按字母序)

    public List<String> findItinerary(List<List<String>> tickets) {
        ans = new ArrayList<>();
        if (tickets == null || tickets.size() == 0)
            return ans;
        for (List<String> ticket : tickets) {
            String src = ticket.get(0);
            String dst = ticket.get(1);
            if (!map.containsKey(src)) {
                PriorityQueue<String> pq = new PriorityQueue<>();
                map.put(src, pq);
            }
            map.get(src).add(dst);
        }
        dfs("JFK");
        Collections.reverse(ans);
        return ans;

    }

    private void dfs(String src) {
        PriorityQueue<String> pq = map.get(src);
        if (pq != null) {
            while (!pq.isEmpty()) {
                dfs(pq.poll());
            }
        }
        ans.add(src);
    }
class Solution {
public:
    //欧拉路径(https://www.cnblogs.com/vocaloid01/p/9514023.html)
    vector<string> findItinerary(vector<vector<string>> &tickets) {
        unordered_map<string, multiset<string>> from_to;//multiset相当于小根堆
        for (auto ticket:tickets)
            from_to[ticket[0]].insert(ticket[1]);
        vector<string> ans;
        dfs("JFK", from_to, ans);
        return vector<string>(ans.rbegin(), ans.rend());

    }

    void dfs(string from, unordered_map<string, multiset<string>> &from_to, vector<string> &ans) {
        while (from_to[from].size() != 0) {
            string next = *from_to[from].begin();
            from_to[from].erase(from_to[from].begin());//可能存在相同的地点,所以只能erase迭代器
            dfs(next, from_to, ans);
        }
        ans.push_back(from);//一定倒着存,将孤立节点放在最后访问。题目保证一定会有路径
    }
};

79. 单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
public boolean exist2(char[][] board, String word) {
//和695、200差不多
        boolean result;
        boolean[][] visited=new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    result = dfs2(board, word, i, j, 0,visited);
                    if (result) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private static boolean dfs2(char[][] board, String word, int i, int j, int index,boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length|| visited[i][j]) {
            return false;
        }
        if (board[i][j] != word.charAt(index)) {
            return false;
        }

        boolean result;
        visited[i][j]=true;//标记已经访问:不会回溯
        result = dfs2(board, word, i - 1, j, index + 1,visited)
                || dfs2(board, word, i + 1, j, index + 1,visited)
                || dfs2(board, word, i, j - 1, index + 1,visited)
                || dfs2(board, word, i, j + 1, index + 1,visited);
        visited[i][j]=false;//恢复未访问
        return result;
    }
class Solution {
public:
    bool exist(vector<vector<char>> &board, string word) {
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0])
                    if (dfs(board, word.substr(0), i, j, visited))
                        return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>> &board, string word, int i, int j, vector<vector<bool>> &visited) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[0] != board[i][j] || visited[i][j])
            return false;
        if (word.size() == 1 && word[0] == board[i][j])
            return true;
        visited[i][j] = true;
        bool result = dfs(board, word.substr(1), i - 1, j, visited) || dfs(board, word.substr(1), i + 1, j, visited) ||
                      dfs(board, word.substr(1), i, j + 1, visited) || dfs(board, word.substr(1), i, j - 1, visited);
        visited[i][j] = false;
        return result;
    }
};

417. 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。

 

提示:

输出坐标的顺序不重要
m 和 n 都小于150
 

示例:

 

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
public class Fourhundred_seventeen {
    /**
     *  反向思维---DFS
     *  依题意,最左边和最上面可以流向太平洋,最右边和最下面可以流向大西洋
     *  那么,可以从最左边和最上面开始dfs所有可以到达的山脉,即为可以流向太平洋的山脉
     *  从最右边和最下面开始dfs所有可以到达的山脉,即为可以流向大西洋的山脉
     *  注意:此时dfs的方向为从高度低的山脉向高度高的山脉走
     *  参考:https://leetcode-cn.com/problems/pacific-atlantic-water-flow/comments/36773
     */
    public List<List<Integer>> pacificAtlantic2(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return ans;
        m = matrix.length;
        n = matrix[0].length;
        boolean[][] reachPacific = new boolean[m][n];
        boolean[][] reachAtlantic = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(matrix, i, 0, reachPacific);//从最左出发判断是否可到达Pacific
            dfs(matrix, i, n - 1, reachAtlantic);//从最右出发判断是否可达到Atlantic
        }
        for (int j = 0; j < n; j++) {
            dfs(matrix, 0, j, reachPacific);//从最上出发判断是否可到到Pacific
            dfs(matrix, m - 1, j, reachAtlantic);//从最下出发判断是否可到达Atlantic
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (reachPacific[i][j] && reachAtlantic[i][j]) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    ans.add(temp);
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] matrix, int startX, int startY, boolean[][] reach) {
        if (startX < 0 || startX > m || startY < 0 || startY > n || reach[startX][startY])
            return;
        reach[startX][startY] = true;
        for (int i = 0; i < 4; i++) {
            int newstartX = startX + direction[i][0];
            int newstartY = startY + direction[i][1];
            if (isValid(newstartX, newstartY) && matrix[newstartX][newstartY] >= matrix[startX][startY])
                dfs(matrix, newstartX, newstartY, reach);
        }
    }

}
class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>> &matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return vector<vector<int>>{};
        vector<vector<bool>> reach_pacific(matrix.size(), vector<bool>(matrix[0].size(), false));
        vector<vector<bool>> reach_atlantic(matrix.size(), vector<bool>(matrix[0].size(), false));
        for (int i = 0; i < matrix.size(); i++) {
            dfs(matrix, i, 0, reach_pacific);
            dfs(matrix, i, matrix[0].size() - 1, reach_atlantic);
        }
        for (int j = 0; j < matrix[0].size(); j++) {
            dfs(matrix, 0, j, reach_pacific);
            dfs(matrix, matrix.size() - 1, j, reach_atlantic);
        }
        vector<vector<int>> ans;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (reach_atlantic[i][j] && reach_pacific[i][j]) {
                    ans.push_back({i, j});
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<int>> &matrix, int x, int y, vector<vector<bool>> &reach) {
        if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size() || reach[x][y])
            return;
        reach[x][y] = true;
        for (auto direction:directions) {
            int new_x = x + direction.first;
            int new_y = y + direction.second;
            if (new_x >= 0 && new_x < matrix.size() && new_y >= 0 && new_y < matrix[0].size()) {
                if (matrix[new_x][new_y] >= matrix[x][y])
                    dfs(matrix, new_x, new_y, reach);
            }
        }
    }
};

133. 克隆图

给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。

示例:



输入:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释:
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
 

提示:

节点数介于 1 到 100 之间。
无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
必须将给定节点的拷贝作为对克隆图的引用返回。
package main.gongel_first;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
    }

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Onehundred_thirtyThree {
    /**
     * 深拷贝就是对于所有的指针成员,不能仅仅是赋值,还有重新分配空间
     */
    private Map<Node, Node> map;

    public Node cloneGraph(Node node) {
        map = new HashMap<>();
        return dfs(node);
    }

    public Node dfs(Node node) {
        if (!map.containsKey(node)) {//防止成环
            Node copy = new Node(node.val, new ArrayList<Node>());
            map.put(node, copy);
            for (Node neibor : node.neighbors) {
                copy.neighbors.add(dfs(neibor));
            }
        }
        return map.get(node);
    }
}
class Node {
public:
    int val;
    vector<Node *> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node *>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node *>();
    }

    Node(int _val, vector<Node *> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
//和138. 复制带随机指针的链表 相似
private:
    unordered_map<Node *, Node *> map;//存着节点和他自己的拷贝
public:
    Node *cloneGraph(Node *node) {
        if (node == nullptr)
            return nullptr;
        return dfs(node);
    }

    Node *dfs(Node *node) {
        if (map.count(node) == 0) {
            Node *copy = new Node(node->val, vector<Node *>());
            map[node] = copy;
            for (Node *neighbor:node->neighbors) {
                copy->neighbors.push_back(dfs(neighbor));
            }
        }
        return map[node];
    }
};

473. 火柴拼正方形

还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。

输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形,每边两根火柴。
示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。
注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。
package gongel_first;

public class Fourhundred_seventyThree {
    /**
     * DFS自己去寻找最优解
     * 和494题相同
     */
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length == 0)
            return false;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (sum / 4 * 4 != sum)
            return false;
        //每个边的长度初始化为0
        return dfs(0, nums, 0, 0, 0, 0, sum / 4);
    }

    private boolean dfs(int i, int[] nums, int up, int down, int left, int right, int len) {
        if (i == nums.length)
            return up == len && down == len && left == len && right == len;
        if (up > len || down > len || left > len || right > len)
            return false;
        //对每个边进行加和,一旦满足则返回
        return dfs(i + 1, nums, up + nums[i], down, left, right, len) || dfs(i + 1, nums, up, down + nums[i], left, right, len) || dfs(i + 1, nums, up, down, left + nums[i], right, len) || dfs(i + 1, nums, up, down, left, right + nums[i], len);
    }
}
class Solution {
public:
    bool makesquare(vector<int> &nums) {
        if (nums.empty())
            return false;
        //剪枝: 大的先放,减少比较次数
        sort(nums.rbegin(), nums.rend());
        int sum = 0;
        for (auto num:nums)
            sum += num;
        if (sum % 4 != 0)
            return false;
        int len = sum / 4;
        return helper(nums, 0, 0, 0, 0, 0, len);

    }

    bool helper(vector<int> &nums, int index, int left, int right, int up, int down, int len) {
        if (index > nums.size() || left > len || right > len || up > len || down > len)
            return false;
        if (index == nums.size()) {
            if (left == len && right == len && up == len && down == len)
                return true;
            else
                return false;
        }
        //剪枝: 提前判断长度
        return (left + nums[index] <= len && helper(nums, index + 1, left + nums[index], right, up, down, len)) ||
               (right + nums[index] <= len && helper(nums, index + 1, left, right + nums[index], up, down, len)) ||
               (up + nums[index] <= len && helper(nums, index + 1, left, right, up + nums[index], down, len)) ||
               (down + nums[index] <= len && helper(nums, index + 1, left, right, up, down + nums[index], len));
    }
};

 

494. 目标和

给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
注意:

数组的长度不会超过20,并且数组中的值全为正数。
初始的数组的和不会超过1000。
保证返回的最终结果为32位整数。
package gongel_first;

public class Fourhundred_ninetyFour {
    public int findTargetSumWays(int[] nums, int S) {
        /**
         * 法一:dp
         sum(P) 前面符号为加号的集合;sum(N) 前面符号为减号的集合
         * 所以题目可以转化为
         * sum(P) - sum(N) = target
         * => sum(nums) + sum(P) - sum(N) = target + sum(nums)
         * => 2 * sum(P) = target + sum(nums)
         * => sum(P) = (target + sum(nums)) / 2
         * 因此题目转化为01背包,也就是能组合成容量为sum(P)的方式有多少种*/
        if (nums == null || nums.length == 0)
            return 0;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (sum < S || (((S) + sum) & 1) == 1)//target + sum(nums)必须为偶数
            return 0;
        int w = (S + sum) / 2;
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = w; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[w];
    }

    /**
     * 法二:DFS,和473题相同
     */
    public int findTargetSumWays2(int[] nums, int S) {
        if (nums == null || nums.length == 0)
            return 0;
        return dfs(nums, 0, 0, S);
    }

    private int dfs(int[] nums, int index, int sum, int target) {
        if (index == nums.length)
            return target == sum ? 1 : 0;//找到则最终结果加1
        return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);
    }
}
class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int S) {
        if (nums.empty())
            return 0;
        return dfs(nums, 0, 0, S);
    }

    int dfs(vector<int> &nums, int index, int sum, int target) {
        if (index == nums.size())
            return sum == target ? 1 : 0;
        return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);
    }
};