头像

温柔大鸡翅




离线:31分钟前



题目描述

给你一个长度为 偶数 n 的整数数组 nums 和一个整数limit 。每一次操作,你可以将 nums 中的任何整数替换为1limit 之间的另一个整数。

如果对于所有下标 i(下标从 0 开始),nums[i] + nums[n - 1 - i]都等于同一个数,则数组 nums互补的 。例如,数组 [1,2,3,4] 是互补的,因为对于所有下标inums[i] + nums[n - 1 - i] = 5

返回使数组 互补最少操作次数。

样例

示例1
输入:nums = [1,2,4,3], limit = 4
输出:1
解释:经过 1 次操作,你可以将数组 nums 变成 [1,2,2,3](加粗元素是变更的数字):
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ,nums[i] + nums[n-1-i] = 4 ,所以 nums 是互补的。
示例2
输入:nums = [1,2,2,1], limit = 2
输出:2
解释:经过 2 次操作,你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ,因为 3 > limit 
示例3
输入:nums = [1,2,1,2], limit = 2
输出:0
解释:nums 已经是互补的。

提示:

  • n == nums.length
  • 2 <= n <= 10^5
  • 1 <= nums[i] <= limit <= 10^5
  • n 是偶数。

算法1

(差分) $O(max(n, limit))$

大家可以移步 @WZC的题解


算法2

(数学,枚举) $O(max(nlog(n), limit*log(n)))$
  1. 考虑数字对 $a_1$和$a_2$,和为s.
  2. 我们不需要做任何改动,就可以形成和为s的一个对。
  3. 我们尝试找出区间 [l, r],使得 $a_1$和$a_2$可以只经过1次改动就进入这个区间
    1. $l = min(a_1, a_2) + 1$
    2. $r = max(a_1, a_2) + limit$
      记录 lr存入两个数组minsmaxs
  4. 对于每一个可能的和t, $t\in[2, limit * 2] $,mins中超过t的以及maxs中小于t的情况,(变化一次还不够小,或者变化一次还不够大)表示需要两次变化, 计算对于t需要两次变化的对数cnt2
  5. 需要一次变化的对数cnt1 = n/2 - 和等于t的对数 - 需要进行两次变化的对数(cnt2)
  6. 考虑对minsmax排序,以通过二分在$log(n)$的时间复杂度内找到cnt2.
  7. 当前t需要 cnt1 + cnt2次变化可以令数组互补。 更新最小的变化次数ans.
  8. [2, limit * 2]枚举所有可能的和,统计出可以构造所有和需要的最小操作步数即为答案.

时间复杂度

  1. 统计 t,minsmaxs需要$O(n)$的时间复杂度
  2. minsmaxs排序需要$O(nlog(n))$的时间复杂度
  3. [2, limit * 2]枚举所有可能的和,需要$limit$此操作,每次需要$log(n)$的时间二分minsmaxs数组来找到cnt2和计算 cnt1
  4. 故总时间复杂度为 $O(max(nlog(n), limit*log(n)))$

C++ 代码

