README.md

Coding For Master And Offer

leetcode

number	title
001	Two Sum
002	Add Two Numbers
003	Longest Substring Without Repeating Characters
004	Median of Two Sorted Arrays
005	Longest Palindromic Substring
006	ZigZag Conversion
007	Reverse Integer
009	Palindrome Number
011	Container With Most Water
012	Integer to Roman
013	Roman to Integer
014	Longest Common Prefix
015	Three Sum
017	Letter Combinations of A Phone Number
019	Remove Nth Node From End of List
020	Valid Parentheses
021	Merge Two Sorted Lists
022	Generate Parentheses
026	Remove Duplicates from Sorted Array
027	Remove Element
031	Next Permutation
033	Search in Rotated Sorted Array
034	Search for a Range
035	Search Insert Position
039	Combination Sum
043	Multiply Strings
049	Group Anagrams
053	Maximum Subarray
058	Length of Last Word
062	Unique Paths
063	Unique Paths II
064	Minimum Path Sum
066	Plus One
067	Add Binary
070	Climbing Stairs
072	Edit Distance
074	Search a 2D Matrix
088	Merge Sorted Array
093	Restore IP Addresses
096	Unique Binary Search Trees
097	Interleaving String
100	Same Tree
105	Construct Binary Tree from Preorder and Inorder Traversal
115	Distinct Subsequences
118	Pascal's Triangle
119	Pascal's Triangle II
120	Triangle
121	Best Time to Buy and Sell Stock
122	Best Time to Buy and Sell Stock II
125	ValidPalindrome
128	Longest Consecutive Sequence
139	Word Break
167	Two Sum II - Input array is sorted
169	Majority Element
189	Rotate Array
191	Number of 1 Bits
215	Kth Largest Element in An Array
217	Contains Duplicate
219	Contains Duplicate II
231	Pow of Two
240	Search a 2D Matrix II
258	Add Digits
322	Coin Change
338	Counting Bits
413	Arithmetic Slices
687	Longest Univalue Path
746	Min Cost Climbing Stairs

常见题型总结

动态规划

• 最长公共子串

// 子串必须连续
public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        int dp[][] = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (ans < dp[i][j]) {
                    ans = dp[i][j];
                }
            }
        }
        return ans;
    }
}

• 最长公共子序列

// 子序列不必连续
public class LongestSequence {
    public int findLCS(String A, int n, String B, int m) {
        int dp[][] = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[n][m];
    }
}

• 爬楼梯

// 每次只能爬一阶或两阶，问爬上n阶有多少种方法？
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

• 矩形路径数

// 从矩形左上角到右下角的不同路径数
class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

• 编辑步数

// 字符串A经过插入，删除，修改三种操作变为字符串B的步骤数
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.equals(word2)) {
            return 0;
        }
        if (word1.length() == 0 || word2.length() == 0) {
            return Math.max(word1.length(), word2.length());
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        int i, j;
        // 初始化，有一个单词长度为0时，则需要采取进行另一个单词的长度次操作
        for (i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;
        }
        for (i = 1; i <= word1.length(); i++) {
            for (j = 1; j <= word2.length(); j++) {
                // 刚好word1[i] == word2[j]时，下标从0开始，但是dp数组从1开始，dp[0][0]表示空串
                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], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    // 如果不等，可以通过修改或者删除最后一个字符，增加一次操作
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

• 找零问题

public class GetMoney {
    public int countWays(int[] changes, int n, int x) {
        //抄袭的代码
        int[] dp = new int[x + 1];
        dp[0] = 1;
        for (int change : changes) {
            for (int i = 0; i + change <= x; i++) {
                dp[i + change] += dp[i];
            }
        }
        return dp[x];
    }
}