首页 > 其他分享 >2023-09-01：用go语言编写。给出两个长度均为n的数组， A = { a1, a2, ... ,an }， B = { b1, b2, ... ,bn }。 你需要求出其有多少个区间[L,R]

2023-09-01：用go语言编写。给出两个长度均为n的数组， A = { a1, a2, ... ,an }， B = { b1, b2, ... ,bn }。 你需要求出其有多少个区间[L,R]

时间：2023-09-01 17:22:29浏览次数：52  
标签：... 01 lb rand int bn la let ans

2023-09-01：用go语言编写。给出两个长度均为n的数组，

A = { a1, a2, ... ,an }，

B = { b1, b2, ... ,bn }。

你需要求出其有多少个区间[L,R]满足:

数组A中下标在[L,R]中的元素之和在[La,Ra]之中，

数组B中下标在[L,R]中的元素之和在[Lb,Rb]之中。

输入：

第一行有一个正整数N(1<=N<=100000)，代表两个数组的长度。

第二行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。

第三行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。

第四行有4个整数La,Ra,Lb,Rb，范围在0到10^18之间，代表题目描述中的参数。

输出：

输出一个整数，代表所求的答案。

来自微众银行。

来自左程云。

答案2023-09-01：

大体过程如下：

1.定义两个暴力方法（nums1和nums2）来求解问题。这两个方法的输入参数包括两个数组A和B，数组A的左右边界（la和ra），数组B的左右边界（lb和rb）。

2.方法nums1使用暴力的方法遍历所有可能的区间，并统计满足条件的区间个数。

  • 初始化变量ans为0，表示满足条件的区间个数。

  • 使用两层循环遍历数组A的所有可能区间。外层循环变量l表示区间的左边界，内层循环变量r表示区间的右边界。

  • 对于每个区间，初始化变量sumA和sumB为0，分别表示数组A和数组B中元素之和。

  • 使用一个循环遍历当前区间内的元素，累加sumA和sumB。

  • 判断sumA是否在[la, ra]之间，sumB是否在[lb, rb]之间，如果满足条件则增加ans的值。

  • 返回ans作为结果。

3.方法nums2使用优化的方法来求解问题。

  • 初始化变量ans为0，表示满足条件的区间个数。

  • 初始化变量rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2为0，分别表示数组A和数组B的右边界和元素之和。

  • 使用一个循环遍历数组A的所有可能左边界。循环变量l表示左边界的位置。

  • 在循环中，使用while循环更新rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2，使其满足条件。

  • 计算数组A和数组B的左右交集的左边界left和右边界right。

  • 如果left小于right，则将right减去left的值加到ans中。

  • 根据当前左边界l更新rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2。

  • 返回ans作为结果。

4.定义randomArray方法，用于生成指定长度和范围的随机数组。

  • 输入参数包括数组的长度n和随机数的范围v。

  • 初始化一个长度为n的数组ans。

  • 使用一个循环遍历数组，为每个元素赋一个随机数值。

  • 返回生成的随机数组ans。

5.定义max和min方法，分别用于求两个数的最大值和最小值。

6.在main函数中进行测试。

  • 初始化随机数种子。

  • 定义常量N和V，表示数组的长度和随机数的范围。

  • 定义变量testTimes，表示测试次数。

  • 使用循环进行测试。

  • 在每次测试中，生成随机数组A和B，以及随机的la、ra、lb、rb。

  • 调用nums1和nums2方法，分别得到暴力和优化方法的结果。

  • 比较两个结果，如果不一致则输出错误信息。

  • 完成测试后输出测试结束信息。

总的时间复杂度：

  • 对于方法nums1，需要三重循环遍历数组，时间复杂度为O(n^3)。

  • 对于方法nums2，需要两重循环遍历数组，时间复杂度为O(n^2)。

总的额外空间复杂度：

  • 除了输入参数外，额外使用的空间主要是变量和随机数组。因此，额外空间复杂度为O(n)。