const int N = 1e5 + 10;
int sumDict[N * 2];
int mins[N / 2], maxs[N / 2];
class Solution {
public:
    int n;
    int minMoves(vector<int>& nums, int limit) {
        memset(sumDict, 0,sizeof sumDict);
        n = nums.size();
        int cnt = n;
        for(int i = 0; i < n/2; i++){
            sumDict[nums[i] + nums[n - i - 1]] ++;
            mins[i] = min(nums[i], nums[n - i - 1]) + 1;
            maxs[i] = max(nums[i], nums[n - i - 1]) + limit;
        }
        sort(mins, mins + n / 2);
        sort(maxs, maxs + n / 2);

        for(int i = 2; i <= limit* 2; i++){
            int cnt2 = mins + n / 2 - upper_bound(mins, mins + n / 2, i) + lower_bound(maxs, maxs + n / 2, i) - maxs; 
            int cnt1 = n / 2 - sumDict[i] - cnt2;
            cnt = min(cnt, cnt1 + 2 * cnt2);
        }
        return cnt;
    }
};



  1. 这只是我个人的推荐,大家可以按照自己的水平和学习能力选择最适合自己的计划。

  2. 为了方便系统学习,建议大家在Java与C++之间选择一门语言,大多数的题解和代码还是以C++为主,但是Java选手在阅读C++代码时应该不会有太大困难。掌握一门语言到可以刷题的程度,在有语言基础的情况下也就2-3天就行了.

  3. 学习C++可以考虑语法基础课,掌握基本语法以及STL的常用函数即可。 语法课链接点击这里

  4. 语法课学习完/有语言基础,如果你是一个算法萌新,那么直接上基础课可能会有一些压力,基础课不代表简单。这里其实跟推荐萌新可以报一个PAT的课,它不仅仅是考研,拿来工具语法顺便学习一下基础的算法数据结构也是很好的

  5. 学完PAT之后,可以进入我们的基础班的学习巩固了。准备北美面试的同学可以再同步报一个LC究极班,PAT其实已经涵盖了大部分LC的内容所以刷完PAT刷LC已经可以很舒服了。 LC究极班链接在这里

  6. 搞定PAT LC基础班之后,面试应该没啥问题了奥。如果你是竞赛党,学完基础课之后,根据实际水平:学得不错的同学可以直接上提高课,觉得还需要巩固的同学可以报一个USACO的习题课。但是USACO里面还有有一些奇怪的科技,你可以适当跳过也没关系。等以后再回来啃. USACO辅导课链接在这里

  7. ACWING其实还提供一节在基础课和提高课难度之间的课,我觉得竞赛选手用来过渡很合适,只不过名字比较容易让竞赛生忽略,就是算法笔试面试辅导课 笔试面试辅导课连接在这里 当然如果你只是为了笔试面试,那么这个笔试面试辅导课的难度应该已经面足够绝大多数公司了 (除了少数奇难无比的笔试)

  8. 接下来就是算法提高课啦,我觉得是全家桶中最核心的一节课,虽然说他的难度已经超过了正常笔试面试难度,但是在学习的过程中,你会对一些常用的基础算法和数据结构有一个更深刻的认识,哪怕这些技巧在笔试面试或者做LC周赛的时候用不到,但是你会发现你的码力得到了提升,看问题解决问题的速度也会更快。

  9. 不过提高课的报名费虽然已经很便宜了,但是如果部分同学真的囊中羞涩的话,其实可以白嫖 “算法竞赛进阶指南活动”,目前停更中,但是也已经有了60+小时的视频时长了。 B站链接在这里 不想报提高课的可以报进阶指南,就是难度可能会稍稍陡峭一些,更侧重于习题讲解,理论会比提高课稍微少一些

  10. 提高课和进阶指南打完卡之后,有一个LYD讲的进阶指南DP篇,(我买了,但是感觉提高课和B站的竞赛指南打卡活动的DP章节和LYD的这个活动有一丢丢的重合部分),如果同学兜里有米,当然要支持。而且很多似懂非懂的东西,换个人讲可能会豁然开朗,”在ACWING没有一分钱花的不值得”

  11. 最后就是进阶课了, 大佬们快来进阶课学习新科技!我一个知识点都听不懂!

  12. 另外一些竞赛专题类的 比如NOIP专题 蓝桥杯专题,因为我没打过比赛,也不知道课程难度,就不评论了。

综上,ACWING课程的难度划分,或者让自己打下最扎实基础的学习路线,在我看来应该是

语法课 < PAT = LC究极班 <= 基础课 <= USACO(USACO部分科技应该属于提高课级别)
<= 笔试面试辅导课 < 提高课 <= 进阶指南打卡活动 = LYD系列 <= 进阶课 << YLS




题目描述

给你一个整数数组 nums 和一个正整数k ,返回长度为 k 且最具 竞争力nums 子序列。

数组的子序列是从数组中删除一些元素(可能不删除元素)得到的序列。

在子序列a 和子序列b 第一个不相同的位置上,如果a中的数字小于b 中对应的数字,那么我们称子序列a 比子序列 b(相同长度下)更具 竞争力 。 例如,[1,3,4][1,3,5] 更具竞争力,在第一个不相同的位置,也就是最后一个位置上,4 小于 5

样例

示例1
输入:nums = [3,5,2,6], k = 2
输出:[2,6]
解释:在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中,[2,6] 最具竞争力。

示例2
输入:nums = [2,4,3,3,5,4,9,6], k = 4
输出:[2,3,3,4]


算法1

(单调栈) $O(n + k)$
  1. 这题的暴力思路是显然的: 在 $[0, (n-k+1)]$(因为尾巴要至少留出足够多的数字去凑答案)之间找到最小的数的第一个位置idx 作为ans中的第0个数.
  2. idx + 1(n - (k - 1 )+ 1)之间找到最小的数的第一个位置作为ans 中的第1个数
  3. 重复 步骤$1$, $2$。直到凑满k个.
  4. 这个思路的复杂度是$n^2$的,因此我们需要对他做优化.
    5 一个比较显然的做法是使用线段树维护区间最小值,这个思路的代码会在后面补上。
  5. 观察到搜索区间的左端点idx是一直往右移动的,具有单调性,因此我们可以考虑维护一个单调不递减的栈,前提要求是这个栈的长度加上剩余待枚举的数量和超过k个。
  6. 直接用vector模拟栈即可

