wangxuehui LV 9 @ 8 months ago

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <climits>
#include <set>
using namespace std;
typedef long long LL ;

 //借用力扣128的官解思路
int main() {
    string s;
    cin>>s;
    stringstream ss(s);
    string t;
    set<LL> st;//如果存在多个最大连续内存块，则返回起始编号最小的那个。 必须使用set 如果是unordered_set就无序会报错

    while(getline(ss,t,',')){
        st.insert(stoll(t));
    }
    LL maxlen=0;
    LL res_start=0;
    for(auto& num:st){
        if (!st.count(num-1)) {
            LL start_num=num;//存序号
            LL start=num;
            LL slen=1;
            while (st.count(start+1)) {
                start++;//进行加加
                slen++;
            }
            if (slen>maxlen) {
               maxlen=slen;
               res_start=start_num;
            }
        }
    }
    cout<<res_start<<","<<maxlen;
    return 0;
}

TaZi SU @ 9 months ago

题面描述

在本题中，要求实现一个动态内存管理模块的内存块合并功能。当用户释放一组内存块（如“2,4,3,7,6”）后，系统需返回当前最大的连续可用内存块的起始编号和长度。如果多个最大连续内存块存在，需返回起始编号最小的那个。通过对释放的内存块进行排序和合并，最终输出一个包含起始位置和长度的元组（例如“2,3”），表示从编号2开始的长度为3的连续内存块是最大的。

思路

由于需要我们查找连续数字,因此,我们需要对给定的数组进行排序,这样我们判断两个数字连续只需要判断 $arr[i]-arr[i-1]==1$ 即可.

那么我们可以对于每一个数字 $arr[i]$ 都以它本身编号i为起始编号,不断向后查找求得最长长度,时间复杂度为 $O(n^2)$ .这个时间复杂度可以优化.我们发现假设i为起始编号对应最长长度为 $cnt(cnt>1)$ ,那么 $i+1$ 为起始编号时,最长长度肯定是 $cnt-1$ .

因此,我们一旦发现最长长度 $cnt$ 大于1时,那么后续的 $cnt-1$ 个数都不需要寻找最长长度,因为必定小于 $cnt$ .

按照上面的思路,我们假设 $i$ 为起始编号时,对应最长长度为 $cnt$ .此时,下一步我们需要判断的下标就可以为 $i+cnt$ ,其中 $[i+1,i+cnt-1]$ 的下标都不需要判断最长长度.所以总的时间复杂度为 $O(n)$ ,因为每个点都只会被所有循环加起来枚举到一次.

题解

在本题中，我们需要实现一个动态内存管理模块的内存块合并功能。当用户释放一组内存块编号时，我们需要返回当前最大的连续可用内存块的起始编号和长度。为了实现这一点，我们可以按照以下步骤进行：

输入处理：首先读取用户输入的内存块编号，并将其拆分成整数数组。
排序：对数组进行排序，以便后续判断相邻编号是否连续。
查找最大连续块：
- 遍历排序后的数组，通过判断相邻元素的差值是否为1来确定连续的内存块。
- 记录当前连续块的长度，并更新最大连续块的信息（起始编号和长度）。
- 优化查找过程：当我们发现一个连续块的长度大于1时，后续的连续块长度必定小于之前的长度，因此可以跳过已检查的元素，直接移动到下一个可能的起始位置。
输出结果：最终输出找到的最大连续内存块的起始编号和长度。

代码

CPP

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr; // 存储释放的内存块编号
    std::string input; // 用于存储输入字符串
    std::getline(std::cin, input); // 读取整行输入

    std::string token; // 用于存储分割的每个编号
    size_t pos = 0; // 记录当前分割位置
    // 处理输入，将以逗号分隔的数字转为整数并存入数组
    while ((pos = input.find(',')) != std::string::npos) {
        token = input.substr(0, pos); // 提取当前编号
        arr.push_back(std::stoi(token)); // 转换为整数并存入数组
        input.erase(0, pos + 1); // 移除已处理的部分
    }
    arr.push_back(std::stoi(input)); // 处理最后一个编号

    std::sort(arr.begin(), arr.end()); // 对数组进行排序

    int i = 0; // 当前遍历的索引
    int ans1 = -1; // 用于存储最大连续块的起始编号
    int ans2 = -1; // 用于存储最大连续块的长度

    while (i < arr.size()) { // 遍历整个数组
        int cnt = 1; // 记录当前连续块的长度
        // 向后查找相邻的连续数字
        for (int j = i + 1; j < arr.size(); j++) {
            // 判断相邻元素是否连续
            if (arr[j] - arr[j - 1] == 1) {
                cnt++; // 如果连续，长度加1
            } else {
                break; // 如果不连续，退出循环
            }
        }
        // 更新最大连续块的信息
        if (cnt > ans2) { // 如果当前长度大于已知最大长度
            ans2 = cnt; // 更新最大长度
            ans1 = arr[i]; // 更新起始编号
        }
        // 跳过已经检查的元素，直接移动到下一个可能的起始位置
        i += cnt; // 将i移动到下一个待检查的索引
    }
    
    // 输出结果，格式为“起始编号,长度”
    std::cout << ans1 << ",";
    std::cout << ans2 << std::endl;
    
    return 0; // 返回成功
}

