最长的字母子字符串-从哪里开始 [英] Longest alphabetical substring - where to begin

问题描述

我正在研究流行的MIT课程中的最长字母子串问题。我已经阅读了很多有关如何进行编码的信息，但是我真的很难从概念上进行跨越。在此之前的手指练习不太难。我想知道是否有人知道任何可以真正解决该问题的解决方法的材料。我试过拿出笔和纸，却迷路了。我看到人们使用各种各样的计数器，或者包含到目前为止最长的子字符串的字符串，当我看别人的解决方案时，我可以理解他们对他们的代码做了什么，但是如果我试图

I am working on the "longest alphabetical substring" problem from the popular MIT course. I have read a lot of the information on SO about how to code it but I'm really struggling to make the leap conceptually. The finger exercises preceding it were not too hard. I was wondering if anyone knows of any material out there that would really break down the problem solving being employed in this problem. I've tried getting out a pen and paper and I just get lost. I see people employing "counters" of sorts, or strings that contain the "longest substring so far" and when I'm looking at someone else's solution I can understand what they've done with their code, but if I'm trying to synthesize something of my own it's just not clicking.

我什至休息了一段时间，尝试通过其他书籍学习，但是我仍然回到这个问题上，觉得我需要突破。我想我正在苦苦挣扎的是从了解一些Python语法和工具跃升为真正地有机地使用这些工具来解决问题或计算的飞跃。

I even took a break from the course and tried learning via some other books, but I keep coming back to this problem and feel like I need to break through it. I guess what I'm struggling with is making the leap from knowing some Python syntax and tools to actually employing those tools organically for problem solving or "computing".

在有人向我指出之前，我知道旨在提供帮助的课程材料。我看过其中一个助教制作的视频有些帮助，但他并没有真正将其分解。我觉得我需要将程序与某人配对，或者……坐在白板前，让某人一步一步地走，回答我的所有愚蠢问题。

Before anyone points me towards it, I'm aware of the course materials that are aimed at helping out. I've seen some videos that one of the TAs made that are somewhat helpful but he doesn't really break this down. I feel like I need to pair program it with someone or like... sit in front of a whiteboard and have someone walk me step by step and answer every stupid question I would have.

作为参考，问题如下：

假设s是一个

Assume s is a string of lower case characters.

编写一个程序，该程序打印s的最长子串，其中字母按字母顺序出现。例如，如果s ='azcbobobegghakl'，则您的程序应打印

Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then your program should print

按字母顺序排列的最长子字符串为：beggh

Longest substring in alphabetical order is: beggh

如果是平局，则打印第一个子字符串。例如，如果s ='abcbcd'，则程序应打印

In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print

按字母顺序排列的最长子字符串为：abc

Longest substring in alphabetical order is: abc

我知道发布代码会很有帮助，但是我没有其他地方没有的东西，因为那是我在IDE中一直在玩的东西如果我能理解发生了什么。同样，不要寻找代码片段，更多的阅读内容或资源将扩展在此问题中使用的逻辑。我会发布我所拥有的内容，但还没有完成，这是我所知，直到我开始感到困惑为止。

I know that it's helpful to post code but I don't have anything that isn't elsewhere on SO because, well, that's what I've been playing with in my IDE to see if I can understand what's going on. Again, not looking for code snippets - more some reading or resources that will expand upon the logic being employed in this problem. I'll post what I do have but it's not complete and it's as far as I get before I start feeling confused.

s = 'azcbobobegghakl'

current = s[0]
longest = s[0]

for letter in range(0, len(s) -1):
    if s[letter + 1] >= s[letter]:
        current.append(s[letter + 1])
        if len(current) > len(longest):
            longest = current
        else:
            current = 

很抱歉出现格式化错误，这仍然是新问题。我对这个问题感到非常沮丧。

Sorry for formatting errors, still new to this. I'm really frustrated with this problem.

推荐答案

