删除最短的子数组使剩余数组有序

阿里笔试

https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        int left = 0 ,right = n;
        while (left < n - 1 && arr[left] <= arr[left + 1])
            left++;
        int remain = left + 1;
        while (left < right - 1 && (right == n || arr[right] >= arr[right - 1])) {
            right--;
            while (left >= 0 && arr[left] > arr[right])
                left--;
            remain = max(left + n - right + 1, remain);
        }
        return n - remain;
    }
};

将数组拆分成斐波那契序列

这题很坑：0 <= f[i] < 2^31

class Solution {
public:
    using int64 = long long;
    vector<int> splitIntoFibonacci(string num) {
        vector<int> res;
        dfs(res, num, 0, 0, 0);
        return res;
    }

    bool dfs(vector<int>& res, string num, int64 sum, int idx, int pre) {
        if (idx == num.size()) {
            return res.size() >= 3;
        }
        if (num[idx] == '0') {
            if (res.size() >= 2) {
                if (0 != sum) return false; 
            }
            res.emplace_back(0);
            if (dfs(res, num, pre + 0, idx + 1, 0)) return true;
            res.pop_back();
            return false;
        }
        
        int64 cur = 0;
        for (int i = idx; i < num.size(); ++i) {
            cur = cur * 10 + num[i] - '0';
            if (cur > INT_MAX) break;

            if(res.size() >=2 ){
                if(cur < sum) continue;
                else if(cur> sum) break;
            }
            res.emplace_back(cur);
            if (dfs(res, num, pre + cur, i + 1, cur)) return true;
            res.pop_back();
        }
        return false;
    }
};