python

arr = [int(i) for i in input().split(",")]#处理输入
arr.sort()#排序
i = 0
ans1 = -1
ans2 = -1
while i < len(arr):#第一层循环
    cnt = 1
    for j in range(i + 1, len(arr)):#记录最大相邻数
       if arr[j] - arr[j - 1] == 1:#向后找有没有相邻的
           cnt += 1
       else:
           break
    if cnt > ans2:#更新答案
        ans2 = cnt
        ans1 = arr[i]
    i += cnt#按照题解意思,我们后面需要查找的下标为i+cnt
print(ans1,end="")
print(",",end="")
print(ans2,end="")

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(",");
        List<Integer> arr = new ArrayList<>();
        for (String s : input) {
            arr.add(Integer.parseInt(s));
        }//处理输入
        Collections.sort(arr);//排序

        int i = 0;
        int ans1 = -1;
        int ans2 = -1;
        while (i < arr.size()) {//第一层循环
            int cnt = 1;
            for (int j = i + 1; j < arr.size(); j++) {//记录最大相邻数
                if (arr.get(j) - arr.get(j - 1) == 1) {//向后找有没有相邻的
                    cnt++;
                } else {
                    break;
                }
            }
            if (cnt > ans2) {//更新答案
                ans2 = cnt;
                ans1 = arr.get(i);
            }
            i += cnt;//按照题解意思,我们后面需要查找的下标为i+cnt
        }
        System.out.print(ans1 + ",");
        System.out.print(ans2);
    }
}

Go

package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

func main() {
	var input string
    fmt.Scanln(&input)
	arrStr := strings.Split(input, ",")
	arr := make([]int, len(arrStr))
	for i, numStr := range arrStr {
		arr[i], _ = strconv.Atoi(numStr)
	}//处理输入

	sort.Ints(arr)//排序
	i := 0
	ans1 := -1
	ans2 := -1
	for i < len(arr) {//第一层循环
		cnt := 1
		for j := i + 1; j < len(arr); j++ {//记录最大相邻数
			if arr[j]-arr[j-1] == 1 {//向后找有没有相邻的
				cnt++
			} else {
				break
			}
		}
		if cnt > ans2 {//更新答案
			ans2 = cnt
			ans1 = arr[i]
		}
		i += cnt//按照题解意思,我们后面需要查找的下标为i+cnt
	}
	fmt.Printf("%d,%d", ans1, ans2)
}

Js

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.question('', input => {
  const arr = input.split(',').map(Number);//处理输入
  arr.sort((a, b) => a - b);//排序

  let i = 0;
  let ans1 = -1;
  let ans2 = -1;
  while (i < arr.length) {//第一层循环
    let cnt = 1;
    for (let j = i + 1; j < arr.length; j++) {//记录最大相邻数
      if (arr[j] - arr[j - 1] === 1) {//向后找有没有相邻的
        cnt++;
      } else {
        break;
      }
    }
    if (cnt > ans2) {//更新答案
      ans2 = cnt;
      ans1 = arr[i];
    }
    i += cnt;//按照题解意思,我们后面需要查找的下标为i+cnt
  }
  console.log(`${ans1},${ans2}`);

  rl.close();
});

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

模拟

# Submissions

193

Accepted

Uploaded By

TaZi

2 solutions

题面描述

思路

题解

代码

CPP

python

Java

Go

Js

2023.05.24-暑期实习-第一题-连续内存合并

Information

Status

Development

Support