logo标签列表

判断一个数组是否可以分成两个子序列，每个子序列都是递增顺序

c++arraysalgorithmdynamic-programming
4
我目前在算法课的作业问题上遇到了困难。指令概述如下：
用户输入整数'n'来确定测试用例的数量。 用户单独输入另一个整数'num'来确定每个测试用例中的元素数量。 用户输入各个数组的元素。
该算法必须处理数组并确定它是否可以被分成两个子序列，每个子序列都是严格递增的。如果结果为正，则程序打印"Yes"，否则打印"No"。
我有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。

1
你正在使用变长数组，这在C++中是不存在的，而且NumOfTestCases和n都还没有初始化。请打开编译器警告并使用std::vector。 - Quentin
你正在嵌套循环中使用for(int i...)，内层循环隐藏了外层循环。请使用不同的变量 - 我建议您在外部循环中使用变量i_test_case，在内部循环中使用变量i_element代替i。 - Sigi
一个单元素部分被认为是“严格递增”的吗？ - גלעד ברקן
{3,4}和{1}是{3,4,1}的有效分割吗？ - גלעד ברקן
在我的回答中添加了关于O(1)空间算法的解释。 - גלעד ברקן
显示剩余4条评论
4个回答
5
似乎存在任何至少有三个元素的相等或递减子序列，都意味着数组无法被分成两个严格递增顺序的子序列，因为一旦我们把第一个元素放在一个部分中，把第二个元素放在另一个部分中，我们就没有地方可以放第三个元素了。
这似乎表明找到最长的递减或相等子序列是一个确定的解决方案。因为我们只需要长度为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);

这个观察结果可以用来证明贪心的“只在必要时切换”算法对于分割列表总是有效的，因为当它失败时总是违反这个条件。这导致了一个类似于@schorsch312提出的O(n)算法，但也证明了这个条件是足够的。因此，使用前缀和后缀最大/最小值找到这些三元组的简单O(n)算法也完全可以工作。 - Matt Timmermans
你可以将元素添加到一个列表中，直到找到一个不大于前一个元素的元素。然后切换到另一个列表。如果在另一个列表中它也不大于前一个元素，则表示找到了一个非递增三元组。继续向新列表中添加元素，直到再次被迫切换，以此类推。 - Matt Timmermans
啊，你说得对。我忘记了初始列表不是通过开关创建的。不过我仍然认为你的条件已经足够了。 - Matt Timmermans
1
证明是Dilworth定理，加上适当的决胜规则：https://en.m.wikipedia.org/wiki/Dilworth%27s_theorem - David Eisenstat
1
具体而言，将其应用于二维偏序（位置、值），其中我们扰动相等的值，使得后面的值比前面的值小。 - David Eisenstat
显示剩余6条评论
1

我会遍历整个数组并检查两个最大值。如果实际的数组值小于这两个最大值，那么它是不可能的，否则适当的最大值会增加。

如果在分裂条件之前违反了条件，算法就不必遍历整个数组。

这是我的代码

#include <algorithm>
#include <iostream>
#include <vector>

bool isAddable(const int item, int &max1, int &max2) {
    if (max2 > item) {
        return false;
    }
    else {
        if (max1 > item) {
            max2 = item;
        }
        else {
            max1 = item;
        }
        return true;
    }
}

void setStartValue(int &max1, int &max2, const std::vector<int> &vec) {
    max1 = *std::min_element(vec.begin(), vec.begin() + 3);
    max2 = *std::max_element(vec.begin(), vec.begin() + 3);
}