时间复杂度

  1. 遍历整个数组需要$O(n)$的时间
  2. 维护单调栈最坏需要k次比较(清空)
  3. 故总时间复杂度为 $O(n + k)$

C++ 代码

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> ans;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(ans.size() && (n - i) + ans.size() > k && nums[i] < ans.back()){
                ans.pop_back();
            }
            if(ans.size() < k) ans.push_back(nums[i]);
        }
        return ans;
    }
};

算法2

(线段树) $O(nlog(n))$

参考解法1的思路,使用线段树加速找到ans[i]的对应区间的最小值.

  1. 这题的暴力思路是显然的: 在 $[0, (n-k+1)]$之间找到最小的数的第一个位置idx 作为ans中的第0个数.
  2. idx(n - (k - 1) + 1)之间找到最小的数的第一个位置作为ans中的第1个数
  3. 重复 步骤$1$, $2$。直到凑满k个.
  4. 这个思路的复杂度是$n^2$的,因此我们需要对他做优化.
  5. 使用线段树加速找到ans[i]的所在原数组区间的最小值。 线段树记录了 区间最小值最小值所在的位置
  6. 由于个人习惯,我在节点中记录了左右端点,静态线段树这里其实是不需要的。

时间复杂度

  1. 需要 $O(n)$的时间预处理线段树
  2. 需要 $O(klog(n))$的时间进行k次查询找到区间最小值
    故总时间复杂度为$O(klog(n))$

C++ 代码

struct Node{
    int l, r, v, idx;
}tr[(int)1e5 * 4 + 10];

class Solution {
public:
    vector<int> nums;

    void pushup(Node& u, Node& left, Node& right){
        u.v = min(left.v, right.v);
        u.idx = left.v <= right.v ? left.idx : right.idx;
    } 

    void build(int u, int l, int r){
        tr[u] = {l, r, 0x3f3f3f3f, 0};
        if(l >= r) {
            tr[u] = {l, r, nums[l], l};
            return;
        }
        int mid = (l + r) >> 1;
        build(u * 2, l, mid);
        build(u * 2 + 1, mid + 1, r);
        pushup(tr[u], tr[u * 2], tr[u * 2 + 1]);
    }

    Node query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u];
        else{
            int mid = (tr[u].l + tr[u].r) >> 1;
            if(r <= mid) return query(u * 2, l, r);
            else if(l > mid) return query(u * 2 + 1, l, r);
            else{
                Node left = query(u * 2, l, r);
                Node right = query(u * 2 + 1, l, r);
                Node ans = {0, 0, 0, 0};
                pushup(ans, left, right);
                return ans;
            }
        }

    }

    vector<int> mostCompetitive(vector<int>& _nums, int k) {
        _nums.insert(_nums.begin(), 0x3f3f3f3f);
        nums = _nums;
        int n = nums.size() - 1;
        build(1, 1, n);
        vector<int> ans(k);
        int idx = 1;
        int K = k;
        Node temp =  query(1, 1, n);
        for(int i = 0; i < K; i++){
            Node temp =  query(1, idx, n - k + 1);
            ans[i] = temp.v;
            idx = temp.idx + 1;
            k--;
        }
        return ans;
    }
};

算法3

(排序 双指针双向夹逼) $O(nlog(n))$
  1. 我们存储{nums[i], i}到数组a中,进行双关键字排序
  2. 定义双指针idx,idx2分别表示
    1. idx表示目前已经处理过的数的最后一个数在原数组中的可行最小位置,从0开始往后遍历。
    2. idx2表示剩余没有确定的数中,已经可以确定的最小位置, 即nums[idx2...n - 1]是可以确定的答案的后缀。初始化为数组长度,即没有一个剩余数字是确定的
  3. 定义参数rem表示剩余未排数字,初始化为k.
  4. 从前往后遍历a数组, 由于a是从小到大排序的,那么
    1. 如果当前遍历到的数字可以放到 k - rem处(当前答案更新到的位置),直接放在k-rem处,rem--
    2. 如果当前遍历到的数字放到k-rem处会导致剩下的数字不够构成长度为k的答案,那么我们尝试更新idx2
    3. 当发现 已经摆好的数字个数+后缀长度等于k时,跳出循环,并把后缀补到ans中。
      这里的4.1和4.2概括一下就是 “非前即后”。遍历到的这个数,它在原数组中的位置只有以下三种情况
      1.属于前缀(即有更小的数字提前卡在了这个位置上) - 无视
      2.属于后缀(即idx2 - n之间) - 无视
      3.在中间:
      * 如果添加到前缀中之后,该位置在原数组中后面剩下的数无法凑够答案,那么就把他拿来更新后缀
      * 否则由于a是有序的,所以它应该直接添加到前缀中
  5. 举个简单的例子
    [3 2 1 4 5] K = 4 排完之后 [1 2 3 4 5]
    1. 遍历 [1 2 3 4 5]1在原数组的下标是2,那么2-4位置的那几个数1 4 5 一定是答案的后缀了.
    2. 下一个数字是2,2在原数组的位置是1,1-4是够拼成k个数的 那么ans的第一个数字肯定是2.
    3. 由于次数已有答案(前缀)的数量是1个,后缀长度是3,刚好可以凑成k=4个数,那么把后缀拼接到ans后面就是我们的答案。

