小编Lan*_*AOH的帖子

在计算机科学中,据说哈希表的插入,删除和搜索操作具有O(1)的复杂度,这是最好的.所以,我想知道,为什么我们需要使用其他数据结构,因为散列操作如此之快？为什么我们不能简单地使用哈希/哈希表来处理所有事情？

我试图解决这个算法问题:

https://dunjudge.me/analysis/problems/469/

为方便起见,我总结了下面的问题陈述.

给定包含[0,1,000,000]范围内的整数的长度(<= 2,000,000)数组,找到包含多数元素的最长子数组.

多数元素被定义为在长度为n的列表中发生> floor(n/2)次的元素.

时间限制:1.5秒

例如:

如果给定的数组是[1,2,1,2,3,2],

答案是5,因为从位置1到5(0索引)的长度为5的子阵列[2,1,2,3,2]具有数字2,其显示3> floor(5/2)次.请注意,我们不能采用整个数组,因为3 = floor(6/2).

首先想到的是一个明显的暴力(但正确)解决方案,它解决了子阵列的起始和结束索引并循环遍历它以检查它是否包含多数元素.然后我们采用包含多数元素的最长子阵列的长度.这在O(n ^ 2)中工作,具有小的优化.显然,这不会超过时限.

我还想把元素分成包含排序顺序的索引的桶.

使用上面的示例,这些桶将是:

1:0,2

2:1,3,5

3:4

然后对于每个桶,我会尝试将索引合并在一起以找到包含k作为多数元素的最长子阵列,其中k是该桶的整数标签.然后我们可以在k的所有值上取最大长度.我没有尝试这个解决方案,因为我不知道如何执行合并步骤.

编辑:

由于PhamTrung和hk6279的答案,我解决了这个问题.虽然我接受了PhamTrung的答案,因为他首先提出了这个想法,但我强烈建议你看一下hk6279的答案,因为他的回答详细阐述了PhamTrung的想法并且更详细(并且还附带了一个很好的正式证据!).

数组A []仅包含'1'和'-1'

构造数组B,其中B [i]是从j开始并在i结束的最长连续子阵列的长度,其中 j < i and A[j] + .. + A[i] > 0

明显的O(n ^ 2)解决方案是:

for (int i = 0; i < A.size(); ++i) {
    j = i-1;
    sum = A[i];
    B[i] = -1; //index which fills criteria not found
    while ( j >=0 ) {
        sum += A[j];
        if (sum > 0)
            B[i] = i - j + 1;
        --j;
    }
}

我正在寻找O(n)解决方案.

我用python解决了SPOJ的大输入测试问题，遇到了一个很奇怪的现象。我 使用 PyPy 和 Python 2提交了相同的代码。结果如下所示：

正如预期的那样，与 CPython 相比，使用 PyPy 的代码运行速度要快得多。但与此同时，内存使用量增加了惊人的 7 倍！我在网上进行了搜索，但找不到任何证据表明 PyPy 的内存使用量远远超过 CPython。有人可以解释一下内存使用量的巨大差异吗？

我也考虑过这可能是因为我的代码。因此，我在下面发布了我的代码：

import io, sys, atexit, os
sys.stdout = io.BytesIO()
atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))
sys.stdin = io.BytesIO(sys.stdin.read())
raw_input = lambda: sys.stdin.readline().rstrip()

line = list(map(int,raw_input().split()))
num, k = line
ans = 0

for i in xrange(0,num):
    if int(raw_input())%k == 0:
        ans += 1;

print(ans) 

有人可以建议我吗？

鉴于以下问题:

有一个k整数序列,名为s,可以有2个操作,

1)Sum [i,j] - s [i] + s [i + 1] + ... + s [j]的值是多少？

2)更新[i,val] - 将s [i]的值更改为val.

我相信这里的大多数人都听说过使用累积频率表/ fenwick树来优化复杂性.

现在,如果我不想查询总和,而是我想执行以下操作:

乘积[i,j] - s [i]*s [i + 1]*...*s [j]的值是多少？

新问题起初似乎微不足道,至少对于第一次操作Product [i,j].

假设我使用名为f的累积产品表:

