经典算法题

1143.最长公共子序列

视频教学：https://www.bilibili.com/video/BV14A411v7mP

基本思路是转化为二维数组

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n=text1.length(),m=text2.length();
        // text1=" "+text1;text2=" "+text2;//给字符串首部加空格，方便计算
        char[] s1=text1.toCharArray(),s2=text2.toCharArray();//字符串转字符数组
        int[][] f = new int[n+1][m+1];//动态规划用二维数组辅助，首部初始化加0故初始化长度+1

        // 二维数组初始化
        // for(int i=0;i<n+1;i++) f[i][0]=0;
        // for(int j=0;j<m+1;j++) f[0][j]=0;

        //模拟二维数组算解
        for(int i=1;i<n+1;i++){
            for(int j=1;j<m+1;j++){
            /*
             *if(s1[i]==s2[j])首部加空格则直接i=j，不用转换，直接类比二维数组比较直接
             *但数组这种不好插入的还得用偏移
             */
                if(s1[i-1] == s2[j-1]) f[i][j]=f[i-1][j-1]+1;
                else f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
            }
        }
        return f[n][m];
    }
}

208.实现Trie（构造前缀树）

参考1：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/

参考2：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-we-esm9/

前缀树思想还是好理解的，注意看怎么实现，它的结点构造是包含一个结点类型的数组，这是关键，我一开始没搞明白这个数组，所以有几个地方卡住了（next.node[ch] = new TrieNode();就是这句！），建议插入和查两个功能对比着看好理解，我看插入还有点没想明白，看到查找就懂了。

class Trie {
    class TrieNode{
        boolean isEnd;//字符串是否匹配结束
        TrieNode[] node = new TrieNode[26];//范围是26个字母，结点属性是数组
    }
    TrieNode root;
	
    //结构初始化
    public Trie() {
        root = new TrieNode();//根结点是一个新的treenode
    }
    
    //插入字符串
    public void insert(String word) {
        TrieNode next = root;//头结点
        //字符串逐位匹配，charAt()
        for(int i=0;i<word.length();i++){
            int ch = word.charAt(i)-'a';//字符ascll码计算位置，如z-a=25，这便是z在数组的下标
            /*
             *对应next节点数组属性为空，则在对应数组下标处新建结点，
             *这里是和查找对应的，不理解去看看查找怎么写的
             */
            if(next.node[ch] == null) 
                next.node[ch] = new TrieNode();
            next=next.node[ch];//更新next节点，继续匹配字符串
        }
        next.isEnd=true;//完成匹配则最后结点属性为结束
    }
    
    //查询字符串
    public boolean search(String word) {
        TrieNode next = root;
        for(int i=0;i<word.length();i++){
            int ch = word.charAt(i)-'a';
            /*
             *ch是一个相对字母顺序的值，初始化结点数组属性是全null，只有插入过新结点的才会不为空
             *也就是说你现在在查询的字符串的对应结点数组为空，说明它没插入过，肯定找不到返回F 
             */
            if(next.node[ch] == null) return false;
            next=next.node[ch];
        }
        /*
         *字符串匹配完后，检查isEnd属性，isEnd=T代表插入的时候这个结点是一个结束
         *isEnd=F代表这不是一个结束处，可能是其他字符的一部分和你这个字符相同罢了。
         */
        return next.isEnd;
    }
    
    //返回是否有字符串前缀符合传入的字符串，这里就比较好理解了，和查询只有在返回值处有不同
    public boolean startsWith(String prefix) {
        TrieNode next = root;
        for(int i=0;i<prefix.length();i++){
            int ch=prefix.charAt(i)-'a';
            if(next.node[ch] == null) return false;
            next=next.node[ch];
        }
        return true; 
    }
}

5773.插入后的最大值

5773.插入后的最大值。周赛碰到的，自己写的时候考虑不周全，首尾添加的情况老是出问题，学习一下别人的写法。

题目：https://leetcode-cn.com/problems/maximum-value-after-insertion/

class Solution {
    public String maxValue(String n, int x) {
        StringBuilder sb = new StringBuilder();
        /*
         *找对应的插入位置，负数要绝对值更小，整数要绝对值更大
         *substring返回截取字符串，用该方法拼接
         *不符合上述条件，直接插入串尾
         */
        if(n.charAt(0) == '-'){
            for(int i=1;i<n.length();i++){
                //字符'0'ascii码为48，-48算出相对的int型
                if(n.charAt(i) - 48 > x){
                    sb.append(n.substring(0,i)).append(x).append(n.substring(i));
                    return sb.toString();
                }
            }
        }else {
            for(int i=0;i<n.length();i++){
                if(x > n.charAt(i) - 48){
                    //substring(0,0)返回空字符串，也就是x可插入首部
                    sb.append(n.substring(0,i)).append(x).append(n.substring(i));
                    return sb.toString();
                }
            }
        }
        return n + x;
    }
}