go完整代码如下：

package main

import (
    "math/rand"
    "fmt"
	"time"
)

// 暴力方法
func nums1(A []int, B []int, la int, ra int, lb int, rb int) int {
    n := len(A)
    ans := 0
    for l := 0; l < n; l++ {
        for r := l; r < n; r++ {
            sumA := 0
            sumB := 0
            for i := l; i <= r; i++ {
                sumA += A[i]
                sumB += B[i]
            }
            if sumA >= la && sumA <= ra && sumB >= lb && sumB <= rb {
                ans++
            }
        }
    }
    return ans
}

// 正式方法
func nums2(A []int, B []int, la int, ra int, lb int, rb int) int {
    n := len(A)
    ans := 0
    rightA1, sumA1, rightA2, sumA2 := 0, 0, 0, 0
    rightB1, sumB1, rightB2, sumB2 := 0, 0, 0, 0
    for l := 0; l < n; l++ {
        for rightA1 < n && sumA1+A[rightA1] < la {
            sumA1 += A[rightA1]
            rightA1++
        }
        for rightA2 < n && sumA2+A[rightA2] <= ra {
            sumA2 += A[rightA2]
            rightA2++
        }
        for rightB1 < n && sumB1+B[rightB1] < lb {
            sumB1 += B[rightB1]
            rightB1++
        }
        for rightB2 < n && sumB2+B[rightB2] <= rb {
            sumB2 += B[rightB2]
            rightB2++
        }
        left := max(rightA1, rightB1)
        right := min(rightA2, rightB2)
        if left < right {
            ans += right - left
        }
        if rightA1 == l {
            rightA1++
        } else {
            sumA1 -= A[l]
        }
        sumA2 -= A[l]
        if rightB1 == l {
            rightB1++
        } else {
            sumB1 -= B[l]
        }
        sumB2 -= B[l]
    }
    return ans
}

func randomArray(n int, v int) []int {
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        ans[i] = rand.Intn(v)
    }
    return ans
}

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

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
	rand.Seed(time.Now().Unix())
    N := 50
    V := 100
    testTimes := 10000
    fmt.Println("测试开始")
    for i := 0; i < testTimes; i++ {
        n := rand.Intn(N)
        A := randomArray(n, V)
        B := randomArray(n, V)
        a := rand.Intn(V)
        b := rand.Intn(V)
        c := rand.Intn(V)
        d := rand.Intn(V)
        la := min(a, b)
        ra := max(a, b)
        lb := min(c, d)
        rb := max(c, d)
        ans1 := nums1(A, B, la, ra, lb, rb)
        ans2 := nums2(A, B, la, ra, lb, rb)
        if ans1 != ans2 {
            fmt.Println("出错了!")
        }
    }
    fmt.Println("测试结束")
}

在这里插入图片描述

rust完整代码如下：

use rand::Rng;

fn nums1(A: &[i32], B: &[i32], la: i32, ra: i32, lb: i32, rb: i32) -> i32 {
    let n = A.len();
    let mut ans = 0;
    for l in 0..n {
        for r in l..n {
            let mut sum_a = 0;
            let mut sum_b = 0;
            for i in l..=r {
                sum_a += A[i];
                sum_b += B[i];
            }
            if sum_a >= la && sum_a <= ra && sum_b >= lb && sum_b <= rb {
                ans += 1;
            }
        }
    }
    ans
}