时间复杂度

  1. 需要 $O(n)$的时间预处理{nums[i], [i]}数组a
  2. 需要 $O(nlog(n))$的时间对a排序
  3. 需要 $O(n)$的时候遍历数组移动指针更新答案
    故总时间复杂度为$O(nlog(n))$

C++ 代码

pair<int, int> a[(int)1e5+10];
class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        int idx = 0, n = nums.size(), rem = k, idx2 = nums.size();
        vector<int> ans(k);
        for(int i = 0; i < n; i++) a[i] = {nums[i], i};
        sort(a, a + n);
        for(auto p : a){
            if(p.second >= idx && p.second <= n - rem ){
                ans[k - rem] = p.first;
                rem --;
                idx = p.second + 1;
            }else if(p.second > n - rem && p.second < idx2){
                idx2 = p.second;    
            }
            if(rem - (n - idx2) == 0) break;
        }
        for(int i = idx2; i < n; i++){
            ans[k - (n - i)] = nums[i];
        }
        return ans;
    }
};



题目描述

给你一个 m x n 的整数网格 accounts ,其中 accounts[i][j] 是第 i位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。

客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

样例

示例1
输入:accounts = [[1,2,3],[3,2,1]]
输出:6
解释:
第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的,资产总量都是 6 ,所以返回 6 
示例2
输入:accounts = [[1,5],[7,3],[3,5]]
输出:10
解释:
第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10 
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的,资产总量是 10

示例3
输入:accounts = [[2,8,7],[7,1,3],[1,9,5]]
输出:17

提示

  • m == accounts.length
  • n ==accounts[i].length
  • 1 <= m, n <= 50
  • 1 <= accounts[i][j] <= 100

算法1

(暴力枚举) $O(n * m)$
  1. 按题目模拟,统计出所有客户在各个银行的资产综合,找到资产最多的用户即可

时间复杂度

  1. 统计客户资产综合需要对整个accounts进行遍历, 需要$O(n * m)$的时间
  2. 找到答案需要$O(n)$的时间
  3. 故总时间复杂度为$O(n * m)$

参考文献

C++ 代码

class Solution {
public:
    int maximumWealth(vector<vector<int>>& a) {
        int n = a.size(), m = a[0].size(); 
        vector<int> f(n);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                f[i] += a[i][j];
            }
        }
        return *max_element(f.begin(), f.end());
    }
};



题目描述

我们定义arr山形数组当且仅当它满足:

  • arr.length >= 3
  • 存在某个下标$i$(从 0 开始)满足$0 < i < arr.length - 1$且:
    * $arr[0] < arr[1] < … < arr[i - 1] < arr[i]$
    * $arr[i] > arr[i + 1] > … > arr[arr.length - 1]$
    给你整数数组nums ,请你返回将 nums变成 山形状数组最少删除次数。

样例

示例1
输入:nums = [1,3,1]
输出:0
解释:数组本身就是山形数组,所以我们不需要删除任何元素。
示例2
输入:nums = [2,1,1,5,6,2,3,1]
输出:3
解释:一种方法是将下标为 0,1 和 5 的元素删除,剩余元素为 [1,5,6,3,1] ,是山形数组。
示例3
输入:nums = [4,3,2,1,1,2,3,1]
输出:4
示例4
输入:nums = [1,2,3,4,4,3,2,1]
输出:1

提示

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^9
  • 题目保证 nums 删除一些元素后一定能得到山形数组。

算法1

(最长上升子序列) $O(n^2)$
  1. 我们求出最长上升子序列f1和最长下降子序列f2
  2. 枚举每一个位置i,如果i可能为山峰(左右都有比它小的数), 计算如果以i为山峰所能构造出的山型数组的最大长度,更新这个最大长度.
  3. 总数组的长度减去能形成的山型数组的最大长度,即为最小删除个数.