如果您在解决此问题的概念和逻辑上苦苦挣扎，建议您退一步，然后逐步解决。更简单的编码教程和互动练习。您可能还喜欢尝试JavaScript，从一开始就可以更轻松地获得创意，构建可与浏览器立即交互的代码片段和/或网页。然后，当您获得更多有趣的编码词汇时，其中的算法部分将显得更加熟悉自然。我也认为让自己的创造力和想象力引导您可以成为一个非常强大的学习过程。

If you are struggling with the concepts and logic behind solving this problem, I would recommend perhaps stepping back a little and going through easier coding tutorials and interactive exercises. You might also enjoy experimenting with JavaScript, where it might be easier to get creative right from the outset, building out snippets and/or webpages that one can immediately interact with in the browser. Then when you get more fun coding vocabulary under your belt, the algorithmic part of it will seem more familiar and natural. I also think letting your own creativity and imagination guide you can be a very powerful learning process.

暂时不要忘记字母部分。想象一下，我们有一袋书，我们一次抽出一个，却不知道接下来是哪一个，我们必须连续记录最长的 R s运行。你会怎么做？让我们尝试用文字来描述该过程，然后再用伪代码来描述。

Let's forget about the alphabetical part for the moment. Imagine we have a bag of letters that we pull out one at a time without knowing which is next and we have to record the longest run of Rs in a row. How would you do it? Let's try to describe the process in words, then pseudocode.

我们将保留一个容器以保持迄今为止最长的运行时间，另外一个容器将检查当前运行情况。我们拉字母，直到我们连续击中两个 R ，然后将其放入当前容器中。下一个字母不是 R ，这表示我们的运行已结束。 最长到目前为止运行为空，因此我们将当前容器倒入其中并继续。接下来的四个字母不是 R s，因此我们将其忽略。然后我们得到一个 R ，将其放入 current，然后一个 H 。我们的运行再次结束，但是这次我们在当前中的一个 R 小于我们在最长的中已经拥有的两个，因此我们将其保留为空当前。

We'll keep a container for the longest run we've seen so far and another to check the current run. We pull letters until we hit two Rs in a row, which we put it in the "current" container. The next letter is not an R, which means our run ended. The "longest-so-far" run is empty so we pour the "current" container in it and continue. The next four letters are not Rs so we just ignore them. Then we get one R, which we put in "current" and then an H. Our run ended again but this time our one R in "current" was less than the two we already have in "longest-so-far" so we keep those and empty "current."

我们得到一个 A ，一个 B 和 C ，然后运行五个 R s，我们将其放入当前容器中逐一。现在，我们的书包中包含最后一个字母，即 T 。我们看到运行再次结束，并且当前容器的容量超过了最长容器，因此我们倒出最长容器，并将其内容替换为五个 R s为当前。就是这样，我们在包中找到了运行时间最长的 R s。 （如果运行次数更多，则每次结束时，我们都会选择是否替换最长的内容。）

We get an A, a B, and a C, and then a run of five Rs, which we put into the "current" container one by one. Our bag now contains the last letter, a T. We see that our run ended again and that "current" container has more than the "longest-so-far" container so we pour out "longest" and replace its contents with the five Rs in "current." That's it, we found the longest run of Rs in the bag. (If we had more runs, each time one ended we'd choose whether to replace the contents of "longest-so-far.")

使用伪代码：

// Initialise
current <- nothing
longest <- nothing

for letter in bag:
  if letter == 'R':
    add 'R' to current
  else:
    if there are more letters
    in current than longest:
      empty longest and pour
      in letters from current
    otherwise:
      empty current to get ready
      for the next possible run

现在，按字母顺序的规定使我们的情况稍微复杂了一些。我们将需要跟踪放置在当前中的最新字母，并且为了继续运行，它不会看到同样重要的另一个字母。相反，下一个字母必须比我们当前放置的最后一个字母大（按字典顺序）；否则，运行将结束，我们将针对最长的时间执行数量检查。

Now the alphabetical stipulation just slightly complicates our condition. We will need to keep track of the most recent letter placed in "current," and in order for a run to continue, its not seeing another of the same letter that counts. Rather, the next letter has to be "greater" (lexicographically) than the last one we placed in current; otherwise the run ends and we perform our quantity check against "longest-so-far."

这篇关于最长的字母子字符串-从哪里开始的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！