15.三数之和

题目：https://leetcode-cn.com/problems/3sum/

这道三数之和也有K神的题解我是没想到的，然后就按老习惯看了k神题解，其中左右指针分别设为两端就很巧妙，再根据和的大小，动态改变左右指针向中间靠拢，提高了算法的效率，我一开始做都是从左到右的双指针。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for(int a = 0; a < nums.length - 2; a++){
            if(nums[a] > 0) return ans;
            // 相同数跳过，就是与前一位相同就跳过该相同数
            // a > 0是为了a - 1不越界
            if(a > 0 && nums[a] == nums[a-1]) continue;
            // 这里初始化很关键，b、c双指针处于数组两侧
            // 然后根据大小向中间靠拢，不是单向遍历，效率更高
            int b = a + 1, c = nums.length - 1;
            while(b < c){
                int sum = nums[a] + nums[b] + nums[c];
                // sum < 0，代表和较小，很明显b右移使和变大
                // 且要跳过一切与当前b相等的值
                if(sum < 0){
                    while(b < c && nums[b] == nums[++b]);
                }
                // sum > 0，代表和较大，c左移使和变小
                // 且要跳过所有与c相等的数
                else if (sum > 0){
                    while(b < c && nums[c] == nums[--c]);
                }else {//和为0，增加一种结果
                    List<Integer> temp= new ArrayList<>();
                    temp.add(nums[a]);
                    temp.add(nums[b]);
                    temp.add(nums[c]);
                    ans.add(temp);
                    // 同理跳过所有与b、c相等的结果集
                    while(b < c && nums[b] == nums[++b]);
                    while(b < c && nums[c] == nums[--c]);
                }
            }
        }
        return ans;
    }   
}

5.最长回文子串

题目：https://leetcode-cn.com/problems/longest-palindromic-substring/

一般的算法都需要O(n^2)，我们就学习一下动态规划。

这里转移方程是：

• 字符串左右边界不等，一定不是回文串，记false
• 字符串左右相等，若其长度<=3说明一定是回文串，记true
• 字符串左右相等且长度>3，根据其内部子串是否为回文串来判断

然后如果现在的子串是回文串且长度最大就更新最长回文子串的判断长度与起始位，方便后续截取字符串进行输出。

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        // 单个字符或空串，s本身即最长回文子串
        if(length < 2) return s;
        //最长回文串的长度，以及起始位，方便截取字符串
        int max = 1, left = 0;
        boolean[][] dp = new boolean[length][length];
        // 初始化，单个字符一定是回文子串
        for(int i = 0; i < length; i++) dp[i][i] = true;

        char[] str = s.toCharArray();
        //len即当前子串长度，l即子串的左边界
        for(int len = 2; len <= length; len++){
            for(int l = 0; l < length; l++){
                int r = len + l - 1;
                // 计算子串右边界r，r越界退出当前长度子串的遍历
                if(r >= length) break;
                // 子串左右两侧不等，说明当前子串不是回文串
                if(str[l] != str[r]) dp[l][r] = false;
                // 当前子串长度左右两侧相等且长度<=3
                // 例如aba、aa，说明当前子串是一个回文串
                else if(r - l + 1 <= 3) dp[l][r] = true;
                // 左右两侧相等，且长度大于3的子串，向内收缩
                // 查看其内部是不是回文串，因为回文串内部一定是回文串
                else dp[l][r] = dp[l+1][r-1];
                // 当前子串是回文串且长度大于最大值，更新最长回文子串
                if(dp[l][r] && r - l + 1 > max){
                    max = r - l + 1;
                    left = l;
                }
            }
        }
        // 按最长回文子串的信息进行截取，左闭右开对应l~r+1
        return s.substring(left, left + max);
    }
}

19.删除链表的倒数第N个结点（快慢指针）

题目：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

经典快慢指针，一开始没思路看到评论说快慢就想到解法了，知道快慢指针后就很好做了，一次遍历即可得到答案。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //初始化慢指针l、快指针r，l即头结点，在head前面
        ListNode l = new ListNode(0), r = head;
        l.next = head;
        //快慢指针空出空间
        for(int i = n; n > 1; n--){
            r = r.next;
        }
        //快指针走到链表尾，此时慢指针处于n-1处
        while(r.next != null){
            l = l.next;
            r = r.next;
        }
        //如果倒数n是head，直接返回head.next
        //否则跳过倒数第n结点，然后返回head
        if(l.next == head) return head.next;
        l.next = l.next.next;
        return head;
    }
}