时间复杂度

  1. 由于数据范围很小,这里用朴素的求解LIS的两个for循环的方法计算出f1f2需要$O(n^2)$
  2. 枚举答案需要$O(n)$
  3. 故总的时间复杂度为 $O(n^2)$

C++ 代码

class Solution {
public:
    int f1[1010], f2[1010];
    int minimumMountainRemovals(vector<int>& arr) {
        int n = arr.size();
        for(int i = 0; i < n; i++){
            f1[i] = 1;
            for(int j = 0; j < i; j++){
                if(arr[j] < arr[i]) f1[i] = max(f1[i], f1[j] + 1);
            }
        }
        for(int i = n - 1; i >= 0; i--){
            f2[i] = 1;
            for(int j = n - 1; j > i; j--){
                if(arr[j] < arr[i]) f2[i] = max(f2[i], f2[j] + 1);
            }
        }
        int tot = 0;
        for (int i = 0; i <= n; i++){
            if(f1[i] > 1 && f2[i] > 1)
                tot = max(tot, f1[i] + f2[i] - 1);
        }
        int ans = n - tot;
        return ans;
    }
};




题目描述

请你设计一个队列,支持在前,中,后三个位置的 pushpop操作。

请你完成FrontMiddleBack类:

FrontMiddleBack()初始化队列。
void pushFront(int val)val添加到队列的 最前面
void pushMiddle(int val)val添加到队列的 正中间
void pushBack(int val)val添加到队里的 最后面
int popFront()将 最前面 的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1
int popMiddle()正中间的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1
int popBack()最后面 的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1
请注意当有两个中间位置的时候,选择靠前面的位置进行操作。比方说:

6添加到[1, 2, 3, 4, 5]的中间位置,结果数组为[1, 2, 6, 3, 4, 5]
[1, 2, 3, 4, 5, 6]的中间位置弹出元素,返回3,数组变为[1, 2, 4, 5, 6]

样例

示例1
输入:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出:
[null, null, null, null, null, 1, 3, 4, 2, -1]

解释:
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] (队列为空)

提示

  • 1 <= val <= 10^9
  • 最多调用1000pushFrontpushMiddlepushBackpopFrontpopMiddlepopBack

注意

  1. 由于此题的数据范围仅有 1000次调用, 因此我这里给出了$O(n^2)$的代码很短能在考试快速AC的写法。
  2. 如果读者需要了解效率更优的 双向链表 和/或 两个双端队列的,$O(n)$解法,可以参照 @WZC的题解

算法1

(暴力模拟) $O(n^2)$
  1. 由于此题的数据范围仅有 1000次调用, 因此我们考虑最简单的暴力模拟即可
  2. 使用一个vector存储当前数据结构中的所有数,那么我们可以利用 vector提供的 insert, push_back,erase等操作实现题目要求的API
  3. Java中的List接口亦有 add(E), add(index, E), remove(index)等对应的API
  4. 对于找中点操作而言,由于题目要求当有两个正中间位置的数的时候,取前面一个,因此对于popMiddle我们的中点坐标为(v.size() - 1) / 2, 而对于pushMiddle而言,我们的目标位置应该在v.size() / 2

时间复杂度

  1. n次操作,每次最坏需要将整个数组中的所有元素挪一个位置
  2. 故总的时间复杂度为$O(n^2)$

参考文献

C++ 代码

class FrontMiddleBackQueue {
public:
    vector<int> v;
    FrontMiddleBackQueue() {

    }

    void pushFront(int val) {
        v.insert(v.begin(), val);
    }

    void pushMiddle(int val) {
        int idx =  (v.size()) / 2;
        v.insert(v.begin() + idx, val);
    }

    void pushBack(int val) {
        v.push_back(val);
    }

    int popFront() {
        if(v.size() == 0) return -1;
        int t = v.front();
        v.erase(v.begin());
        return t;
    }

    int popMiddle() {
        if(v.size() == 0) return -1;
        int t = v[(v.size() - 1) / 2];
        v.erase(v.begin() + (v.size() - 1) / 2);
        return t;
    }

    int popBack() {
        if(v.size() == 0) return -1;
        int t = v.back();
        v.pop_back();
        return t;
    }
};

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
 * obj->pushFront(val);
 * obj->pushMiddle(val);
 * obj->pushBack(val);
 * int param_4 = obj->popFront();
 * int param_5 = obj->popMiddle();
 * int param_6 = obj->popBack();
 */




题目描述

给你两个链表list1list2,它们包含的元素分别为n 个和m 个。

请你将list1中第a个节点到第b个节点删除,并将list2接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果:

fig1.png

请你返回结果链表的头指针。

样例

示例1

merge_linked_list_ex1.png

