Java每日一练(20230415) 扰乱字符串、单词拆分、模拟计算器-阿里云开发者社区

1. 扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：

在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：s1 = "great", s2 = "rgeat"

输出：true

解释：s1 上可能发生的一种情形是：

"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串

"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」

"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割

"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」

"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"

"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」

算法终止，结果字符串和 s2 相同，都是 "rgeat"

这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

示例 2：

输入：s1 = "abcde", s2 = "caebd"

输出：false

示例 3：

输入：s1 = "a", s2 = "a"

输出：true

提示：

s1.length == s2.length
1 <= s1.length <= 30
s1 和 s2 由小写英文字母组成

以下程序实现了这一功能，请你填补空白处内容：

```c++
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() == 0 && s2.length() == 0)
            return true;
        if (s1.length() != s2.length())
            return false;
        return dfs(s1.toCharArray(), s2.toCharArray(), 0, 0, s1.length());
    }
    private boolean dfs(char[] s1, char[] s2, int start1, int start2, int len) {
        if (len == 1) {
            return s1[start1] == s2[start2];
        }
        if (!equals(s1, s2, start1, start2, len)) {
            return false;
        }
        for (int i = 1; i < len; i++) {
            ____________________;
        }
        return false;
    }
    public boolean equals(char[] s1, char[] s2, int start1, int start2, int len) {
        int[] charArr = new int[26];
        for (int i = 0; i < len; i++) {
            charArr[s1[start1 + i] - 'a']++;
            charArr[s2[start2 + i] - 'a']--;
        }
        for (int item : charArr) {
            if (item != 0)
                return false;
        }
        return true;
    }
}
```

出处：

https://edu.csdn.net/practice/25658360

代码：

import java.util.*;
public class isScramble {
    public static class Solution {
        public boolean isScramble(String s1, String s2) {
            if (s1.length() == 0 && s2.length() == 0)
                return true;
            if (s1.length() != s2.length())
                return false;
            return dfs(s1.toCharArray(), s2.toCharArray(), 0, 0, s1.length());
        }
        private boolean dfs(char[] s1, char[] s2, int start1, int start2, int len) {
            if (len == 1) {
                return s1[start1] == s2[start2];
            }
            if (!equals(s1, s2, start1, start2, len)) {
                return false;
            }
            for (int i = 1; i < len; i++) {
                if (dfs(s1, s2, start1, start2, i) && dfs(s1, s2, start1 + i, start2 + i, len - i))
                    return true;
                if (dfs(s1, s2, start1, start2 + len - i, i) && dfs(s1, s2, start1 + i, start2, len - i))
                    return true;
            }
            return false;
        }
        public boolean equals(char[] s1, char[] s2, int start1, int start2, int len) {
            int[] charArr = new int[26];
            for (int i = 0; i < len; i++) {
                charArr[s1[start1 + i] - 'a']++;
                charArr[s2[start2 + i] - 'a']--;
            }
            for (int item : charArr) {
                if (item != 0)
                    return false;
            }
            return true;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String s1 = "great", s2 = "rgeat";
        System.out.println(s.isScramble(s1, s2));
        s1 = "abcde"; s2 = "caebd";
        System.out.println(s.isScramble(s1, s2));
        s1 = "a"; s2 = "a";
        System.out.println(s.isScramble(s1, s2));
    }
}

输出：

true

false

true

2. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]

输出: true

解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。

注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: false

出处：

https://edu.csdn.net/practice/25658361

代码：

import java.util.*;
public class wordBreak {
    public static class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            int length = s.length();
            int size = wordDict.size();
            if (length == 0) {
                return true;
            }
            if (size == 0) {
                return false;
            }
            boolean[] dp = new boolean[length];
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < size; j++) {
                    String now = wordDict.get(j);
                    if (i < now.length()) {
                        String test = s.substring(0, i + 1);
                        if (now.equals(test)) {
                            dp[i] = true;
                            break;
                        }
                    }
                    if (i >= now.length()) {
                        String test = s.substring(i - now.length() + 1, i + 1);
                        if (dp[i - now.length()] && test.equals(now)) {
                            dp[i] = true;
                            break;
                        }
                    }
                }
            }
            return dp[length - 1];
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] str1 = {"leet", "code"};  
        List<String> wordDict = new ArrayList<>(Arrays.asList(str1));
        String s = "leetcode";
        System.out.println(sol.wordBreak(s, wordDict));
        String[] str2 = {"apple", "pen"};
        s = "applepenapple";
        wordDict = new ArrayList<>(Arrays.asList(str2));
        System.out.println(sol.wordBreak(s, wordDict));
        String[] str3 = {"cats", "dog", "sand", "and", "cat"};
        s = "catsandog";
        wordDict = new ArrayList<>(Arrays.asList(str3));
        System.out.println(sol.wordBreak(s, wordDict));
    }
}

输出：

true

false

3. 模拟计算器

要求：

（1）定义名为Number的类，在其中定义两个私有的整型数据成员n1和n2；

（2）在Number类中编写构造方法，赋予n1和n2初始值；

（3）再为Number类定义加（addition）、减（subtration）、乘（multiplication）、除（division）四个公有成员方法，分别对两个成员变量执行加、减、乘、除的运算。注意：除法运算时要抛出除数为0的异常；

（4）在主方法中创建Number类的对象，调用上述各个方法，测试并输出计算结果，注意进行必要的异常捕获与处理。

出处：

https://edu.csdn.net/practice/25658362

代码：

public class Number {
    private int n1;
    private int n2;
    public Number(int n1, int n2) {
        this.n1 = n1;
        this.n2 = n2;
    }
    public int addition() {
        return n1 + n2;
    }
    public int subtration() {
        return n1 - n2;
    }
    public int multiplication() {
        return n1 * n2;
    }
    private int division() {
        if (n2 == 0) {
            throw new IllegalArgumentException("除数参数不合法");
        }
        return n1 / n2;
    }
    public static void main(String[] args) {
        Number number = new Number(6, 0);
        System.out.println(number.addition());
        System.out.println(number.subtration());
        System.out.println(number.multiplication());
        try {
            System.out.println(number.division());
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }
}