输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

双指针合并，不如找两串珠子自己比划比划

这个问题之前给人家形象的比喻讲解过。

1. 你拿两串珠子，分别按照题意标上有序递增的数字
2. 另外你再拿一根线，把这两串珠子合并成一串，这时候你会怎么做呢？
3. 当然是两个原串头上挑小的串起来呀！哪个小串哪个，另外一串没有了就整个串上就完了

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}

如果本题能够很好理解了不妨再去试试23. 合并K个升序链表
题解JAVA 分治归并 其实挺简单的

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

JAVA 分治归并 其实挺简单的

1. 对于K个链表，可以两两合并（有点归并排序的意思）
2. 一次合并完了之后此时变成K/2个链表了，对剩下的链表继续两两合并
3. 最终全都合并到了一个链表里
4. 至于两个链表的合并过程，直接参考剑指Offer25题，比较简单算链表基本题了吧，我之前写的题解双指针合并，不如找两串珠子自己比划比划
5. 至于如何选择两两的过程可以简单设计下

//对应为k个链表在入参数组中的下标
1 [0,1],[2,3],[4,5],[6,7],[8]
2 [0,2],[4,6],[8]
4 [0,4],[8]
8 [0,8]

- 第一次 `[0,1],[2,3],[4,5],[6,7]`互相合并，结果留在第一个链表位置， `[8]`单独拉下了没关系先留着
- 第二次 `[0,2],[4,6]` 互相合并，结果存在0 , 4 位置，8继续留着，`[8]`没关系
- 第三次 再次合并`[0,4]`，`[8]`继续留着
- 最后一次合并`[0,8]`结束收工

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 1){
            return lists[0];
        }
        if (lists.length == 0){
            return null;
        }
        int dis = 1;
        while (dis < lists.length){
            //1 [0,1],[2,3],[4,5],[6,7],[8]
            //2 [0,2],[4,6],[8]
            //4 [0,4],[8]
            //8 [0,8]
            for (int i = 0; i + dis < lists.length; i += dis*2) {
                //合并两个有序链表  剑指Offer25题
                lists[i] = mergeTwoLists(lists[i],lists[i+dis]);
                lists[i+dis] = null;
            }
            dis *=2;
        }
        return lists[0];
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

示例 1：

输入：s = "owoztneoer"
输出："012"

示例 2：

输入：s = "fviefuro"
输出："45"

提示：

• 1 <= s.length <= 105
• s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
• s 保证是一个符合题目要求的字符串

class Solution {
    public String originalDigits(String s) {
        //0 zero
        //1 one
        //2 two
        //3 three
        //4 four
        //5 five
        //6 six
        //7 seven
        //8 eight
        //9 nine
        int[] charChount = new int[26];
        for (int i = 0; i < s.length(); i++) {
            charChount[s.charAt(i)-'a']++;
        }
        int[] arr = new int[10];
        arr[0] = charChount[25];
        arr[2] = charChount[22];
        arr[4] = charChount[20];
        arr[6] = charChount[23];
        arr[8] = charChount[6];

        arr[5] = charChount[5] - arr[4];
        arr[3] = charChount[7] - arr[8];
        arr[7] = charChount[18] - arr[6];
        arr[1] = charChount[14] - arr[0] - arr[2] - arr[4];

        arr[9] = charChount[8] - arr[5] - arr[6] - arr[8];

        char[] chars = new char[s.length()/3];
        int idx = -1;
        for (int i = 0; i < arr.length; i++) {
            while (--arr[i]>=0){
                chars[++idx] = (char)('0'+i);
            }
        }
        idx++;
        char[] ans = new char[idx];
        System.arraycopy(chars,0,ans,0,idx);
        return new String(ans);
    }
}

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

【动态规划】java 编辑距离

直接上图

动态规划的思想不做过多描述了。主要分析下这个过程。

以中间一步的标号35的格子的 ABCDE需要转换成BBAC为例

如下情况

1. 可以由已知的ABCD→BBAC的过程之前执行一次删除末位的字母E操作 （对应删除）
2. 可以由已知的ABCDE→BBA的过程之后再执行一次插入字母C的操作来达到 （对应插入）
3. 由ABCD→BBA的操作再执行一次修改操作，把E改为C来达到，如果字母相同则不需要修改 (对应修改)

代码

class Solution {
    public int minDistance(String word1, String word2) {
        int lenght1 = word1.length();
        int lenght2 = word2.length();
        int[][] dp = new int[lenght1+1][lenght2+1];
        for (int i = 0; i <= lenght1 || i <= lenght2; i++) {
            if (i <= lenght2){
                dp[0][i] = i;
            }
            if (i <= lenght1){
                dp[i][0] = i;
            }
        }
        for (int row = 1; row <= lenght1; row++) {
            for (int col = 1; col <= lenght2; col++) {
                dp[row][col] = Math.min(
                        dp[row-1][col-1] + (word2.charAt(col-1) == word1.charAt(row-1)?0:1) ,
                        Math.min(dp[row][col-1],dp[row-1][col]) + 1
                );
            }
        }
        return dp[lenght1][lenght2];
    }
}

