讨论/技术交流/C:关于暴力解法申请数组的一些问题请教/
C:关于暴力解法申请数组的一些问题请教

Q0:在一个leetcode的题解程序里,可以申请多大的数组(常用的int类型,自定义的struct类型等等,怎么计算)?

#define MAX 50000
int array[MAX];

int DoSomethingBad()
{
    int *ret = (int*)malloc(sizeof(int) * MAX);
    printf("array[MAX - 1] = %d\n", array[MAX - 1]);
    printf("ret[MAX - 1] = %d\n", ret[MAX - 1]);

    free(ret);
    return 0;
}

Q1: 上面这里的 MAX 我最大可以设置多少?
Q2: 在这个题解的程序开头申请一个全局数组和在某个函数内用malloc申请堆内存有什么具体区别,最大能申请多少?
Q3:因为经常会在leetcode题解程序里先试一试用大数组暴力解,这个“大”在什么数量级就超出限制了?
Q4:关于题解程序外面的main函数调用框架和程序规格信息在哪里可以查看?

上述问题,望诸君解惑,细说之

1
共 2 个回复

Q1: 通常情况下,申请的全局数组和数据范围有关,例如给定数据范围为10000 那么可能申请一个int a[10010] 这么大的数组。
这应该和题目的内存/数据范围限制相关。

Q2: 区别在于malloc可以根据每次输入数据规模确定申请的大小,全局数组大小则需要设定在题目数据范围的上界。 比如给定一道题,数据的上界是1e5,但是当前数据量是1e3, 则可以通过manloc 申请1e3的数组。但是如果用全局数组的话,必须要1e5 (要考虑所有测试用例)。

Q3: leetcode 好像没有说明内存限制。通常不爆出 Memory Limit Exceed 超出内存限制 的都是可以的。

Q4: 可以看一看leetcode 做题时编辑器右上角的playground , python语言是有的,如下:


class Solution(object):
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """

def stringToInt2dArray(input):
    return json.loads(input)

def main():
    import sys
    def readlines():
        for line in sys.stdin:
            yield line.strip('\n')
    lines = readlines()
    while True:
        try:
            line = lines.next()
            matrix = stringToInt2dArray(line)
            
            ret = Solution().isToeplitzMatrix(matrix)

            out = (ret)
            print out
        except StopIteration:
            break

if __name__ == '__main__':
    main()
1

层主说的不错,补充一些个人经验,
1.申请超过10^7到10^8的数组就很危险了
2.全局数组是static的。一般可以这么用:申请一次,初始化多次。这样题跑起来一般比从heap上malloc要快。在没有-o2之前这是个大坑。LC没有开源测试代码。对于C,它无非就是include了你写的代码或者link了你的实现。LC调用定了接口的函数,跑完所有样例,测试的应该是所有样例的总时间。