算法刷题篇

图论算法

专题1：深度优先遍历

例题1：二叉树中的最大路径和（124）

class Solution {
    private int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxWithRoot(root);
        return res;
    }
    private int maxWithRoot(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = Math.max(maxWithRoot(root.left),0);
        int right = Math.max(maxWithRoot(root.right),0);
        res = Math.max(res, left + right + root.val);
        return root.val + Math.max(left, right);
    }
}

例题2：求根到叶子节点数字之和（129）

class Solution {
    private int res = 0;
    public int sumNumbers(TreeNode root) {
        if(root == null){
            return 0;
        }
        sum(root, 0);
        return res;
    }
    private void sum(TreeNode root, int cur){
        if(root.left == null && root.right == null){
            res += 10 * cur + root.val;
        }
        if(root.left != null){
            sum(root.left, 10 * cur + root.val);
        }
        if(root.right != null){
            sum(root.right, 10 * cur + root.val);
        }
    }
}

专题2：广度优先遍历

例题1：二进制矩阵中的最短路径（1091）

class Solution {
    class Point{
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public int shortestPathBinaryMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (grid[0][0] == 1 || grid[m-1][n-1] == 1)
            return -1;
        int[][] dir = {{1,-1},{1,0},{1,1},{0,-1},{0,1},{-1,-1},{-1,0},{-1,1}};
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0));
        grid[0][0] = 1;
        int distance = 0;
        while (!queue.isEmpty()){
            distance ++;
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                Point point = queue.poll();
                int x = point.x;
                int y = point.y;
                if (x == m - 1 && y == n - 1)
                    return distance;
                for (int i = 0; i < 8; i++) {
                    int newX = x + dir[i][0];
                    int newY = y + dir[i][1];
                    if (newX < 0 || newY < 0 || newX >= n || newY >= n)
                        continue;
                    if(grid[newX][newY] == 1)
                        continue;
                    queue.add(new Point(newX, newY));
                    grid[newX][newY] = 1;
                }
            }
        }
        return -1;
    }
}

例题2：网格中的最短路径(1293)

class Solution {
    class Point{
        int x;
        int y;
        int z;
        public Point(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
        boolean[][][] visited = new boolean[m][n][k+1];
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0, 0));
        visited[0][0][0] = true;
        int distance = 0;
        while (!queue.isEmpty()){
            distance ++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point point = queue.poll();
                int x = point.x;
                int y = point.y;
                int z = point.z;
                visited[x][y][z] = true;
                if (x == m - 1 && y == n - 1)
                    return distance - 1;
                for (int j = 0; j < 4; j++) {
                    int newX = x + dir[j][0];
                    int newY = y + dir[j][1];
                    int newZ = z;
                    if (newX < 0 || newY < 0 || newX >= m || newY >= n)
                        continue;
                    if (visited[newX][newY][newZ])
                        continue;
                    if (grid[newX][newY] == 1){
                        if (z < k){
                            newZ  = z + 1;
                        }else{
                            continue;
                        }
                    }
                    if (!visited[newX][newY][newZ]){
                        visited[newX][newY][newZ] = true;
                        queue.add(new Point(newX, newY, newZ));
                    }
                }
            }
        }
        return -1;
    }
}

例题3：找树左下角的值（513）

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ret = root.val;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i ++) {
                TreeNode cur = queue.poll();
                if(i == 0)
                    ret = cur.val;
                if(cur.left != null)
                    queue.add(cur.left);
                if(cur.right != null)
                    queue.add(cur.right);
            }
        }
        return ret;
    }
}

专题3：搜索

例题1：单词接龙（127）

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new TreeSet<>(wordList);
        Map<String, Integer> map = new HashMap<>();
        if (!dict.contains(endWord))
            return 0;
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        map.put(beginWord, 1);
        while (!queue.isEmpty()){
            int size = queue.size();
            String cur = queue.poll();
            for (int i = 0; i < cur.length(); i++) {
                StringBuilder sb = new StringBuilder(cur);
                for (char c = 'a'; c <= 'z' ; c++) {
                    sb.replace(i,i+1, c + "");
                    String next = sb.toString();
                    if (next.equals(endWord)){
                        return map.get(cur) + 1;
                    }
                    if (!map.containsKey(next) && dict.contains(next)) {
                        queue.add(next);
                        map.put(next, map.get(cur)+1);
                    }
                }
            }
        }
        return 0;
    }
}

