C/C++教程

LeetCode 剑指 Offer II 069. 山峰数组的顶部(三分) / 38. 外观数列 / 282. 给表达式添加运算符

本文主要是介绍LeetCode 剑指 Offer II 069. 山峰数组的顶部(三分) / 38. 外观数列 / 282. 给表达式添加运算符,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

剑指 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. 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

来源:力扣(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;
        }
    }
}
这篇关于LeetCode 剑指 Offer II 069. 山峰数组的顶部(三分) / 38. 外观数列 / 282. 给表达式添加运算符的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!