当前位置：
  1. 首页
  2. 互联网
  3. 正文
本文介绍: 2023-09-01：用go语言编写。给出两个长度均为n的数组，你需要求出其有多少个区间[L,R]满足:数组A中下标在[L,R]中的元素之和在[La,Ra]之中，数组B中下标在[L,R]中的元素之和在[Lb,Rb]之中。输入：第一行有一个正整数N(1

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使用暴力的方法遍历所有可能的区间，并统计满足条件的区间个数。

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

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

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

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

总的时间复杂度：

总的额外空间复杂度：

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 &amp;&amp; sumA <= ra &amp;&amp; sumB >= lb &amp;&amp; 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 &amp;&amp; sumA1+A[rightA1] < la {
            sumA1 += A[rightA1]
            rightA1++
        }
        for rightA2 < n &amp;&amp; sumA2+A[rightA2] <= ra {
            sumA2 += A[rightA2]
            rightA2++
        }
        for rightB1 < n &amp;&amp; sumB1+B[rightB1] < lb {
            sumB1 += B[rightB1]
            rightB1++
        }
        for rightB2 < n &amp;&amp; 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: &amp;[i32], B: &amp;[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 &amp;&amp; sum_a <= ra &amp;&amp; sum_b >= lb &amp;&amp; sum_b <= rb {
                ans += 1;
            }
        }
    }
    ans
}

fn nums2(A: &amp;[i32], B: &amp;[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;
}

在这里插入图片描述

原文地址:https://blog.csdn.net/weixin_48502062/article/details/132624038

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_34984.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

上一篇 golang常用库之- encoding/binary包 | 字节转换成整形、整形转换成字节、“大字端” 和 “小字端”
下一篇 【Spring Boot】如何集成Swagger

相关文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

插入图片
浏览器会保存昵称、邮箱和网站cookies信息，下次评论时使用。