专题4：最短路径

例题1：网络延迟时间(743)

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        int[] distance = new int[N+1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[K] = 0;
        for(int i=1;i<N;i++){
            for(int[] pair : times){
                int u = pair[0];
                int v = pair[1];
                int w = pair[2];
                if(distance[u] != Integer.MAX_VALUE && distance[u] + w < distance[v])
                    distance[v] = distance[u] + w;
            }
        }
        int ret = Arrays.stream(distance).skip(1).max().getAsInt();
        return ret == Integer.MAX_VALUE ? -1 :ret;  
    }
}

专题5：拓扑排序

例题1：最小高度树(310)

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        TreeSet<Integer>[] graph = new TreeSet[n];
        List<Integer> ret = new ArrayList<>();
        if (n == 1) {
            ret.add(0);
            return ret;
        }
        for (int i = 0; i < n; i++) {
            graph[i] = new TreeSet<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (graph[i].size() == 1){
                queue.add(i);
            }
        }
        while (n > 2) {
            int size = queue.size();
            n -= size;
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int adj : graph[cur]) {
                    graph[adj].remove(cur);
                    if (graph[adj].size() == 1) {
                        queue.add(adj);
                    }
                }
            }
        }
        ret.addAll(queue);
        return ret;
    }
}

动态规划算法

专题1：区间dp

例题1：编辑距离（72）

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符

class Solution{
    public int minDistance(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        int [][] dp = new int[n1+1][n2+1];
        for(int i=0;i<=n1;i++)
            dp[i][0] = i;
        for(int i=0;i<=n2;i++)
            dp[0][i] = i;
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
            }
        }
        return dp[n1][n2];        
    }
}

例题2：分割回文串II(132)

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean [][] dp = new boolean[n][n];
        int [] min = new int[n];
        for (int i = 0; i < n; i++) {
            min[i] = i;
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (j+1 > i-1 || dp[j+1][i-1])){
                    dp[j][i] = true;
                    min[i] = j == 0 ? 0 : Math.min(min[i], min[j-1] + 1);
                }
            }
        }
        return min[n-1];
    }
}

专题2：记忆化搜索

例题1：整数拆分（343）

class Solution {
    private int [] memo;
    public int integerBreak(int n) {
        memo = new int[n+1];
        Arrays.fill(memo, -1);
        return breakInteger(n);
    }
    private int breakInteger(int n){
        if(memo[n] != -1)
            return memo[n];
        int max = 0;
        for(int i = 1; i < n; i ++){
            max = Math.max(max,Math.max(i*(n-i), i*breakInteger(n-i)));
        }
        return memo[n] = max;    
    }
}

例题2：单词拆分II(140)

class Solution {
    private Map<Integer, List<String>> memo;
    public List<String> wordBreak(String s, List<String> wordDict) {
        memo = new HashMap<>();
        return wordBreak(s, wordDict, 0);
    }
    private List<String> wordBreak(String s, List<String> wordDict, int start) {
        if (memo.containsKey(start)){
            return memo.get(start);
        }
        LinkedList<String> res = new LinkedList<>();
        if (start == s.length()){
            res.add("");
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end))){
                List<String> list = wordBreak(s,wordDict, end);
                for (String l : list) {
                    res.add(s.substring(start, end) + (l.equals("") ? "" : " ") + l);
                }
            }
        }
        memo.put(start, res);
        return res;
    }
}

专题3：经典算法剖析

例题1：最长上升子序列（1143）

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int dp[][] = new int[m+1][n+1];
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                dp[i][j] = text1.charAt(i-1)==text2.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j],dp[i][j-1]);
        return dp[m][n];
    }
}

专题4：状态转移方程