3.无重复字符的最长子串

题目：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

典型的滑动窗口题目，我们注意重复值和左右边界的关系即可解题。当加入字符在窗口中没有重复值时再加入。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <=1) return s.length();
        Set<Character> set = new HashSet<>();
        int l = 0, max = 0;
        for(int r = 0; r < s.length(); r++){
            //判断要加入的字符在窗口是否重复
            //若重复，则缩小左边界直到没有重复值
            while( set.contains(s.charAt(r)) ){
                set.remove(s.charAt(l++));
            }
            //窗口和加入字符无重复，加入字符，记录长度
            set.add(s.charAt(r));
            max = Math.max(r - l + 1, max);
        }
        return max;
    }
}

64.最小路径和

题目：https://leetcode-cn.com/problems/minimum-path-sum/

刚看到题就知道普通办法行不通，然后评论提到动态规划马上就懂了，就是一个普通的动态规划题目，比较简单。注意m是行、n是列，也就是m是竖着的长度，n是横着的长度，我老是搞混，是说怎么会数组越界😂

class Solution {
    public int minPathSum(int[][] grid) {
        //对应题目的m x n，m是行，n是列
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        //分别初始化行、列的首位
        for(int i = 1; i < m; i++)
            dp[i][0] = dp[i-1][0] + grid[i][0];
        for(int i = 1; i < n; i++)
            dp[0][i] = dp[0][i-1] + grid[0][i];
        //dp得到矩阵内的各个最小值
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

300.最长递增子序列

题目：https://leetcode-cn.com/problems/longest-increasing-subsequence/

挺好理解的，但不是最优解法，今日摸鱼了，注意dp[n]的意义，即数组0~n长度中最长递增子序列的长度。

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        // dp代表当前位数的最长递增子序列长度
        int[] dp = new int[nums.length];
        int ans = 0;
        // 先初始化全部位的递增子序列max为1
        Arrays.fill(dp, 1);
        // 遍历一次数组，每次遍历到一个位数，就把该位数前的递增子序列一起比较
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                // 当前位数 > 遍历位，说明递增，则更新最大值为遍历位的长度+1 
                if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);                
            }
            // 每走过一个位数，就判断当前位数的递增子序列是否是max
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

2.两数相加

题目：https://leetcode-cn.com/problems/add-two-numbers/

一开始还想用辅助栈来把两个链表的数取出来相加，随后再存入到新链表，观察了一会发现可以直接对两个原链表操作，这样效率肯定更高，没想到直接做出了标准答案，看来最近的刷题还是有用的。

当然这里可以发现代码没有完全实现复用，评论区有优化版本，不过我的思路是正确的，让代码进一步优化还要学习。

class Solution {
    ListNode head = new ListNode(0);// 新链表头结点
    ListNode ans = head;// 记录头结点，方便返回结果
    int num, ten = 0;// 两个原链表的相加和，相加和的十位数
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 两个链表逐位相加得到num，并记录到新链表
        // 新链表结点值等于num的个位数
        // 记录两个链表相加是否进位，也就是num的十位数
        // 新链表和两个原链表移动到下一位
        while(l1 != null && l2 != null){
            num = l1.val + l2.val + ten;
            head.next = new ListNode(num % 10);
            ten = num / 10;
            head = head.next;
            l1 = l1.next;
            l2 = l2.next;
        }

        // 两个原链表可能长度不相同
        // 此时一个链表走完。另一个链表没走完
        loop(l1);
        loop(l2);

        // 如果最后两个原链表相加和进位了
        // 则把进位的1要补到新链表
        if(ten != 0){
            head.next = new ListNode(ten);
            head = head.next;
        }
        // 返回新链表的第一个结点
        return ans.next;
    }

    // 和两个原链表的操作相似，走完当前剩下的链表
    void loop(ListNode node){
        while(node != null){
            num = node.val + ten;
            head.next = new ListNode(num % 10);
            ten = num / 10;
            head = head.next;
            node = node.next;
        }
    }
}

141.环形链表

题目：https://leetcode-cn.com/problems/linked-list-cycle/

简单做法是走过一个链表结点就加入Set，若加入失败则说明有环。