输入:list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出:[0,1,2,1000000,1000001,1000002,5]
解释:我们删除 list1 中第三和第四个节点,并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例1merge_linked_list_ex2.png

输入:list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出:[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释:上图中蓝色的边和节点为答案链表。

提示

  • 3 <= list1.length <= 10^4
  • 1 <= a <= b < list1.length - 1
  • 1 <= list2.length <= 10^4

算法1

(模拟) $O(n * m)$
  1. 按题意模拟即可
  2. 找到list1a,b的位置
  3. a的前一个节点指向list2
  4. 找到list2的尾巴位置tail2
  5. b的后一个节点接到tail2后面

时间复杂度

  1. 对于list1最坏情况需要遍历整个链表
  2. 对于list2一定需要至少遍历整个链表
  3. 故总时间复杂度为$O(n * m)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode * dummy = new ListNode(-1);
        dummy -> next = list1;
        ListNode *cur = dummy, * prevA = 0, *B = 0;
        while(true){
            if(cur->next->val == a) prevA = cur;
            if(cur->val == b) B = cur;
            if(prevA && B) break;
            cur = cur -> next;
        }
        ListNode* tail = list2;
        while(tail -> next) tail = tail -> next;
        tail -> next = B -> next;
        prevA -> next = list2;
        return dummy->next;

    }
};



题目描述

给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 wordsequence 中最大的重复值。如果word 不是 sequence 的子串,那么重复值 k0

给你一个字符串 sequenceword ,请你返回 最大重复值 k

样例

示例1
输入:sequence = "ababc", word = "ab"
输出:2
解释:"abab" 是 "ababc" 的子字符串。
示例2
输入:sequence = "ababc", word = "ba"
输出:1
解释:"ba" 是 "ababc" 的子字符串,但 "baba" 不是 "ababc" 的子字符串。
示例3
输入:sequence = "ababc", word = "ac"
输出:0
解释:"ac" 不是 "ababc" 的子字符串。

提示

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • sequenceword 都只包含小写英文字母。

算法1

(暴力枚举) $O(n^2)$
  1. t = b;
  2. 如果a中可以找到t,那么让 t = t + b
  3. 一直到找不到t为止,t的延伸次数b即为答案。

时间复杂度

  1. n = sequence.size(), m = word.size()
  2. t最多拓展 n/m次, 每次判断需要$O(n* m * k)$,k 是延伸次数
  3. 故总时间复杂度为 $O(n^3/m)$

C++ 代码

class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int ans = 1;
        string t = word;
        while(sequence.find(t) != -1) {
            ans ++;
            t += word;
        }
        return ans - 1;
    }
};

算法2

(KMP) $O(n)$
  1. 对此题进行KMP扩展以可以解决 n = 10^7级别的问题
  2. 预处理kmpnext数组,在sequence中找到word的所有出现位置
  3. 找到出现位置中的最长连续递增位置,比如当m=5时,如果在 0,5,10,15均找到了,那么次数的连续包含长度就是4.
  4. 可以使用哈希表,记录匹配成功的位置以及对应连续长度。

时间复杂度

  1. 预处理 next数组需要 $O(m)$的时间
  2. KMP匹配需要 $O(m + n)$的时间
  3. 每次匹配成功后更新答案需要$O(1)$的时间
  4. 由于当 m < n时直接返回0, 因此总有 m < n 故总时间复杂度为$O(n)$

C++ 代码

int ne[110];
class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int n = sequence.size(), m = word.size();
        if(m > n) return 0;
        ne[0] = -1;
        for(int i = 1, j = -1; i < m; i++){
            while(j != -1 && word[i] != word[j + 1]) j = ne[j];
            if(word[j + 1] == word[i]) j++;
            ne[i] = j;
        }
        unordered_map<int ,int> hash;
        int ans = 0;
        int last = -1, lastLen = 0;
        for(int i = 0, j =-1; i < n; i++){
            while(j != -1 && sequence[i] != word[j + 1]) j = ne[j];
            if (sequence[i] == word[j + 1])j ++;
            if(j + 1 == m){
                if(hash.count(i - m + 1 - m)){
                    int len = hash[i - m + 1] = hash[i - m + 1 - m] + 1;
                    ans = max(ans, len); 
                }else{
                    ans = max(ans, 1);
                    hash[i - m + 1] = 1;
                }
                j = ne[j];
            }
        }
        return ans;
    }
};

算法3

(KMP) $O(n)$

另一种kmp的写法是通过补齐p的长度到可能的最大可能长度, 通过前缀匹配找到答案.
可以参考
@WZC的题解




题目描述