fn nums2(A: &[i32], B: &[i32], la: i32, ra: i32, lb: i32, rb: i32) -> i32 {
    let n = A.len() as i32;
    let mut ans = 0;
    let (mut right_a1, mut sum_a1, mut right_a2, mut sum_a2) = (0, 0, 0, 0);
    let (mut right_b1, mut sum_b1, mut right_b2, mut sum_b2) = (0, 0, 0, 0);
    for l in 0..n {
        while right_a1 < n && sum_a1 + A[right_a1 as usize] < la {
            sum_a1 += A[right_a1 as usize];
            right_a1 += 1;
        }
        while right_a2 < n && sum_a2 + A[right_a2 as usize] <= ra {
            sum_a2 += A[right_a2 as usize];
            right_a2 += 1;
        }
        while right_b1 < n && sum_b1 + B[right_b1 as usize] < lb {
            sum_b1 += B[right_b1 as usize];
            right_b1 += 1;
        }
        while right_b2 < n && sum_b2 + B[right_b2 as usize] <= rb {
            sum_b2 += B[right_b2 as usize];
            right_b2 += 1;
        }
        let left = right_a1.max(right_b1);
        let right = right_a2.min(right_b2);
        if left < right {
            ans += right - left;
        }
        if right_a1 == l {
            right_a1 += 1;
        } else {
            sum_a1 -= A[l as usize];
        }
        sum_a2 -= A[l as usize];
        if right_b1 == l {
            right_b1 += 1;
        } else {
            sum_b1 -= B[l as usize];
        }
        sum_b2 -= B[l as usize];
    }
    ans
}

fn random_array(n: i32, v: i32) -> Vec<i32> {
    let mut rng = rand::thread_rng();
    (0..n).map(|_| rng.gen_range(0, v)).collect()
}

fn main() {
    const N: i32 = 50;
    const V: i32 = 100;
    const TEST_TIMES: usize = 10000;
    println!("测试开始");
    for _ in 0..TEST_TIMES {
        let n = rand::thread_rng().gen_range(0, N);
        let A = random_array(n, V);
        let B = random_array(n, V);
        let a = rand::thread_rng().gen_range(0, V);
        let b = rand::thread_rng().gen_range(0, V);
        let c = rand::thread_rng().gen_range(0, V);
        let d = rand::thread_rng().gen_range(0, V);
        let la = a.min(b);
        let ra = a.max(b);
        let lb = c.min(d);
        let rb = c.max(d);
        let ans1 = nums1(&A, &B, la, ra, lb, rb);
        let ans2 = nums2(&A, &B, la, ra, lb, rb);
        if ans1 != ans2 {
            println!("出错了!");
        }
    }
    println!("测试结束");
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

int nums1(vector<int>& A, vector<int>& B, int la, int ra, int lb, int rb) {
    int n = A.size();
    int ans = 0;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int sumA = 0;
            int sumB = 0;
            for (int i = l; i <= r; i++) {
                sumA += A[i];
                sumB += B[i];
            }
            if (sumA >= la && sumA <= ra && sumB >= lb && sumB <= rb) {
                ans++;
            }
        }
    }
    return ans;
}

int nums2(vector<int>& A, vector<int>& B, int la, int ra, int lb, int rb) {
    int n = A.size();
    int ans = 0;
    int rightA1 = 0, sumA1 = 0, rightA2 = 0, sumA2 = 0, rightB1 = 0, sumB1 = 0, rightB2 = 0, sumB2 = 0;
    for (int l = 0; l < n; l++) {
        while (rightA1 < n && sumA1 + A[rightA1] < la) {
            sumA1 += A[rightA1++];
        }
        while (rightA2 < n && sumA2 + A[rightA2] <= ra) {
            sumA2 += A[rightA2++];
        }
        while (rightB1 < n && sumB1 + B[rightB1] < lb) {
            sumB1 += B[rightB1++];
        }
        while (rightB2 < n && sumB2 + B[rightB2] <= rb) {
            sumB2 += B[rightB2++];
        }
        int left = max(rightA1, rightB1);
        int right = min(rightA2, rightB2);
        if (left < right) {
            ans += right - left;
        }
        if (rightA1 == l) {
            rightA1++;
        }
        else {
            sumA1 -= A[l];
        }
        sumA2 -= A[l];
        if (rightB1 == l) {
            rightB1++;
        }
        else {
            sumB1 -= B[l];
        }
        sumB2 -= B[l];
    }
    return ans;
}

vector<int> randomArray(int n, int v) {
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = rand() % v;
    }
    return ans;
}

