2

我需要从给定的输入字符串中找到词典上最大的字符串。所以如果输入是

enjoy

o/p 应该是

yenjo

我试过的代码是....

int n;
cout<<"Enter the number of strings";
cin>>n;
int len[n];
char str[n][1000];
for(int i=0;i<n;i++)
{
    cin>>str[i];
    len[i]=strlen(str[i]);
}
int num,pos[n];
for(int i=0;i<n;i++)
{
    pos[i]=0;
    num=int(str[i][0]);
    for(int j=1;j<len[i];j++)
    {
       if(int(str[i][j])>num)
        {
           num=int(str[i][j]);
           pos[i]=j;
       }   
    }    
}
int i,j,k;
char temp[1];
for(i=0;i<n;i++)
{
    for(j=0;j<pos[i];j++)
        {
        temp[0]=str[i][0];
        for(k=0;k<len[i];k++)
         {
            str[i][k]=str[i][k+1];
        }
        strcat(str[i],temp);
        str[i][len[i]]='\0';
    }
    cout<<str[i]<<"\n";
}
return 0;
}

但是这段代码只检查最大的数字，而不是它旁边的数字，因此 i/p 失败

blowhowler

o/p 应该是wlerblowho，但我得到 o/p 为whowlerblo.
我如何跟踪最大字符之前的每个元素以获得正确的输出？

4

7 回答 7

1

为了在平均情况下获得良好的性能（实际上是 O(N)），但在最坏的情况下仍然是 O^2（并且始终正确），您可以跟踪可能性，并随时消除它们。基本上是这样的。

struct PermSum
{
  int sum;
  int perm;
}

LinkedList<PermSum> L;

for(int i = 0; i != input.size(); ++i) L.append(PermSum{0,i});

int depth = 0;
int max = 0;
const int length = input.size()
while(L.size() > 1 && depth < length)
{
  for(l in L)
  {
    l.sum += input[(l.perm + depth) % length]
    if (l.sum > max) max = l.sum
  }

  for(l in L)
  {
    if (l.sum < max) L.delete(l)
  }
  depth ++;
}

if (L.size() == 1)
  return L.front().perm
else
  return -1

我在使用 c++ 代码的某些部分有点懒惰，但我相信你可以在 L 中找出 for l。关键行是第一个 for 循环。这个想法是它在 l.perm-th 排列的深度字母处添加字典值。通过这种方式，它会更新所有可能性，同时跟踪最佳可能性的级别。然后，您进行第二遍以删除任何未达到最佳效果的可能性。值得注意的是，我的编码方式可能与循环排列的标准约定相反。也就是说，我的程序中的 perm 字段表示循环移位左移多少个点，而通常正数是循环右移。您可以在某处用减号解决此问题。

至于运行时间分析，和Quickselect基本一样。每次 while 循环迭代所花费的时间与 L 的长度成正比。第一次迭代时，L 将始终具有长度 = N（其中 N 是字符串的长度，与代码中的可变长度相同）。下一轮，我们通常只期望 1/26 的数据通过，之后的一轮又是 1/26...所以我们有 N(1 + 1/26 + 2/26^2...)是 O(N)。

于 2014-09-18T01:35:48.000 回答
1

您可以： 1. 生成旋转 2. 将所有旋转放入 map<> 3. 找到地图的最后一个元素。这是 C++ 中的实现。

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

int main() {
    // your code goes here
    string str;int len,i=0,j=0,k=0;char temp;
    cin>>str;
    len = str.length();
    map<string,int>m;
    while(i<len)
    {
        temp = str[0];
        while(j<len-1)
        {
            str[j] = str[j+1];
            j++;
        }
        str[j] = temp;
        m[str] = k;
        k++;
        i++;j=0;
    }
    str = m.rbegin()->first;
    cout<<str;
    return 0;
}
于 2014-09-18T08:37:08.140 回答
1

通过首先将字符串附加到自身并从中构建后缀数组，可以在 O(n log n) 时间内解决该问题。找到相应的条目并在那里找到您想要的结果。实施留作练习。

