串联所有单词的子串(哈希表、字符串)、求公式的值(数学、阶乘)、扰乱字符串(字符串、动态规划)

串联所有单词的子串(哈希表、字符串)

给定一个字符串 s和一些长度相同的单词 words。找出 s中恰好可以由 words中所有单词串联形成的子串的起始位置。
注意子串要与 words中的单词完全匹配，中间不能有其他字符，但不需要考虑 words中单词串联的顺序。

示例 1：

输入：  s = "barfoothefoobarman",  words = ["foo","bar"]
输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：  s = "wordgoodgoodgoodbestword",  words = ["word","good","best","word"]
输出：[]

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

class Solution {
	public List<Integer> findSubstring(String s, String[] words) {
		List<Integer> res = new ArrayList<>();
		if (s == null || s.length() == 0 || words == null || words.length == 0)
			return res;
		HashMap<String, Integer> map = new HashMap<>();
		int one_word = words[0].length();
		int word_num = words.length;
		int all_len = one_word * word_num;
		for (String word : words) {
			map.put(word, map.getOrDefault(word, 0) + 1);
		}
		for (int i = 0; i < one_word; i++) {
			int left = i, right = i, count = 0;
			HashMap<String, Integer> tmp_map = new HashMap<>();
			while (right + one_word <= s.length()) {
				String w = s.substring(right, right + one_word);
				right += one_word;
				if (!map.containsKey(w)) {
					count = 0;
					left = right;
					tmp_map.clear();
				} else {
					tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
					count++;
					while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)) {
						______________________;
					}
					if (count == word_num)
						res.add(left);
				}
			}
		}
		return res;
	}
}

解答：

String t_w = s.substring(left, left + one_word);
count--;
tmp_map.put(t_w, tmp_map.getOrDefault(t_w, 0) - 1);
left += one_word;

求公式的值(数学、阶乘)

求 1-1/2!-1/3! -… -1/10!
解答：

public class TEST {
    public static double jiecheng(int n) {
        double s = 1;
        for (int i = 1; i <= n; i++)
            s *= i;
        return s;
    }
    public static double sum(int n) {
        double sum = 0.0;
        int s = 1;
        for (int i = 1; i <= n; i++) {
            sum += s / jiecheng(i);
            s = -s;
        }
        return sum;
    }
    public static void main(String[] args) throws Exception {
        int n = 10;
        double ss = sum(n);
        System.out.println(ss);
    }
}

扰乱字符串(字符串、动态规划)

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

1. 如果字符串的长度为 1 ，算法停止
2. 如果字符串的长度 > 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 由小写英文字母组成

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

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;
	}
}

解答：

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;

本文内容到此结束了，
如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位大佬指出。
保持热爱，奔赴下一场山海。🏃🏃🏃