首页 > 其他分享 >2023-08-24：请用go语言编写。给定一个长度为n的数组arr， 现在你有一次机会, 将其中连续的K个数全修改成任意一个值， 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出

2023-08-24：请用go语言编写。给定一个长度为n的数组arr， 现在你有一次机会, 将其中连续的K个数全修改成任意一个值， 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出

时间：2023-11-10 12:00:58浏览次数：34  
标签：arr int len find 修改 MAXN ans 最长


2023-08-24：请用go语言编写。给定一个长度为n的数组arr，

现在你有一次机会, 将其中连续的K个数全修改成任意一个值，

请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。

请输出这个最长的长度。

最长不下降子序列:子序列中的每个数不小于在它之前的数。

1 <= k, n <= 10^5，

1 <= arr[i] <= 10^6。

答案2023-08-24：

以下是大致的步骤描述：

1.定义常量MAXN为100001，声明全局数组和变量：arr、right、ends、n和k。这些数组和变量将用于存储计算过程中的中间结果和输入数据。

2.在main函数中设置给定的输入数据：n表示数组的长度为5，k表示连续的k个数需要修改，arr存储具体的数组元素。

3.判断如果k大于等于n，则无需做修改，直接输出n作为最长不下降子序列的长度。

4.否则，调用rightFn函数计算修改后的数组中以每个元素为结尾的最长不下降子序列的长度，并将结果存储在数组right和ends中。

5.调用getAns函数计算修改后的数组的最长不下降子序列的长度，并输出结果。

rightFn函数的步骤描述：

1.初始化right数组的最后一个元素right[n]为1，表示以最后一个元素为结尾的最长不下降子序列的长度为1。

2.初始化ends数组的第一个元素ends[1]为arr[n]，表示以最后一个元素为结尾的最长不下降子序列的最后一个元素为arr[n]。

3.初始化len为1，表示当前得到的最长不下降子序列的长度为1。

4.从倒数第二个元素开始，循环遍历数组arr，通过二分查找的方式找到以arr[i]为结尾的最长不下降子序列的长度。

5.使用二分查找的辅助数组ends，找到大于arr[i]的第一个元素位置find。

6.将arr[i]赋值给ends[find]，更新当前的最长不下降子序列的长度为max(len, find)，并将结果存储在right[i]中。

7.循环结束后，right数组存储了以每个元素为结尾的最长不下降子序列的长度。

getAns函数的步骤描述：

1.初始化ans为0，表示当前的最长不下降子序列的长度为0。

2.初始化len为0，表示当前最长不下降子序列的长度为0。

3.从第k+1个元素开始，循环遍历数组arr，计算修改后的数组的最长不下降子序列的长度。

4.使用二分查找的方式找到arr[i]在ends数组中的位置find。

5.更新ans为max(ans, find+right[i]-1+k)。其中，find表示以arr[i]为结尾的最长不下降子序列的长度，right[i]表示以arr[i]为起点的最长不下降子序列的长度，k表示连续的k个数被修改。

6.使用二分查找的辅助数组ends，找到大于arr[j]的第一个元素位置find（这里j为i-k）。

7.将arr[j]赋值给ends[find]，更新当前的最长不下降子序列的长度为max(len, find)。

8.循环结束后，ans存储了修改后的数组的最长不下降子序列的长度。

9.返回ans作为结果。

总的时间复杂度为O(n log n)，其中n为数组的长度，主要是由二分查找的过程引起的。

总的额外空间复杂度为O(n)，主要是由数组的存储引起的。

go完整代码如下：

package main

import (
	"fmt"
)

const MAXN = 100001

var arr [MAXN]int
var right [MAXN]int
var ends [MAXN]int
var n, k int

func main() {

	n = 5
	k = 1
	arr[1] = 1
	arr[2] = 4
	arr[3] = 2
	arr[4] = 8
	arr[5] = 5

	if k >= n {
		fmt.Println(n)
	} else {
		rightFn()
		fmt.Println(getAns())
	}
}

func rightFn() {
	right[n] = 1
	ends[1] = arr[n]
	len := 1

	for i := n - 1; i > 0; i-- {
		l := 1
		r := len
		find := len + 1

		for l <= r {
			m := (l + r) / 2
			if ends[m] < arr[i] {
				find = m
				r = m - 1
			} else {
				l = m + 1
			}
		}

		ends[find] = arr[i]
		len = max(len, find)
		right[i] = find
	}
}

