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