1. 在首先想到的,当我们调用更新[我,VAL] ,我们应该划分累积性的产品F [Z]为z的我- >Ĵ通过的旧值S [I]然后乘以新的价值.

2. 但是如果s [i]的旧值为0,我们将面临2个问题:

   • 除以0.但是通过检查s [i]的旧值是否为0可以很容易地解决这个问题.

   • 任何实数为0的乘积为0.此结果将导致从f [i]到f [j]的所有其他值为0.因此我们无法成功执行Update [i,val].这个问题并不是那么微不足道,因为它会影响f [i]以外的其他值. …

我创建了一个程序来尝试对列表数据结构的语义进行练习。我注意到以下代码段有一个怪异的区别：

第一个代码：

#include<iostream>
#include<list>

using namespace std;

int main() {
    list<int> l;
    int n = 100;
    for(int i = 0; i < n; i++) {
        l.push_back(i);
    }
    list<int>::iterator it = l.end();
    it--;
    for(; !l.empty(); it--) {
        cout << "the size of l is " << (int) l.size() << endl;
        l.erase(it);
    }
}

第二个代码：

#include<iostream>
#include<list>

using namespace std;

int main() {
    list<int> l;
    int n = 100;
    for(int i = 0; i < n; i++) {
        l.push_back(i);
    }
    list<int>::iterator it …

我从许多来源读到,如果使用一种天真的方式来获得最小元素(线性搜索),Dijkstra的最短路径也将以O(V ^ 2)复杂度运行.但是,如果使用优先级队列,它可以优化为O(VLogV),因为此数据结构将在O(1)时间内返回min元素,但在删除min元素后需要O(LogV)时间来恢复堆属性.

我已经在以下代码中通过以下代码实现了Dijkstra的算法:https://uva.onlinejudge.org/index.php？option = com_onlinejudge&Itemid = 8&category = 16&page = show_problem&issue_1927 :

#include<iostream>
#include<vector>
#include <climits>
#include <cmath>
#include <set>

using namespace std;

#define rep(a,b,c) for(int c=a;c<b;c++)

typedef std::vector<int> VI;
typedef std::vector<VI> VVI;

struct cmp {
    bool operator()(const pair<int,int> &a,const pair<int,int> &b) const {
        return a.second < b.second;
    }
};

void sp(VVI &graph,set<pair<int,int>,cmp> &minv,VI &ans,int S,int T) {
    int e = -1;
    minv.insert(pair<int,int>(S,0));
    rep(0,graph.size() && !minv.empty() && minv.begin()->first != T,s) {
        e = minv.begin()->first;
        minv.erase(minv.begin());
        int nb …

我已经成功地完成了一个迷宫的最短路径算法（见下面的代码）。但是，我想将最短路径的坐标存储到传递给我的函数的 Stack 参数中。有人可以告诉我如何实现这一目标吗？这是我正在研究的迷宫：

图例：1：墙，0：有效路径，s：开始，e：结束

String[][] map = new String[][]
     {
             new String[] { "1","1","1","0","0","0","1","1","1","1" },
             new String[] { "s","0","0","0","1","1","0","0","0","1" },
             new String[] { "1","1","0","0","1","0","0","1","0","1" },
             new String[] { "1","1","1","0","0","0","0","0","0","1" },
             new String[] { "1","0","1","1","1","0","1","1","0","1" },
             new String[] { "0","0","0","0","0","0","0","0","0","1" },
             new String[] { "0","1","1","1","1","1","1","1","1","1" },
             new String[] { "0","0","0","0","0","0","0","0","0","e" },
     };

我的算法：

// Pre-condition: Two integers indicating the row and col number to start from,
// a 2d array of string objects representing the map of the maze,
// a …

我是C++的初学者.据我所知,为了使用名称,我们必须包含由该名称组成的库.此后,我们可以预先添加命名空间的名称或使用using关键字.

例如

不使用关键字:

std::cout << "Hello Word!" << std::endl;

使用关键字:

using namespace std;
cout << "Hello World!" << endl;

我在网上看到了一个使用isalpha名称空间中locale库名称的在线代码示例std.但是,该样本不使用上述任何方法.

例如

#include <iostream>
#include <locale>
int main() {
  std::cout << isalpha('a') << std::endl;
}

有人可以向我解释为什么代码仍然有效吗？