1. 外观数列
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
例如，数字字符串 "3322251" 的描述如下图：
示例 1：
输入：n = 1
输出："1"
解释：这是一个基本样例。
示例 2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示：
1 <= n <= 30
出处：
https://edu.csdn.net/practice/26974821
代码：
import java.util.*; public class countAndSay { public static class Solution { public String countAndSay(int n) { String pre = "1"; for (int i = 1; i < n; i++) { StringBuilder temp = new StringBuilder(); char c = pre.charAt(0); int cnt = 1; for (int j = 1; j < pre.length(); j++) { char cc = pre.charAt(j); if (c == cc) { cnt++; } else { temp.append(cnt).append(c); cnt = 1; c = cc; } } temp.append(cnt).append(c); pre = temp.toString(); } return pre; } } public static void main(String[] args) { Solution s = new Solution(); System.out.println(s.countAndSay(1)); System.out.println(s.countAndSay(4)); } }
输出：
1
1211
2. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按 严格递增 顺序排列
出处：
https://edu.csdn.net/practice/26974822
代码：
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } class Solution { public TreeNode sortedArrayToBST(int[] nums) { return traversal(nums, 0, nums.length - 1); } public TreeNode traversal(int[] nums, int left, int right) { if (left > right) return null; int mid = left + ((right - left) / 2); TreeNode node = new TreeNode(nums[mid]); node.left = traversal(nums, left, mid - 1); node.right = traversal(nums, mid + 1, right); return node; } }
输出：
略
3. 翻转字符串里的单词
给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = " hello world "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
示例 4：
输入：s = " Bob Loves Alice "
输出："Alice Loves Bob"
示例 5：
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
提示：
1 <= s.length <= 10^4
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：
请尝试使用 O(1) 额外空间复杂度的原地解法。
出处：
https://edu.csdn.net/practice/26974823
代码：
import java.util.*; import java.util.LinkedList; public class reverseWords { public static class Solution { public StringBuilder trimSpaces(String s) { int left = 0, right = s.length() - 1; while (left <= right && s.charAt(left) == ' ') ++left; while (left <= right && s.charAt(right) == ' ') --right; StringBuilder sb = new StringBuilder(); while (left <= right) { char c = s.charAt(left); if (c != ' ') sb.append(c); else if (sb.charAt(sb.length() - 1) != ' ') sb.append(c); ++left; } return sb; } public void reverse(StringBuilder sb, int left, int right) { while (left < right) { char tmp = sb.charAt(left); sb.setCharAt(left++, sb.charAt(right)); sb.setCharAt(right--, tmp); } } public void reverseEachWord(StringBuilder sb) { int n = sb.length(); int start = 0, end = 0; while (start < n) { while (end < n && sb.charAt(end) != ' ') ++end; reverse(sb, start, end - 1); start = end + 1; ++end; } } public String reverseWords(String s) { StringBuilder sb = trimSpaces(s); reverse(sb, 0, sb.length() - 1); reverseEachWord(sb); return sb.toString(); } } public static void main(String[] args) { Solution s = new Solution(); String str = "the sky is blue"; System.out.println(s.reverseWords(str)); str = " hello world "; System.out.println(s.reverseWords(str)); str = "a good example"; System.out.println(s.reverseWords(str)); str = " Bob Loves Alice "; System.out.println(s.reverseWords(str)); str = "Alice does not even like bob"; System.out.println(s.reverseWords(str)); } }
输出：
blue is sky the
world hello
example good a
Alice Loves Bob
bob like even not does Alice
