我目前正在为我的算法课做作业。指令摘要:
用户输入一个整数“n”来确定测试用例的数量。 用户单独输入另一个整数“num”以确定每个测试用例中元素的数量。 用户输入单个数组的元素。
算法必须处理数组并确定它是否可以划分为两个子序列，每个子序列都严格递增。如果结果是肯定的，程序打印"is"，否则打印“否”。
我有 24 小时的时间来完成这项任务，但我正在努力解决主要问题 - 我无法正确处理用户输入。 (想出一个算法来拆分两个子序列)
更新:我找到了这个解决方案。它通过了 4/5 测试，但在最后一次测试中未达到时间限制。
#include<iostream>
#include<string>
using namespace std;
bool run(){
int numbers;
int *arr;
cin >> numbers;
arr = new int[numbers];
for (int i = 0; i < numbers; i++)
cin >> arr[i];
long long int MAX = 0;
long long int MAX2 = 0;
string stra = "";
string strb = "";
string result = "";
string total = "";
long long int sum = 0;
for (int i = 0; i < numbers; i++){
if (arr[i] >= MAX && arr[i] != arr[i - 1]){
stra += to_string(arr[i]);
MAX = arr[i];
}
else
if (arr[i] >= MAX2 && MAX2 != MAX){
strb += to_string(arr[i]);
MAX2 = arr[i];
}
}
for (int i = 0; i < numbers; i++){
result = to_string(arr[i]);
total += result;
}
long long int len1 = stra.length();
long long int len2 = strb.length();
sum += len1 + len2;
delete[] arr;
if (sum != total.length())
return false;
else
return true;
}
int main()
{
int test;
cin >> test;
while (test > 0)
{
if (run())
cout << "Yes\n";
else
cout << "No\n";
test--;
}
system("pause");
}
示例输入:
2
5
3 1 5 2 4
5
4 8 1 5 3
示例输出: 是的 否
解释:对于数组 3 1 5 2 4，两个严格递增的子序列是:3 5 和 1 2 4。
最佳答案
似乎存在至少三个元素的任何相等或递减子序列意味着数组不能分成两个子序列，每个子序列都严格递增，因为一旦我们将第一个元素放在一部分中，第二个元素在另一部分，我们没有地方放置第三个。
这似乎表明找到最长递减或相等子序列是一个确定的解决方案。因为我们只需要长度为 3 的一个，所以如果每个元素的左边有一个更大或相等的元素，我们可以在 O(n) 中记录它。然后执行相反的操作。如果任何元素在左侧有一个更大或相等的伙伴，在右侧有一个更小或相等的伙伴，则答案为“否”。
我们可以通过沿值和位置绘图来可视化 O(n) 时间、O(1) 空间方法:
A choosing list B here
A x would be wrong
x
value B z
^ B x
| x
| A
| x
|
| B
| x
- - - - - - - -> position
我们注意到，一旦建立了第二个列表(第一次减少)，到目前为止任何高于绝对最大值的元素都必须分配给包含它的列表，而任何低于它的元素都可以在任何情况下，如果有的话，只放在第二个列表中。
如果我们要将一个高于绝对最大值的元素分配给第二个列表(不包含它)，我们可以通过使下一个元素低于我们刚刚插入的元素来任意构造假阴性第二个列表和前一个绝对最大值，但大于第二个列表的前一个最大值(图中的 z)。如果我们正确地将高于先前绝对最大值的元素插入到第一个列表中，我们仍然有空间将新的任意元素插入到第二个列表中。
(下面的 JavaScript 代码在技术上使用 O(n) 空间来显示分区，但请注意我们只依赖于每个部分的最后一个元素。)
function f(A){
let partA = [A[0]];
let partB = [];
for (let i=1; i<A.length; i++){
if (A[i] > partA[partA.length-1])
partA.push(A[i]);
else if (partB.length && A[i] <= partB[partB.length-1])
return false;
else
partB.push(A[i]);
}
return [partA, partB];
}
let str = '';
let examples = [
[30, 10, 50, 25, 26],
[3, 1, 5, 2, 4],
[4, 8, 1, 5, 3],
[3, 1, 1, 2, 4],
[3, 4, 5, 1, 2],
[3, 4, 1],
[4, 1, 2, 7, 3]
];
for (e of examples)
str += JSON.stringify(e) + '\n' + JSON.stringify(f(e)) + '\n\n';
console.log(str);
关于c++ - 确定一个数组是否可以分成两个子序列，每个子序列的顺序都是递增的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54762557/
类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc
我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代
我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby数组，我们在StackOverflow上找到一
使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta
我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]
我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何
我想要做的是有2个不同的Controller，client和test_client。客户端Controller已经构建，我想创建一个test_clientController，我可以使用它来玩弄客户端的UI并根据需要进行调整。我主要是想绕过我在客户端中内置的验证及其对加载数据的管理Controller的依赖。所以我希望test_clientController加载示例数据集，然后呈现客户端Controller的索引View，以便我可以调整客户端UI。就是这样。我在test_clients索引方法中试过这个:classTestClientdefindexrender:template=>
查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html
exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby中使用两个参数异步运行exe吗？我已经尝试过ruby命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何rubygems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server