于 2014-09-18T08:50:13.227 回答
1 
//Here the index with greater value is selected,
//if the same char occurs again the next characters
// of prev and curr characters is checked:-Prev=maxIndex,curr=i    
#include<bits/stdc++.h>
using namespace std;
int getIndex(char *str){
int max=INT_MIN,maxIndex;
int n=strlen(str);
int j,p;
for(int i=0;i<n;i++)
{
    if(str[i]>max)
    {
        max=str[i];
        maxIndex=i;
    }
    else if(str[i]==max)
    {
        j=maxIndex+1;
        p=(i+1)%n;
        while(j<n && p<n && str[j]==str[p]){
         j++;
         p=(p+1)%n;
        }
        maxIndex=str[p]>str[j]?i:maxIndex;
    }
}
return maxIndex;
}
int main(void)
{
char str[4000008];
scanf("%s",str);
int i=getIndex(str);
for(int j=i;j<strlen(str);j++)
cout<<str[j];
for(int j=0;j<i;j++)
cout<<str[j];



 }
于 2016-08-09T14:36:24.403 回答
0

此挑战用于活跃的比赛，我要求在 IST 9 月 18 日晚上 9 点之前不提供任何答案。因为代码是可见的，我们可能不得不禁止用户参与我们未来的任何比赛。

于 2014-09-18T12:38:48.327 回答
0

您的算法，更正后，归结为：

  1. 将当前最佳旋转设置为标识（旋转字符串的开始是当前索引 0）。
  2. 对于每个可能的旋转（所有其他起始索引）：
    1. 与当前最佳旋转相比，如下wrapcmp所示。
    2. 如果我们有更好的候选人，请设置当前最佳轮换。

时间复杂度：O(n*n)
空间复杂度：就地

// Function to do ordinal-comparison on two rotations of a buffer
// buffer: The buffer containing the string
// n: The buffers size (string-length)
// a: Index where the first buffer starts pre-rotation
// b: Index where the second buffer starts pre-rotation
int wrapcmp(const void* buffer, size_t n, size_t a, size_t b) {
    auto x = (const unsigned char*)buffer;
    auto m = n - std::max(a, b);
    int ret = memcmp(x+a, x+b, m);
    if(ret) return ret;
    auto left = n - m;
    a = (a + m) % n;
    b = (b + m) % n;
    m = left - std::max(a, b);
    ret = memcmp(x+a, x+b, m);
    if(ret) return ret;
    a = (a + m) % n;
    b = (b + m) % n;
    return memcmp(x+a, x+b, left - m);
}

在 coliru 上使用：http
://coliru.stacked-crooked.com/a/4b138a6394483447 将其放入通用算法中，作为读者练习。

于 2014-09-17T23:00:04.353 回答
0

这太诱人了，所以我不妨张贴我的努力。不确定它如何评价效率。据我测试它似乎有效：

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

std::string max_rot(const std::string& s)
{
    std::string tmp;
    std::string max;

    std::string::const_iterator m = std::max_element(s.begin(), s.end());
    if(m != s.end())
        for(char c = *m; (m = std::find(m, s.end(), c)) != s.end(); ++m)
            if(max < tmp.assign(m, s.end()).append(s.begin(), m))
                max = tmp;

    return max;
}


int main()
{
    size_t times = 0;
    std::string text;

    do { std::cout << "\nHow many words? : "; }
    while(std::getline(std::cin, text) && !(std::istringstream(text) >> times));

    std::vector<std::string> words;
    while(times-- && (std::cin >> text))
        words.push_back(text);

    for(const auto& s: words)
        std::cout << max_rot(s) << '\n';

}

以解释的方式。它找到字符串中的最高字符值并旋转字符串以使该字符首先出现。如果然后在跟踪最高尝试的字符串的其余部分中查找重复的最高字符。可能还有优化的空间。

于 2014-09-18T03:22:54.913 回答