func getAns() int {
	ans := 0
	len := 0

	for i, j := k+1, 1; i <= n; i, j = i+1, j+1 {
		l := 1
		r := len
		find := len + 1

		for l <= r {
			m := (l + r) / 2
			if ends[m] > arr[i] {
				find = m
				r = m - 1
			} else {
				l = m + 1
			}
		}

		ans = max(ans, find+right[i]-1+k)

		l = 1
		r = len
		find = len + 1

		for l <= r {
			m := (l + r) / 2
			if ends[m] > arr[j] {
				find = m
				r = m - 1
			} else {
				l = m + 1
			}
		}

		len = max(len, find)
		ends[find] = arr[j]
	}

	ans = max(ans, len+k)
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

2023-08-24：请用go语言编写。给定一个长度为n的数组arr， 现在你有一次机会, 将其中连续的K个数全修改成任意一个值， 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出_后端

rust完整代码如下：

const MAXN: i32 = 100001;

static mut ARR: [i32; MAXN as usize] = [0; MAXN as usize];
static mut RIGHT: [i32; MAXN as usize] = [0; MAXN as usize];
static mut ENDS: [i32; MAXN as usize] = [0; MAXN as usize];
static mut N: i32 = 0;
static mut K: i32 = 0;

fn main() {
    unsafe {
        N = 5;
        K = 1;
        ARR[1] = 1;
        ARR[2] = 4;
        ARR[3] = 2;
        ARR[4] = 8;
        ARR[5] = 5;

        if K >= N {
            println!("{}", N);
        } else {
            right_fn();
            println!("{}", get_ans());
        }
    }
}

fn right_fn() {
    unsafe {
        RIGHT[N as usize] = 1;
        ENDS[1] = ARR[N as usize];
        let mut len: i32 = 1;

        let mut i = N - 1;
        while i >= 0 {
            let mut l = 1;
            let mut r = len;
            let mut find = len + 1;

            while l <= r {
                let m = (l + r) / 2;
                if ENDS[m as usize] < ARR[i as usize] {
                    find = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            ENDS[find as usize] = ARR[i as usize];
            len = max(len, find);
            RIGHT[i as usize] = find;
            i -= 1;
        }
    }
}

fn get_ans() -> i32 {
    let mut ans = 0;
    let mut len = 0;

    unsafe {
        let mut i = K + 1;
        let mut j: i32 = 1;
        while i <= N {
            let mut l: i32 = 1;
            let mut r = len;
            let mut find = len + 1;

            while l <= r {
                let m = (l + r) / 2;
                if ENDS[m as usize] > ARR[i as usize] {
                    find = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            ans = max(ans, find + RIGHT[i as usize] - 1 + K);

            l = 1;
            r = len;
            find = len + 1;

            while l <= r {
                let m = (l + r) / 2;
                if ENDS[m as usize] > ARR[j as usize] {
                    find = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            len = max(len, find);
            ENDS[find as usize] = ARR[j as usize];
            i += 1;
            j += 1;
        }

        ans = max(ans, len + K);
    }

    ans
}

fn max(a: i32, b: i32) -> i32 {
    if a > b {
        a
    } else {
        b
    }
}

2023-08-24：请用go语言编写。给定一个长度为n的数组arr， 现在你有一次机会, 将其中连续的K个数全修改成任意一个值， 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出_子序列_02

c++完整代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100001;

int arr[MAXN] = { 0 };
int right0[MAXN] = { 0 };
int ends0[MAXN] = { 0 };
int n, k;

int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}

void rightFn() {
    right0[n] = 1;
    ends0[1] = arr[n];
    int len = 1;

    for (int i = n - 1; i > 0; i--) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends0[m] < arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ends0[find] = arr[i];
        len = max(len, find);
        right0[i] = find;
    }
}

int getAns() {
    int ans = 0;
    int len = 0;

    for (int i = k + 1, j = 1; i <= n; i++, j++) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends0[m] > arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ans = max(ans, find + right0[i] - 1 + k);

        l = 1;
        r = len;
        find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends0[m] > arr[j]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        len = max(len, find);
        ends0[find] = arr[j];
    }

    ans = max(ans, len + k);
    return ans;
}

int main() {
    n = 5;
    k = 1;
    arr[1] = 1;
    arr[2] = 4;
    arr[3] = 2;
    arr[4] = 8;
    arr[5] = 5;

    if (k >= n) {
        cout << n << endl;
    }
    else {
        rightFn();
        cout << getAns() << endl;
    }

    return 0;
}

2023-08-24：请用go语言编写。给定一个长度为n的数组arr， 现在你有一次机会, 将其中连续的K个数全修改成任意一个值， 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出_开发语言_03

c完整代码如下：

#include <stdio.h>

#define MAXN 100001

int arr[MAXN];
int right[MAXN];
int ends[MAXN];
int n, k;

int max(int a, int b) {
    return (a > b) ? a : b;
}

void rightFn() {
    right[n] = 1;
    ends[1] = arr[n];
    int len = 1;

    for (int i = n - 1; i > 0; i--) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends[m] < arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ends[find] = arr[i];
        len = max(len, find);
        right[i] = find;
    }
}

int getAns() {
    int ans = 0;
    int len = 0;

    for (int i = k + 1, j = 1; i <= n; i++, j++) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends[m] > arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ans = max(ans, find + right[i] - 1 + k);

        l = 1;
        r = len;
        find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends[m] > arr[j]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        len = max(len, find);
        ends[find] = arr[j];
    }

    ans = max(ans, len + k);
    return ans;
}

int main() {
    n = 5;
    k = 1;
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 4;
    arr[3] = 2;
    arr[4] = 8;
    arr[5] = 5;

    if (k >= n) {
        printf("%d\n", n);
    }
    else {
        rightFn();
        printf("%d\n", getAns());
    }
    return 0;
}

2023-08-24：请用go语言编写。给定一个长度为n的数组arr， 现在你有一次机会, 将其中连续的K个数全修改成任意一个值， 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出_后端_04


标签：arr,int,len,find,修改,MAXN,ans,最长
From： https://blog.51cto.com/moonfdd/8295072

相关文章

  • ArrayList
    ArrayList的底层是动态数组，它的容量能动态增长。索引存取元素，有序，可重复，允许多个null1、ArrayList初始容量privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};privatestaticfinalObject[]EMPTY_ELEMENTDATA={};transientObject[]elementData;......
  • 修改运行中的docker容器的端口映射的三种方式
    前言在dockerrun创建并运行容器的时候，可以通过-p指定端口映射规则。但是，我们经常会遇到刚开始忘记设置端口映射或者设置错了需要修改。当dockerstart运行容器后并没有提供一个-p选项或设置，让你修改指定端口映射规则。那么这种情况我们该怎么处理呢？方法一:删除原有容器，重新建新容......
  • yum源修改基于CentOS Linux release 8.3.2011
    查看系统版本：（8的镜像源都可以用不用分小版本）cat/etc/redhat-release修改centos文件内容sed-i's/mirrorlist/#mirrorlist/g'/etc/yum.repos.d/CentOS-*sed-i's|#baseurl=http://mirror.centos.org|baseurl=http://vault.centos.org|g'/etc/yum.repos.d/CentOS......
  • ABAP:CS01/CS02/CS03 BOM创建/修改保存前增强
    BADI:BOM_UPDATEMETHODif_ex_bom_update~change_at_save.******ADDBYZJ20231108校验存储地点是否为空SIFsy-tcodeEQ'CS01'ORsy-tcodeEQ'CS02'ORsy-tcodeEQ'CS03'.LOOPATdelta_stpobINTODATA(ls_stpob)WHERE......
  • 【安卓13】谷歌原生桌面launcher3源码修改，修改桌面布局（首屏应用、小部件、导航栏、大
    前言近期接到一个关于谷歌EDLA认证的需求，我负责的是谷歌原生桌面布局的修改，通过研究源码，将涉及到了一些修改思路发出来，大家可以参考一下有没有对你有用的信息。主要修改内容有：1、搜索栏、底部导航栏未居中2、中部应用未按要求排布，详情请参考摹客3、在原生Google桌面未添加中......
  • 【Java Web】从配置修改静态变量
    对象@ConfigurationProperties(prefix="system-upload-prefix")@Configuration@RefreshScope@DatapublicclassSystemUploadPrefix{privateStringupload;}修改常量@ComponentpublicclassConstants{@AutowiredSystemUploadPrefixsystemU......
  • 【Git基础篇】Git之撤回修改
    有时候写了一堆东西，发现都不需要了，怎么撤回修改呢？有大致分为以下3种情况：gitadd之前gitadd之后，gitcommit之前gitcommit之后gitadd之前//这2个命令都不会撤回新建的文件，新建的文件只能手动删除gitcheckout--filename//放弃该文件的修改gitcheckout.//放弃所有......
  • 如何修改网络配置(动态_静态IP)
    接口丝印设备名说明NET1eth1百兆网卡，位于核心板上NET2eth0千兆网卡，位于底板上1.配置静态IP  1.1千兆以太网固定IP方式 方法一  打开/etc/profilevi/etc/profile       在最后加上ifconfigeth0192.168.1.151gateway192.168.1.2up      重启开发......
  • DataGridView绑定数据之后如何修改列值
    privatevoiddataGridView1_CellFormatting(objectsender,DataGridViewCellFormattingEventArgse){if(e==null||e.Value==null||!(senderisDataGridView))return;DataGridViewview=(DataGridView)send......
  • 最长平衡子字符串
    题目概述：给定一字符串s(只由字符0和1组成)，返回其平衡子串的最长的长度。所谓平衡子串就是指在该字串中所有的0都在1之前，且0的数量和1的数量相等解题思路：由于数据范围比较小，所以直接暴力枚举所有子串，并判断是否为平衡子串更新答案即可。时间复杂度：\(O(n^4)\)代码：classSolution......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99