LeetCode 751. IP 到 CIDR

Categories:

题目描述
思路分析
1. 解法一：贪心分块（推荐）
相似题目

题目描述

✅ 751. IP 到 CIDR

思路分析

解法一：贪心分块（推荐）

核心思路：

把 IP 转为 32 位整数 start。

每次取能对齐的最大块 lowbit，再根据剩余数量缩小。

生成一个 CIDR 段后前移 start，减少 n，直到结束。

复杂度分析：

时间复杂度：O(log n)，每次至少覆盖一个块。

空间复杂度：O(1) 额外空间。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> ipToCIDR(String ip, int n) {
        List<String> res = new ArrayList<>();
        long start = ipToLong(ip);

        while (n > 0) {
            long lowbit = start & -start;
            if (lowbit == 0) {
                lowbit = 1L << 32;
            }

            while (lowbit > n) {
                lowbit >>= 1;
            }

            int prefix = 32 - Long.numberOfTrailingZeros(lowbit);
            res.add(longToIp(start) + "/" + prefix);
            start += lowbit;
            n -= (int) lowbit;
        }

        return res;
    }

    private long ipToLong(String ip) {
        String[] parts = ip.split("\\.");
        long num = 0;
        for (String part : parts) {
            num = num * 256 + Integer.parseInt(part);
        }
        return num;
    }

    private String longToIp(long num) {
        return ((num >> 24) & 255) + "." + ((num >> 16) & 255) + "." + ((num >> 8) & 255) + "." + (num & 255);
    }
}

import (
	"math/bits"
	"strconv"
	"strings"
)

func ipToCIDR(ip string, n int) []string {
	res := make([]string, 0)
	start := ipToLong(ip)

	for n > 0 {
		lowbit := start & -start
		if lowbit == 0 {
			lowbit = 1 << 32
		}

		for lowbit > int64(n) {
			lowbit >>= 1
		}

		prefix := 32 - bits.TrailingZeros64(uint64(lowbit))
		res = append(res, longToIp(start)+"/"+itoa(prefix))
		start += lowbit
		n -= int(lowbit)
	}

	return res
}

func ipToLong(ip string) int64 {
	parts := strings.Split(ip, ".")
	var num int64
	for _, part := range parts {
		val, _ := strconv.Atoi(part)
		num = num*256 + int64(val)
	}
	return num
}

func longToIp(num int64) string {
	return itoa(int(num>>24&255)) + "." + itoa(int(num>>16&255)) + "." + itoa(int(num>>8&255)) + "." + itoa(int(num&255))
}

func itoa(v int) string {
	if v == 0 {
		return "0"
	}

	buf := make([]byte, 0, 3)
	for v > 0 {
		buf = append(buf, byte('0'+v%10))
		v /= 10
	}

	for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
		buf[i], buf[j] = buf[j], buf[i]
	}

	return string(buf)
}

相似题目

题目	难度	考察点
467. 环绕字符串中唯一的子字符串	中等	数学
468. 验证IP地址	中等	字符串
405. 数字转换为十六进制数	简单	数学
7. 整数反转	中等	数学
171. Excel 表列序号	简单	进制转换

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/40765718