int main() {
    int N = 50;
    int V = 100;
    int testTimes = 10000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTimes; i++) {
        int n = rand() % N;
        vector<int> A = randomArray(n, V);
        vector<int> B = randomArray(n, V);
        int a = rand() % V;
        int b = rand() % V;
        int c = rand() % V;
        int d = rand() % V;
        int la = min(a, b);
        int ra = max(a, b);
        int lb = min(c, d);
        int rb = max(c, d);
        int ans1 = nums1(A, B, la, ra, lb, rb);
        int ans2 = nums2(A, B, la, ra, lb, rb);
        if (ans1 != ans2) {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 暴力方法
// 为了测试
int nums1(int* A, int* B, int n, int la, int ra, int lb, int rb) {
    int ans = 0;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int sumA = 0;
            int sumB = 0;
            for (int i = l; i <= r; i++) {
                sumA += A[i];
                sumB += B[i];
            }
            if (sumA >= la && sumA <= ra && sumB >= lb && sumB <= rb) {
                ans++;
            }
        }
    }
    return ans;
}

// 正式方法
// 时间复杂度O(N)
int nums2(int* A, int* B, int n, int la, int ra, int lb, int rb) {
    int ans = 0;
    int rightA1 = 0, sumA1 = 0, rightA2 = 0, sumA2 = 0, rightB1 = 0, sumB1 = 0, rightB2 = 0, sumB2 = 0;
    for (int l = 0; l < n; l++) {
        while (rightA1 < n && sumA1 + A[rightA1] < la) {
            sumA1 += A[rightA1++];
        }
        while (rightA2 < n && sumA2 + A[rightA2] <= ra) {
            sumA2 += A[rightA2++];
        }
        while (rightB1 < n && sumB1 + B[rightB1] < lb) {
            sumB1 += B[rightB1++];
        }
        while (rightB2 < n&& sumB2 + B[rightB2] <= rb) {
            sumB2 += B[rightB2++];
        }
        int left = rightA1 > rightB1 ? rightA1 : rightB1;
        int right = rightA2 < rightB2 ? rightA2 : rightB2;
        if (left < right) {
            ans += right - left;
        }
        if (rightA1 == l) {
            rightA1++;
        }
        else {
            sumA1 -= A[l];
        }
        sumA2 -= A[l];
        if (rightB1 == l) {
            rightB1++;
        }
        else {
            sumB1 -= B[l];
        }
        sumB2 -= B[l];
    }
    return ans;
}

// 为了测试
int* randomArray(int n, int v) {
    int* ans = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        ans[i] = rand() % v;
    }
    return ans;
}

// 为了测试
int main() {
    int N = 50;
    int V = 100;
    int testTimes = 10000;
    printf("测试开始\n");
    srand(time(NULL));
    for (int i = 0; i < testTimes; i++) {
        int n = rand() % N;
        int* A = randomArray(n, V);
        int* B = randomArray(n, V);
        int a = rand() % V;
        int b = rand() % V;
        int c = rand() % V;
        int d = rand() % V;
        int la = (a < b) ? a : b;
        int ra = (a > b) ? a : b;
        int lb = (c < d) ? c : d;
        int rb = (c > d) ? c : d;
        int ans1 = nums1(A, B, n, la, ra, lb, rb);
        int ans2 = nums2(A, B, n, la, ra, lb, rb);
        if (ans1 != ans2) {
            printf("出错了!\n");
        }
        free(A);
        free(B);
    }
    printf("测试结束\n");
    return 0;
}

在这里插入图片描述

标签：...,01,lb,rand,int,bn,la,let,ans
From： https://www.cnblogs.com/moonfdd/p/17672454.html