思考题

当我们计算标号35的格子的时候，为什么不能从右上角的标号30的格子推导而来呢？
或者说可以从标号23和18的关系来再看一下

字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:

输入: 
first = "pale"
second = "ple"
输出: True

示例 2:

输入: 
first = "pales"
second = "pal"
输出: False

简单做下，逐字符比较法，附加动态规划相关

简单做下，和另外一题几乎一毛一样
161. 相隔为 1 的编辑距离

这题包含了两字符相同的情况也返回true,稍微更加简单点

另外一题的题解 简单逐字符比较，方法也几乎一样

本题就直接比较遍历最后的指针所在位置了，没有去额外声明变量统计相同字符数量，因为在遍历的过程中其实已经代表了有多少个字符相同了

代码

class Solution {
    public boolean oneEditAway(String first, String second) {
        //相同字符的直接返回
        if (first.equals(second)){
            return true;
        }
        //字符长度相差超过一个的
        if (Math.abs(first.length() - second.length()) > 1){
            return false;
        }
        if (first.length() == second.length()){
            int idx = -1;
            while (++idx < first.length() && first.charAt(idx) == second.charAt(idx)){}
            while (++idx < first.length() && first.charAt(idx) == second.charAt(idx)){}
            return idx == first.length();
        }
        if (first.length()>second.length()){
            if (second.length()==0){
                return true;
            }
            int fIdx = 0;
            int sIdx = 0;
            while (sIdx < second.length() && first.charAt(fIdx) == second.charAt(sIdx)){
                fIdx++;
                sIdx++;
            }
            fIdx++;
            while (sIdx < second.length() && first.charAt(fIdx) == second.charAt(sIdx)){
                fIdx++;
                sIdx++;
            }
            return fIdx == first.length();
        }else{
            return oneEditAway(second,first);
        }
    }
}

动态规划 其实也能做，不过单就这题的话，有点杀鸡用牛刀的意思了
可以想试试动态规划的话看下72. 编辑距离

我之前写过的题解 配有详细画图说明 【动态规划】java 编辑距离

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• ‘+’ 不能用作一元运算(例如， “+1” 和 "+(2 + 3)" 无效)
• ‘-‘ 可以用作一元运算(即 “-1” 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

等于把括号去掉算出当前+,-符号真正对应的加减操作算出来

class Solution {
    public int calculate(String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        int idx = -1;
        int flag = 1;
        while (++idx < s.length()){
            char c = s.charAt(idx);
            if (c == ' ')continue;
            switch (c){
                case '+':
                    flag = stack.peek();
                    break;
                case '-':
                    flag = -stack.peek();
                    break;
                case '(':
                    stack.push(flag);
                    break;
                case ')':
                    stack.pop();
                    break;
                default:
                    //取到整个数字
                    int num = c - '0';
                    while (idx+1 < s.length() && s.charAt(idx+1) - '0'>=0 && s.charAt(idx+1)-'9'<=0){
                        idx++;
                        num *= 10;
                        num += s.charAt(idx) - '0';
                    }
                    //取到了整个数字
                    res += flag * num;
                    break;
            }
        }
        return res;
    }
}

写出来好像和官方题解一样？

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

• 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

示例 1：

输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。

示例 2：

输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。

示例 3：

输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。

提示：

• 1 <= s.length, goal.length <= 2 * 104
• s 和 goal 由小写英文字母组成

遍历比较，简单

遍历比较

1. 长度不同 -> false
2. 遍历字符串， 如果不同的的char超过两个 -> false
3. 如果只有一个字符不同 -> false
4. 如果没有字符不同，看原字符串中有无重复的字符，则相同字符互相交换下可以和原来一样 -> true
5. 剩下有两个字符不同的情况，判断下s字符串中第一个不同字符和goal第二个不同位置的是否一样，且s字符串中第二个不同字符和goal第二个不同位置的是否一样 如果符合 -> true
6. 否则 -> false

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()){
            return false;
        }
        int[] diff = new int[]{-1,-1};
        int idx = -1;
        int diffCount = -1;
        int[] charCount = new int[25];
        while (++idx < s.length()){
            charCount[s.charAt(idx)-'a']++;
            if (s.charAt(idx) == goal.charAt(idx)){
                continue;
            }
            if (diffCount == 1){
                return false;
            }
            diff[++diffCount] = idx;
        }
        if (diffCount == 0){
            return false;
        }
        if (diffCount == -1){
            for (int i : charCount) {
                if (i > 1){
                    return true;
                }
            }
            return false;
        }
        return s.charAt(diff[0]) == goal.charAt(diff[1]) && s.charAt(diff[1]) == goal.charAt(diff[0]);
    }

}