例题1：单词拆分(139)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean []dp = new boolean[n];
        dp[0] = true;
        //前闭后开
        for(int i=0; i < n; i++){
            for(int j=0; j < i; j++){
                if(dp[j] && wordDict.contains(s.substring(j+1, i+1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n-1];
    }
}

例题2：乘积最大子序列(152)

class Solution {
    public int maxProduct(int[] nums) {
        int min = 1;
        int max = 1;
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] < 0){
                int temp = max;
                max = min;
                min = temp;
            }
            max = Math.max(nums[i], max * nums[i]);
            min = Math.min(nums[i], min * nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}

例题3：解码方法(91)

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n == 0 || s.charAt(0) == '0')
            return 0;
        int []dp = new int[n+1];
        dp[0] = 1;
        for(int i=1;i<=n;i++){
            if(s.charAt(i-1)!='0')
                dp[i] = dp[i-1];
            if(i > 1 && s.charAt(i-2) == '1' )
                dp[i] += dp[i-2];
            if(i > 1 && s.charAt(i-2) == '2' && s.charAt(i-1) <= '6')
                dp[i] += dp[i-2];
        }
        return dp[n];
    }
}

递归与回溯算法

专题1：排列问题

例题1：全排列（46）

给定一个没有重复数字的序列，返回其所有可能的全排列。

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
        permuteDFS(num, 0, res);
        return res;
    }
    void permuteDFS(vector<int> &num, int start, vector<vector<int> > &res) {
        if (start >= num.size()) res.push_back(num);
        for (int i = start; i < num.size(); ++i) {
            swap(num[start], num[i]);
            permuteDFS(num, start + 1, res);
            swap(num[start], num[i]);
        }
    }
};

class Solution {
    private ArrayList<List<Integer>> res;
    private boolean[]visited;
    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        visited = new boolean[nums.length];
        dfs(nums, new ArrayList<Integer>());
        return res;
    }
    private void dfs(int[] nums,ArrayList<Integer> temp){
        if(temp.size() == nums.length){
            res.add(new ArrayList(temp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!visited[i]){
                visited[i] = true;
                temp.add(nums[i]);
                dfs(nums,temp);
                visited[i] = false;
                temp.remove(temp.size()-1);
            }
        }
    }
}

例题2：全排列2（47）

给定一个可包含重复数字的序列，返回所有不重复的全排列。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        visited=vector<bool>(nums.size(),false);
        vector<int>vec;
        getPermutation(nums,vec);
        return res;
    }
private:
    vector<vector<int>>res;
    vector<bool>visited;
    void getPermutation(vector<int>&nums,vector<int>&vec){
        if(vec.size()==nums.size()){
            res.push_back(vec);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(!visited[i]){
                if(i>0&&nums[i]==nums[i-1]&&!visited[i-1])
                    continue;
                visited[i]=true;
                vec.push_back(nums[i]);
                getPermutation(nums,vec);
                visited[i]=false;
                vec.pop_back();
            }
        }
        return;
    }
};

class Solution {
    private ArrayList<List<Integer>> res;
    private boolean []used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        res = new ArrayList<>();
        used = new boolean[nums.length];
        dfs(nums, new ArrayList<Integer>());
        return res;
    }
    public void dfs(int []nums, ArrayList<Integer>temp){
        if(temp.size() == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!used[i]){
                if(i>0 && nums[i]==nums[i-1]&&!used[i-1])
                    continue;
                used[i] = true;
                temp.add(nums[i]);
                dfs(nums, temp);
                used[i] = false;
                temp.remove(temp.size()-1);
            }
        }
    }
}

专题2：回溯法

例题1：分割回文串（131）

class Solution {
    private ArrayList<List<String>> res;
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        part(s,0, new ArrayList<>());
        return res;
    }
    public boolean isHuiWen(String s){
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    public void part(String s, int i, ArrayList<String> arr){
        if(i == s.length()){
            res.add(new ArrayList<String>(arr));
        }
        for(int j = i; j < s.length(); j++){
            if(isHuiWen(s.substring(i,j+1))){
                arr.add(s.substring(i,j+1));
                part(s, j+1, arr);
                arr.remove(arr.size()-1);
            }
        }
    }
}

分治算法

