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
