小编srb*_*kmr的帖子

给定一个大小mxn仅为0和1的矩阵.我需要找到最大的子矩阵,其中包含相同数量的1和0.蛮力方法是O(m^2*n^2)我们可以做得比这更好吗？
我尝试应用动态编程,但找不到任何最佳子结构.

我相信这个问题的类似的一维版本在这里讨论:
用于寻找最大平衡子阵列的节省空间的算法？
它有一个O(n)使用一些额外空间的解决方案.

给出的问题:

如果字符串中的左括号和右括号可以正确配对,则称一串括号被平衡.例如,字符串"(())"和"()()"都是平衡的,而字符串"(()("不平衡.
给定长度为n的字符串S由括号组成,假设你想要找到平衡的S的最长子序列.使用动态编程,设计一种算法,在O(n ^ 3)时间内找到S的最长平衡子序列.

我的方法:
假设给定的字符串:S [1 2 ... n]
有效的子序列可以在S [i]结束,如果S [i] ==')'即S [i]是一个右括号并且存在在S [i]之前至少有一个未使用的开口支撑.可以在O(N)中实现.

#include<iostream>
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.length(), o_count = 0, len = 0;
    for(int i=0; i<n; ++i){
        if(s[i] == '('){
            ++o_count;
            continue;
        }
        else if(s[i] == ')' && o_count > 0){
            ++len;
            --o_count;
        }
    }
    cout << len << endl;
    return 0;
}

我尝试了几个测试用例,它们似乎工作正常.我在这里错过了什么吗？如果没有,那么我怎样才能为这个问题设计一个O(n …

我想优化我的程序的一部分,我计算二项式系数之和到K.即

C(N,0) + C(N,1) + ... + C(N,K)

由于值超出数据类型(long long)可以支持,我将计算值mod M 并且正在寻找执行此操作的过程.

目前,我已经用Pascal的Triangle完成了它,但似乎需要一点负担.所以,我想知道是否有其他有效的方法来做到这一点.我已经考虑过卢卡斯的定理,虽然MI已经足够大,所以C(N,k)失控了!

任何指针,如何以不同的方式做到这一点,也许可以用一些其他整齐的表达来计算总和.如果不是,我将把它与Pascal的Triangle方法本身一起留下.

谢谢,

这是我到目前为止O(N^2):

#define MAX 1000000007
long long NChooseK_Sum(int N, int K){
    vector<long long> prevV, V;
    prevV.push_back(1);     prevV.push_back(1);
    for(int i=2;i<=N;++i){
            V.clear();
            V.push_back(1);
            for(int j=0;j<(i-1);++j){
                    long long val = prevV[j] + prevV[j+1];
                    if(val >= MAX)
                            val %= MAX;
                    V.push_back(val);
            }
            V.push_back(1);
            prevV = V;
    }
    long long res=0;
    for(int i=0;i<=K;++i){
            res+=V[i];
            if(res >= MAX)
                    res %= MAX;
    }
    return res;
}

我有一个面试问题,我无法解决.

Java编程语言中的写方法(不是程序),它将在前半部分中将所有偶数移动到整数数组中的后半部分.

例如输入= {3,8,12,5,9,21,6,10}; 输出= {12,8,6,10,3,5,9,21}.

该方法应将整数数组作为参数并在同一数组中移动项目(不要创建另一个数组).数字可能与原始数组的顺序不同.这是算法测试,因此尽量提供尽可能高效的算法(可能是线性O(n)算法).避免使用内置函数/ API.*

还有一些基本介绍什么是数据结构效率

这是一个简单的程序,我写的是找到长度<= L的所有非递减数字的数字,其数字总和为N.代码工作正常,但是当我尝试使用来自ctime的clock()计时运行时间时,它显示了奇怪的行为.

#include<iostream> 
#include<vector> 
#include<ctime>
using namespace std;
typedef long long int LL;
    int Sum(LL S){
        int sum=0;
        for(;S;S/=10)
                sum+=S%10;
        return sum;
}
void Generate(LL S, int len, int N, int L, vector<LL> &V){
        if(len<L)
                for(int i=0;i<=9;++i)
                        if(i>=S%10)
                                Generate(S*10+i, len+1, N, L, V);
        int sum = Sum(S);
        if(sum!=N)
                return;
        else if(sum == N && len == L){
                V.push_back(S);
                cout << S << endl; //Line 4
                return;
        }
}
int main(){
        int N,L;
        vector<LL> V;
        LL S;
        cin >> N >> …