n 个连接的字符串 s 组成字符串 S,记作S = [s,n]。例如,["abc",3]=“abcabcabc”

如果我们可以从 s2中删除某些字符使其变为 s1,则称字符串 s1可以从字符串 s2 获得。例如,根据定义,"abc" 可以从 “abdbec” 获得,但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1s2(每个最多 100 个字符长)和两个整数 0 ≤ n1 ≤ 1061 ≤ n2 ≤ 10^6。现在考虑字符串 S1S2,其中 S1=[s1,n1]S2=[s2,n2]

请你找出一个可以满足使[S2,M]S1获得的最大整数 M

样例

输入:
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2
返回:
2

算法1

(循环节) $O(len(s1) * len(s2))$
  1. 首先判断两个字符串中的字符类型是否相同,不相同则无法生成.
  2. 将字符串s1延伸n1次,会得到形如 "前缀 + 若干循环节sr + 后缀"的字符串.
  3. 为方便叙述,不妨令前缀长度为t1循环节长度为len,后缀长度为s1延伸后的长度减去循环节总长度前缀长度,即rem = n * n1 - (n * n1 - t1) / len * len - t1
  4. 其中循环节sr的定义为:整个字符串从开始到结尾,可以刚好包裹s2字符串 t2次。
  5. 我们只需要分情况计算 前缀部分, 循环节部分,和后缀部分能够包裹多少次s2的总和tot.
  6. tot / n2即为答案
  7. 我们只是计算循环节的长度以及起始位置,在实际问题中, 可能会因为s1 * n1太小而使得循环节数量为0,此时循环节贡献的答案为0,不会影响答案的正确性.
  8. 我们可以利用哈希表记录每次s2被完全覆盖时,s1中指针的相对位置,当两次相对位置相同时,我们找到了一个循环节. 两次走过的步数差就是循环节的长度,总步数减去循环节长度len即为循环节的开始位置,同时也是前缀的长度t1
  9. 考虑到前缀为长度为0的情况,我们将哈希表初始化为hash[0] = 0, 这样当我们刚好走完一次s1s2时候,能找到最短的循环节

时间复杂度

  1. 判断字符串类型是否相同需要$O(len(s1) + len(s2))$的时间
  2. 找到循环节最对需要$O(len(s1) * len(s2))$, 即最差情况为全部逆序错位.
  3. 计算每一段对答案的贡献需要$O(len(s1) * len(s2))$的时间。(前后缀长度最大为 $循环节长度 - 1$)
  4. 故总时间复杂度为 $O(len(s1) * len(s2))$

C++ 代码

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        // 判断字符类型是否相同,全部相同才有机会获得
        int hash1[128] = {0}, hash2[128] = {0};
        for(char ch : s1) hash1[ch]++;
        for(char ch : s2) {
            hash2[ch] ++;
            if(!hash1[ch]) return 0;
        }
        int n = s1.size(), m = s2.size();
        // 找到循环节
        unordered_map<int, int> hash;
        hash[0] = 0;
        int i = 0, j = 0;
        int steps = 0;
        while(true){
            if(s1[i]==s2[j]) i++, j++;
            else i++;
            steps ++ ;
            if(i == n) i = 0;
            if(j == m){
                j = 0;
                if(hash.count(i)) break;
                hash[i] = steps;
            }

        }
        int len = steps - hash[i];  // 循环节的长度
        int t1 = (steps - len);     // 循环节之前出现的字符数量.
        int t2 = 0;                 // 每个循环节可以覆盖的s2长度
        // 统计每个循环节可以构造出多少个 s2 (求t2)
        for(int k = 0, j = 0; k < len; k++){
            int idx = (k + t1) % n;
            if(s1[idx] == s2[j]) j++;
            if(j == m) j = 0, t2++;
        }
        // 计算循环节能贡献的覆盖次数
        int s2Cnt = (n * n1 - t1) / len * t2;
        // 计算前缀可以贡献的覆盖次数
        for(int k = 0, j = 0; k < t1; k++){
            if(s1[k % n] == s2[j]) j++;
            if(j == m){
                j = 0;
                s2Cnt ++;
            }
        }
        // 计算后缀可以贡献的覆盖次数
        int rem = n * n1 - (n * n1 - t1) / len * len - t1;
        for(int k = 0, j = 0; k < rem; k++){
            int idx = (t1 + k) % n;
            if(s1[idx] == s2[j]) j++;
            if (j == m) j = 0, s2Cnt++;
        }
        int M = s2Cnt / n2;
        return M;
    }
};




题目描述