bool isDiviableIntoTwoIncreasingArrays(const std::vector<int> &vec) {
    if (vec.size() < 3) {
        return true;
    }

    int max1, max2;
    setStartValue(max1, max2, vec);

    for (int i = 2; i < vec.size(); ++i) {
        if (max1 > max2) {
            if (!isAddable(vec[i], max1, max2)) {
                return false;
            }
        }
        else {
            if (!isAddable(vec[i], max2, max1)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    std::vector<int> userVec;
    int tmp1;
    while (std::cin >> tmp1) {
        userVec.emplace_back(tmp1);
    }

    const std::vector<int> v1{3, 1, 5, 2, 4};
    const std::vector<int> v2{4, 8, 1, 5, 3};
    const std::vector<int> v3{3, 4, 1};
    for (const std::vector<int> &vec : {userVec, v1, v2, v3}) {
        if (isDiviableIntoTwoIncreasingArrays(vec)) {
            std::cout << "Yes\n";
        }
        else {
            std::cout << "No\n";
        }
    }
}
如何使用向量而不是数组设置用户输入过程？ - Rupert
@גלעדברקן 很好的建议，我已经更正了启动参数。谢谢！ - schorsch312
@Rupert 请查看此帖子 https://stackoverflow.com/questions/33298505/c-populating-a-vector-of-objects-with-user-input - schorsch312
@Rupert 我编辑了我的代码以启用用户输入。只要您输入一个整数，它就会被附加到用户向量中。如果您输入非整数（例如 q），则用户输入将结束。 - schorsch312
2
我认为你的代码对于 {3,1,1,2,4} 返回了一个错误的结果。 - גלעד ברקן
显示剩余4条评论
0

我认为你可以采用暴力解决方案。注意这里我使用了向量（我认为你也应该这样做）来存储数据，并使用递归来穷举所有可能的组合。记住问题，解决它，然后专注于像解析输入和匹配课程作业期望的数据输入方式等琐碎任务。我已经添加了行内注释，使其易于理解。

bool canPartition(vector<int>& nums) {
     if(nums.empty()) return false;

     vector<int> part1 = {}, part2 = {}; // two partitions

     auto ans = canPart(nums, part1, part2, 0); // pass this to our recursive function
     return ans;
   }

bool canPart(vector<int>& nums, vector<int>& part1, vector<int>& part2, int i)
{
    if(i >= nums.size()) // we are at the end of the array is this a solution?
    {
        if(!part1.empty() && !part2.empty()) // only if the partitions are not empty
        {
            //if you want you could print part1 and part2 here 
            //to see what the partition looks like
            return true;
        }

        return false;
    }

    bool resp1empty = false, resp2empty = false, resp1 = false, resp2 = false;    

    if(part1.empty()) // first partition is empty? lets add something
    {
        part1.push_back(nums[i]);
        resp1empty = canPart(nums, part1, part2, i + 1);
        part1.pop_back(); // well we need to remove this element and try another one
    }

    else if(nums[i] > part1.back()) // first partition is not empty lets check if the sequence is increasing
    {
        part1.push_back(nums[i]);
        resp1 = canPart(nums, part1, part2, i + 1);
        part1.pop_back();
    }

    if(part2.empty()) // is partition two empty? lets add something
    {
      part2.push_back(nums[i]);
      resp2empty = canPart(nums, part1, part2, i + 1);
      part2.pop_back();
    }

    else if(nums[i] > part2.back()) // check if sequence is increasing
    {
      part2.push_back(nums[i]);
      resp2 = canPart(nums, part1, part2, i + 1);
      part2.pop_back();
    }

    //if any of the recursive paths returns a true we have an answer
    return resp1empty || resp2empty || resp1 || resp2;
}

现在你可以使用主函数来尝试一下：

vector<int> v = {3,1,5,2,4};
cout << canPartition(v);

关键是要制作一个小测试用例，添加一些非平凡的测试用例，解决问题，然后查看其他测试用例的输入解析。
0

  • 我认为这取决于您是否有选项让数字出现在第一个列表或第二个列表中。

  • 因此，我们将继续向列表1添加数字，如果无法添加任何元素，则将其作为新列表的开头。

  • 假设我们同时拥有两个列表。如果我们遇到一个元素，无法将其添加到任何列表中，我们将返回false。

  • 确实存在一种情况，我们可以将元素添加到任何2个列表中。在这种情况下，我们采用贪婪的方法来添加到哪个列表。

    • 我们准备了一个从右边开始的最小值数组。例如，对于[30,10,50,25,26]，我们将具有最小值数组[10,25,25,26,(空白)]。
    • 现在，让我们跟踪如何正确地将它们分成2个列表。
    • 30 => 列表A。
    • 10 => 列表B。（由于无法将其添加到第一个列表中，因此从此处开始创建新列表）
    • 50 => 列表A。
      • 在这里，50适用于在30或10之后。如果我们选择10，那么我们将无法容纳下一个25在任何2个列表中，因为我们的列表看起来像[30]和[10,50]。但是，如果我们将50添加到30中，并检查存储在最小值数组中的最小值，即25，则可以继续进行。
    • 25 => 列表B。
    • 26 => 列表B。
    • 因此，我们的最终列表是[30,50]和[10,25,26]。

  • 时间复杂度：O(n)，空间复杂度：O(n)，您也可以打印出这2个列表。

  • 如果我们遇到一个严格递增的排序数组，我们无论如何都会返回true。

我认为我们可以使用O(1)的空间。请看我的答案。 - גלעד ברקן
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接