剑指 Offer II 069. 山峰数组的顶部
2021.10.14 每日一题
题目描述
符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
- arr.length >= 3
- 存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i ，即山峰顶部。
示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [1,3,5,4,2]
输出：2
示例 3：
输入：arr = [0,10,5,2]
输出：1
示例 4：
输入：arr = [3,4,5,1]
输出：2
示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2
提示：
3 <= arr.length <= 104
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组
进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/B1IidL
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
最开始练二分的时候做的题，判断mid和mid+1位置的数，如果前者小于后者，说明是上升坡度，所以山脉顶部在mid右边，left = mid + 1，否则是下降，那么顶部在mid及其左边，所以right = mid
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int l = arr.length;
int left = 0;
int right = l - 1;
while(left < right){
int mid = (right - left) / 2 + left;
if(arr[mid] < arr[mid + 1])
left = mid + 1;
else
right = mid;
}
return left;
}
}
然后看了一下三叶姐提到的三分，三分是将区间分成三个部分，但是判断是只判断一次，即和二分一样只有两个分支，如果有三个分支的话，相当于每次判断的时间也增加了，所以不能叫三分，只能说是变形的二分
而三分是解决单峰函数极值问题
因此一般将「通过比较两个端点，每次否决 1/3 区间 来解决单峰最值问题」的做法称为「三分」；而不是简单根据单次循环内将区间分为多少份来判定是否为「三分」。
综上，只有「二分」和「三分」的概念，不存在所谓的 k 分
又学到了！
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 0, r = n - 1;
while (l < r) {
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
if (arr[m1] > arr[m2]) r = m2 - 1;
else l = m1 + 1;
}
return r;
}
}
作者：AC_OIer
链接：https://leetcode-cn.com/problems/B1IidL/solution/gong-shui-san-xie-er-fen-san-fen-ji-zhi-lc8zl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
38. 外观数列
2021.10.15 每日一题
题目描述
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
- countAndSay(1) = “1”
- countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
- 1
- 11
- 21
- 1211
- 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-and-say
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
打表题
class Solution {
static String num = "1";
static String[] list = new String[31];
static{
list[1] = num;
for(int i = 2; i <= 30; i++){
int count = 1;
StringBuffer sb = new StringBuffer();
char c = num.charAt(0);
for(int j = 1; j < num.length(); j++){
if(num.charAt(j) == c)
count++;
else{
sb.append(count + "" + c);
count = 1;
c = num.charAt(j);
}
}
sb.append(count + "" + c);
num = sb.toString();
list[i] = num;
}
}
public String countAndSay(int n) {
return list[n];
}
}
282. 给表达式添加运算符
2021.10.16 每日一题
题目描述
给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。
示例 1:
输入: num = “123”, target = 6
输出: [“1+2+3”, “123”]
示例 2:
输入: num = “232”, target = 8
输出: [“23+2", "2+32”]
示例 3:
输入: num = “105”, target = 5
输出: [“1*0+5”,“10-5”]
示例 4:
输入: num = “00”, target = 0
输出: [“0+0”, “0-0”, “0*0”]
示例 5:
输入: num = “3456237490”, target = 9191
输出: []
提示：
1 <= num.length <= 10
num 仅含数字
-2^31 <= target <= 2^31 - 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/expression-add-operators
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
看到数据范围，很明显想到的是遍历所有情况
先写了个回溯，枚举所有情况，很烦，很勉强的过了
主要还是因为枚举所有情况最后还要计算表达式的值，太烦了
但是在计算过程中因为有乘法，所以不知道怎么在过程中计算表达式的值
class Solution {
List<String> res = new ArrayList<>();
int l;
int target;
public List<String> addOperators(String num, int target) {
//l个数字加l - 1 个运算符
l = num.length();
this.target = target;
StringBuffer sb = new StringBuffer();
backtracking(sb, num, 0);
return res;
}
public void backtracking(StringBuffer sb, String num, int idx){
if(idx == l){
if(calculate(sb) == (long)target){
res.add(sb.toString());
}
return;
}
for(int i = idx; i < l; i++){
String temp = num.substring(idx, i + 1);
if(idx == 0){
sb.append(temp);
backtracking(sb, num, i + 1);
sb.delete(0, sb.length());
}else{
sb.append("*" + temp);
backtracking(sb, num, i + 1);
sb.setCharAt(sb.length() - temp.length() - 1, '+');
backtracking(sb, num, i + 1);
sb.setCharAt(sb.length() - temp.length() - 1, '-');
backtracking(sb, num, i + 1);
sb = sb.delete(sb.length() - temp.length() - 1, sb.length());
}
if("0".equals(temp))
break;
}
}
public long calculate(StringBuffer sb){
long ans = 0;
Stack<Long> n = new Stack<>();
Stack<Character> symbol = new Stack<>();
char lastflag = ' ';
for(int i = 0; i < sb.length(); i++){
char c = sb.charAt(i);
if(c == '+' || c == '-' || c == '*'){
symbol.push(c);
lastflag = c;
}else{
long temp = c - '0';
i++;
while(i < sb.length()){
if(sb.charAt(i) >= '0' && sb.charAt(i) <= '9'){
temp = temp * 10 + (sb.charAt(i) - '0');
i++;
}
else{
break;
}
}
i--;
if(lastflag == '*'){
symbol.pop();
long lastnum = n.pop();
n.push(lastnum * temp);
}else{
n.push(temp);
}
}
}
while(!symbol.isEmpty()){
long t = n.pop();
char c = symbol.pop();
if(c == '+')
ans += t;
else
ans -= t;
}
return ans + n.pop();
}
}
但是看了一下，额外计算表达式值的时候，也是从左到右计算的乘法，所以按理说应该在计算过程中也计算，所以记录一个变量，改一下：
class Solution {
List<String> res = new ArrayList<>();
int l;
int target;
public List<String> addOperators(String num, int target) {
//l个数字加l - 1 个运算符
l = num.length();
this.target = target;
StringBuffer sb = new StringBuffer();
backtracking(sb, num, 0, 0, 0);
return res;
}
public void backtracking(StringBuffer sb, String num, int idx, long mul, long cur){
if(idx == l){
if(cur == (long)target){
res.add(sb.toString());
}
return;
}
for(int i = idx; i < l; i++){
String temp = num.substring(idx, i + 1);
long t = Long.valueOf(temp);
if(idx == 0){
sb.append(temp);
backtracking(sb, num, i + 1, t, t);
sb.delete(0, sb.length());
}else{
sb.append("*" + temp);
backtracking(sb, num, i + 1, mul * t, cur - mul + mul * t);
sb.setCharAt(sb.length() - temp.length() - 1, '+');
backtracking(sb, num, i + 1, t, cur + t);
sb.setCharAt(sb.length() - temp.length() - 1, '-');
backtracking(sb, num, i + 1, -t, cur - t);
sb = sb.delete(sb.length() - temp.length() - 1, sb.length());
}
if("0".equals(temp))
break;
}
}
}