给你一个 n * n 矩阵 grid ,矩阵由若干 01 组成。请你用四叉树表示该矩阵 grid
你需要返回能表示矩阵的 四叉树 的根结点。
注意,当 isLeafFalse 时,你可以把 True 或者 False 赋值给节点,两种值都会被判题机制 接受
四叉树数据结构中,每个内部节点只有四个子节点。此外,每个节点都有两个属性:

  • val:储存叶子结点所代表的区域的值。1 对应 True,0 对应 False
  • isLeaf: 当这个节点是一个叶子结点时为 True,如果它有 4 个子节点则为 False.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树:

  • 如果当前网格的值相同(即,全为 0 或者全为 1),将 isLeaf 设为 True ,将 val 设为网格相应的值,并将四个子节点都设为 Null 然后停止。
  • 如果当前网格的值不同,将 isLeaf 设为 False, 将 val 设为任意值,然后如下图所示,将当前网格划分为四个子网格。
  • 使用适当的子网格递归每个子节点。
    new_top.png
    如果你想了解更多关于四叉树的内容,可以参考 wiki

四叉树格式

输出为使用层序遍历后四叉树的序列化形式,其中 null 表示路径终止符,其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val]

如果 isLeaf 或者 val 的值为 True ,则表示它在列表[isLeaf, val] 中的值为 1 ;如果 isLeaf 或者 val 的值为 False ,则表示值为 0

样例

示例1

grid1.png

输入:grid = [[0,1],[1,0]]
输出:[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释:此示例的解释如下:
请注意,在下面四叉树的图示中,0 表示 false,1 表示 True 。

e1tree.png

示例2

e2mat.png

输入:grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出:[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释:网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft,bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值,因此我们将其再分为 4 个子网格,这样每个子网格都具有相同的值。
解释如下图所示:

e2tree.png

示例3
输入:grid = [[1,1],[1,1]]
输出:[[1,1]]
示例4
输入:grid = [[0]]
输出:[[1,0]]
示例5
输入:grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
输出:[[0,1],[1,1],[1,0],[1,0],[1,1]]

提示:

  • n == grid.length == grid[i].length
  • n == 2^x 其中 0 <= x <= 6

算法1

(dfs, 二维前缀和) $O(n^2)$
  1. 数据范围很小,暴力也可以过。为了方便拓展,这里我们给出矩阵前缀和的做法.
  2. 预处理二维前缀和。
  3. 递归生成根节点和
    • 如果要处理的小矩阵的和等于正方形面积或者等于0,说明是一个叶子节点
    • 如果不是叶子节点,将当前矩形分成四块,分别挂在当前节点的四个变量上, 递归处理

时间复杂度

  1. 预处理前缀和需要$O(n^2)$的时间
  2. 最多将矩阵分成$O(n^2)$个$1*1$的小矩阵,每次分成小矩阵后需要$(O(1)$的时间判断是否是叶子节点,一共需要$O(n^2)$的时间
  3. 故总时间复杂度为 $O(n^2)$

参考文献

大鸡翅的C++模板 - 基础1.2: 二维前缀和
定义:
S[i][1] = m[1][1]到m[i][j]的子矩阵的元素和
构造:
    S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + m[i][j]
    m[i][j] += m[i][j-1] + m[i-1][j] - m[i-1][j-1]  // in place
性质:
    Sum([m[x1][y1]...m[x2][y2]]) = 
        S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1]

C++ 代码

class Solution {
public:
    int n;
    int mat[70][70];
    int getArea(int x1 ,int x2, int y1, int y2){
        return mat[x2][y2] - mat[x2][y1 - 1] - mat[x1 - 1][y2] + mat[x1 - 1][y1 - 1];
    }
    Node* dfs(int x1, int x2, int y1, int y2){
        Node* root = new Node(0, false);
        int allOnes = (x2 - x1 + 1) * (y2 - y1 + 1);
        int area = getArea(x1, x2, y1, y2);
        if(area == allOnes || area == 0){
            root -> isLeaf = true;
            root -> val = area == 0 ? 0 : 1;
            return root; 
        } 
        int midX = (x1 + x2) / 2, midY = (y1 + y2) / 2;
        root -> topLeft = dfs(x1, midX, y1, midY);
        root -> topRight = dfs(x1, midX, midY + 1, y2);
        root -> bottomLeft = dfs(midX + 1, x2, y1, midY);
        root -> bottomRight = dfs(midX + 1, x2, midY + 1, y2);
        return root;
    }

    Node* construct(vector<vector<int>>& grid) {
        memset(mat, 0, sizeof mat);
        n = grid.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j ++){
                mat[i + 1][j + 1] = grid[i][j] + mat[i][j + 1] + mat[i + 1][j] - mat[i][j];
            }
        }
        return dfs(1, n, 1, n);
    }
};