相关文章

  • BUUCTF [安洵杯 2019]easy_web
    试试模板注入发现，不行，然后伪协议，不行，再爆破目录也不行。从?img=TXpVek5UTTFNbVUzTURabE5qYz0入手，可能是base64编码。base64解码：(不知道为什么别的WP上变成这样了，否则解不出来)TXpVek5UTTFNbVUzTURabE5q得到：MzUzNTM1MmU3MDZlNj再base64解码：MzUzNTM1MmU3MDZl得到：353535......
  • 【230901-7】有8位学生，其中小学生2名，初中生3名，高中生3名，现将他们排成一列，要求2名小学
    【230901-7】有8位学生，其中小学生2名，初中生3名，高中生3名，现将他们排成一列，要求2名小学生相邻，3名初中生相邻，3名高中生任意两名都不相邻，则不同排法有几种？......
  • OGG-01496 Failed to open target trail file ./dirdat/ra000002, at RBA 2179
    1．问题描述在启动OGG源端的投递进程时，报错：OGG-01496OGG-01496Failedtoopentargettrailfile./dirdat/ra000002,atRBA2179 2．原因分析目标端trail文件丢失，查看目标端的${OGG_HOME}/dirdat下确实没有文件存在。3．解决办法源端OGG：alter extract pump1 etrollover......
  • tomcat 安装笔记 20230901
    war位置/usr/local/tomcat8_1/webapps/tomcat位置71.170/usr/local/tomcat8_1/给了点工具包位置/usr/local/tool/启动tomcatcd/usr/local/tomcat8_1/bin/./startup.sh没有权限启动cd/usr/local/tomcat8_1/bin/chmode777*启动失败没有java环境，安装下cd/usr/l......
  • [代码随想录]Day33-动态规划part01
    题目：509.斐波那契数思路：动规五部曲：这里我们要用一个一维dp数组来保存递归的结果确定dp数组以及下标的含义dp[i]的定义为：第i个数的斐波那契数值是dp[i]确定递推公式为什么这是一道非常简单的入门题目呢？因为题目已经把递推公式直接给我们了：状态转移方程dp[i]=dp[i-......
  • BN的可训练参数，BN批归一化操作
    批归一化（BatchNormalization，简称BN）是一种深度学习中常用的正则化技术，它有一些可训练的参数，包括：缩放参数（Scale）：通常用γ表示，它用来调整每个特征的标准差，从而控制特征的缩放。偏移参数（Shift）：通常用β表示，它用来调整每个特征的平均值，从而控制特征的平移。这两个参数是可训练的，它......
  • P4344 SHOI2015 脑洞治疗仪
    \(P4344\)[\(SHOI2015\)]脑洞治疗仪一、题目描述曾经发明了自动刷题机的发明家\(SHTSC\)又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。为了简单起见，我们将大脑视作一个\(01\)序列。\(1\)代表这个位置的脑组织正常工作，\(0\)代表......
  • ogg 的抽取进程 2015-06-17 05:51:08 ERROR OGG-02077
    报错信息如下HowtoresolveExtractAbendingWithOGG-02077Error(DocID2037420.1)这种情况是把抽取进程注册到数据库中了，你又强制启动相同的抽取进程，就会与数据库中注册的进程冲突，你可以执行下边语句删除数据库中抽取进程Stepstoclearthespecificextractcomponen......
  • freeswitch 在visualstudio 2017 中编译运行
    1、visualstudio使用2017版本的2、下载 https://github.com/PerkinsZhu/freeswitch/tree/v1.8 源码   错误处理：一、 下载地址：https://wixtoolset.gallerycdn.vsassets.io/extensions/wixtoolset/wixtoolsetvisualstudio2017extension/1.0.0.22/1668223938167/......
  • BUUCTF [GWCTF 2019]我有一个数据库
    文件包含漏洞，和SQL注入等攻击方式一样，文件包含漏洞也是一种注入型漏洞，其本质就是输入一段用户能够控制的脚本或者代码，并让服务端执行。什么叫包含呢？以PHP为例，我们常常把可重复使用的函数写入到单个文件中，在使用该函数时，直接调用此文件，而无需再次编写函数，这一过程叫做包含。有时......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99