复杂一点效率高就是使用快慢指针，快慢指针重合就说明有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 环形链表最少两个结点，使用快慢指针判断
        if(head == null || head.next == null ) return false;
        ListNode quick = head.next;
        ListNode slow = head;
        // 当快慢指针没有重合，说明无环
        while(quick != slow){
            // 当前快指针或其下一个为空，则不存在quick.next.next
            // 且快慢指针没有重合，说明链表走完了，没有环
            if(quick == null || quick.next == null) return false;
            // 快指针走快一步，形成差值，此时快慢指针重合则说明有环
            quick = quick.next.next;
            slow = slow.next;
        }
        // 快慢指针重合说明有环
        return true;
    }
}

62.不同路径

题目：https://leetcode-cn.com/problems/unique-paths/

经典动态规划，初始化两条边然后dp即可。

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for(int i = 1; i < m; i++)
            dp[i][0] = dp[i - 1][0];
        for(int i = 1; i < n; i++)
            dp[0][i] = dp[0][i - 1];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1]; 
    }
}

91.解码方法

题目：https://leetcode-cn.com/problems/decode-ways/

其实这题是一个常规动态规划，理清楚思路后不难理解，笔试的时候死活没想到转移方程，新加入字符的编码次数与自身和前一位的组合相关，通过这个得到转移方程即可。

class Solution {
    public int numDecodings(String s) {
        // 字符串首部加空格方便原字符串第二位计算i-2的值
        s = " " + s;
        int len = s.length();
        int[] dp = new int[len];
        // 空字串，对应初始化的空格，增加这一位时为了方便计算第二位
        dp[0] = 1;
        // 遍历字符串，依照逐个字符进行动态规划计算结果
        for(int i = 1; i < len; i++){
            // 新增的字符
            int one = s.charAt(i);
            // 新增字符与前一位进行组合后的字符
            int two = (s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0';
            // 当前新增字符只要不是0，那么就继承上一位的编译，即无组合编译
            if(one >= '1' && one <= '9') dp[i] = dp[i - 1];
            // 若当前字符可以与上一位进行组合，那么把最后两位看成一个整体
            // 然后当前字符可翻译的次数就要加上倒数第二位的
            // 因为倒数第一位和当前位已经看作一个整体了
            if(two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }
        return dp[len - 1];
    }
}

202.快乐数

题目：https://leetcode-cn.com/problems/happy-number/

确实是简单题，我们只要发现当前数存在于一个循环中，那么他一定不是快乐数，然后若当前数等于1就是快乐数，使用递归轻松解决。判断循环有多种方法，这里我是将数存放到set中，添加失败就说明有循环。

class Solution {
    Set<Integer> set = new HashSet<>();
    public boolean isHappy(int n) {
        int sum = 0;
        int cur = 0;    
        while(n != 0){
            cur = n % 10;
            sum += cur * cur;
            n /= 10;
        }
        if(sum == 1) return true;
        if(!set.add(sum)) return false;
        return isHappy(sum);
    }
}

42.接雨水

题目：https://leetcode-cn.com/problems/trapping-rain-water/

不要看到困难就怕了。其实用动态规划做很好想明白的，如果我们只是单一的接雨水，也就是有递减就算接水，那么题目就很简单。但是这里需要考虑一个区间问题，也就是接雨水处于一个区间内，需要把雨水包住，形成一个盆地，就是要先递减后递增的区间，比如看题目的示例，虽然最大高度是3，但没有其他柱子可以与3形成盆地接水，我们最终用来判断接水的是较小的最大高度2。

总结一下就是判断一个位置接雨水的量需要知道其左右较小的最大高度，通过这个较小的最大高度进行计算，那么我们可以分别计算从左往右和从右往左两个高度递增的数组并记录。最后计算接雨水结果时，取左右两个递增数组中当前位较小高度进行计算。

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        
        // 记录从左往右的高度递增数组
        int[] left_increase = new int[len];
        left_increase[0] = height[0];
        for(int i = 1; i < len; i++)
            left_increase[i] = Math.max(left_increase[i - 1], height[i]);

        // 记录从右往左的高度递增数组
        int[] right_increase = new int[len];
        right_increase[len - 1] = height[len - 1];
        for(int i = len - 2; i >= 0; i--)
            right_increase[i] = Math.max(right_increase[i + 1], height[i]);

        // 每个位置都有左右高度，若当前位比较小的左右高度还小
        // 说明左右高度形成了盆地可以接水
        int ans = 0;
        for(int i = 0; i < len; i++)
            ans += Math.min(left_increase[i], right_increase[i]) - height[i];
        return ans;
    }
}

​