专题1：归并排序

例题1：翻转对(493)

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。

class Solution {
    private int []temp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        temp = new int[n];
        return mergeCount(nums, 0, n-1);
    }
    private int mergeCount(int []nums, int begin, int end){
        if(begin >= end)
            return 0;
        int mid = begin + end >> 1;
        int leftCnt = mergeCount(nums, begin, mid);
        int rightCnt = mergeCount(nums, mid+1, end);
        int midCnt = 0;
        for(int i = begin; i <= end; i++)
            temp[i] = nums[i];    
        int i = begin, j = mid+1;
        while(i <= mid && j <= end){
            if((long)nums[i] > (long)2 * nums[j]){
                midCnt += mid - i + 1;
                j++;
            }else{
                i++;
            }
        }
        i = begin;
        j = mid+1;
        for(int k = begin; k <= end; k++){
            if(i > mid){
                nums[k] = temp[j++];
            }else if(j > end){
                nums[k] = temp[i++];
            }else if(temp[i] < temp[j]){
                nums[k] = temp[i++];
            }else{
                nums[k] = temp[j++];
            }
        }
        return leftCnt + rightCnt + midCnt;
    }
}

例题2：计算右侧小于当前元素的个数(315)

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

class Solution {
    private int index[];
    private int temp[];
    private int counter[];
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        temp = new int[len];
        counter = new int[len];
        index = new int[len];
        for (int i = 0; i < len; i++) {
            index[i] = i;
        }
        mergeAndCountSmaller(nums, 0, len - 1);
        for (int i = 0; i < len; i++) {
            res.add(counter[i]);
        }
        return res;
    }
    private void mergeAndCountSmaller(int[] nums, int begin, int end) {
        if (begin >= end)
            return;
        int mid = begin + end >> 1;
        mergeAndCountSmaller(nums, begin, mid);
        mergeAndCountSmaller(nums, mid + 1, end);
        if (nums[index[mid]] > nums[index[mid + 1]]) {
            merge(nums, begin, mid, end);
        }
    }

    private void merge(int[] nums, int begin, int mid, int end) {
        for (int i = begin; i <= end; i++) {
            temp[i] = index[i];
        }
        int i = begin, j = mid + 1;
        for (int k = begin; k <= end; k++) {
            if (i > mid){
                index[k] = temp[j++];
            }else if(j > end){
                index[k] = temp[i++];
                counter[index[k]] += end - mid;
            }else if (nums[temp[i]] <= nums[temp[j]]){
                index[k] = temp[i++];
                counter[index[k]] += j - mid - 1;
            }else{
                index[k] = temp[j++];
            }
        }
    }
}

贪心算法

例题1：无重叠区间(435)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        Arrays.sort(intervals, (a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
        int res = 1;
        int pre = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[pre][1]){
                res ++;
                pre = i;
            }
        }
        return intervals.length - res;
    }
}

堆

例题1：接雨水II(407)

class Solution {
    class Node implements Comparable<Node>{
        int height;
        int x;
        int y;
        public Node(int height, int x, int y) {
            this.height = height;
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Node node) {
            return height - node.height;
        }
    }
    public int trapRainWater(int[][] heightMap) {
        int ret = 0;
        int m = heightMap.length;
        if (m == 0)
            return 0;
        int n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dir = {{1,0},{-1,0},{0,-1},{0,1}};
        Queue<Node> queue = new PriorityQueue<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1){
                    visited[i][j] = true;
                    queue.add(new Node(heightMap[i][j], i, j));
                }
            }
        }
        int maxHeight = Integer.MIN_VALUE;
        while (!queue.isEmpty()){
            Node node = queue.poll();
            int h = node.height;
            int x = node.x;
            int y = node.y;
            maxHeight = Math.max(h,maxHeight);
            for (int i = 0; i < 4; i++) {
                int newX = x + dir[i][0];
                int newY = y + dir[i][1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]){
                    if (heightMap[newX][newY] < maxHeight)
                        ret += maxHeight - heightMap[newX][newY];
                    queue.add(new Node(heightMap[newX][newY], newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }
        return ret;
    }
}