月度归档： 2022年6月

给你一个字符串 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]);
    }

}

给定两个字符串 s 和 t ，如果它们的编辑距离为 1 ，则返回 true ，否则返回 false 。

字符串 s 和字符串 t 之间满足编辑距离等于 1 有三种可能的情形：

• 往 s 中插入 恰好一个 字符得到 t
• 从 s 中删除 恰好一个 字符得到 t
• 在 s 中用 一个不同的字符 替换 恰好一个 字符得到 t

示例 1：

输入: s = "ab", t = "acb"
输出: true
解释: 可以将 'c' 插入字符串 s 来得到 t。

示例 2:

输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。

提示:

• 0 <= s.length, t.length <= 104
• s 和 t 由小写字母，大写字母和数字组成

简单逐字符比较

比较简单，就挨个比较没啥太多细节，动态规划解法的话，还是有点点复杂的，不过拿来做这题有点过了

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s.length() - t.length() > 1 || t.length() - s.length() > 1){
            return false;
        }
        if (s.length() == t.length()){
            return checkSameLength(s,t);
        }

        if (s.length() > t.length()){
            return checkOneCharDiff(s,t);
        }else{
            return checkOneCharDiff(t,s);
        }
    }

    public boolean checkOneCharDiff(String s, String t){
        int sIdx = 0;
        int tIdx = 0;
        int sameCount = 0;
        while (tIdx<t.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        sIdx++;
        while (tIdx<t.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        return s.length()-sameCount == 1;
    }

    public boolean checkSameLength(String s, String t){
        int sIdx = 0;
        int tIdx = 0;
        int sameCount = 0;
        while (sIdx<s.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        sIdx++;
        tIdx++;
        while (sIdx<s.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        return s.length()-sameCount == 1;
    }
}

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

Sunday算法实现

举个栗子说明，haystack字符串

h, e, l, l, o, s, h, e, l, l, d, o, h, e, l, d, l, o, h, e, l, w, l, o, q, h, e, l, l, o, w, h, e, l, l, o
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

needle字符串

l, o, h, e, l, w, l
0  1  2  3  4  5  6

1. 从头开始匹配，匹配失败，
2. 找到haystack第7个字符下标6位置的字符h，h字符在needle字符串l, o, h, e, l, w, l最后出现的下标为2，则从下标6位置的字符h往前找2位开始匹配，
3. 此时新开始匹配的下标为4，字符为o，依旧匹配失败，继续往后找needle字符串长度的位置在下标11位置发现字符o，此时o在needle中最后出现的位置为下标1，则往前找一位，从haystack的10下标开始匹配
4. 10下标的d不能和needle匹配，继续往后找needle长度个位置，依旧是字符o，在needle中最后出现的位置为下标1，则往前找一位从haystack的第16下标开始匹配，
5. 能完全匹配，结束，返回当前开始的下标16。

代码

class Solution {
    //Sunday算法实现
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        int[] lastPos = new int[256];
        for (int i = 0; i < needle.length(); i++) {
            lastPos[needle.charAt(i)] = i;
        }
        for (int i = 0; i + m <= n; i += (m - lastPos[haystack.charAt(i+m)])) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i+j) == needle.charAt(j)){
                    continue;
                }
                flag = false;
                break;
            }
            if (flag){
                return i;
            }
            if (i + m >= n) break;
        }
        return -1;
    }
}