Написание программы для поиска общего предка между двумя узлами BST. Не удалось распечатать в указанном ниже состоянии. Помогите мне найти решение [дублировать]

Ну, ".*" - жадный селектор. Вы делаете его неживым, используя ".*?". При использовании последней конструкции механизм регулярных выражений на каждом шаге соответствует тексту в "." попытке сопоставления с тем, что происходит после ".*?". Это означает, что если, например, ничего не происходит после ".*?", то оно ничего не соответствует.

Вот что я использовал. s содержит вашу исходную строку. Этот код специфичен для .NET, но большинство вариантов регулярного выражения будут иметь что-то подобное.

string m = Regex.Match(s, @"Project name: (?<name>.*?) J\d+").Groups["name"].Value;
174
задан iammilind 11 April 2013 в 08:30
поделиться

30 ответов

67
ответ дан Community 25 August 2018 в 16:49
поделиться
-1
ответ дан 2 revs 25 August 2018 в 16:49
поделиться
101
ответ дан arviman 25 August 2018 в 16:49
поделиться
0
ответ дан badri.coder 25 August 2018 в 16:49
поделиться
3
ответ дан bragboy 25 August 2018 в 16:49
поделиться
0
ответ дан Bridge 25 August 2018 в 16:49
поделиться
25
ответ дан CEGRD 25 August 2018 в 16:49
поделиться
1
ответ дан coder hacker 25 August 2018 в 16:49
поделиться
0
ответ дан Dreamer 25 August 2018 в 16:49
поделиться
0
ответ дан Gaurav Sinha 25 August 2018 в 16:49
поделиться
2
ответ дан gilla07 25 August 2018 в 16:49
поделиться
7
ответ дан Ha-eun Chung 25 August 2018 в 16:49
поделиться
0
ответ дан HeadAndTail 25 August 2018 в 16:49
поделиться
0
ответ дан iammilind 25 August 2018 в 16:49
поделиться
0
ответ дан janusbalatbat 25 August 2018 в 16:49
поделиться
5
ответ дан jason 25 August 2018 в 16:49
поделиться
1
ответ дан Jatin 25 August 2018 в 16:49
поделиться
1
ответ дан Krishnachandra Sharma 25 August 2018 в 16:49
поделиться
0
ответ дан Mark 25 August 2018 в 16:49
поделиться
0
ответ дан MWiesner 25 August 2018 в 16:49
поделиться
0
ответ дан Neelesh Salian 25 August 2018 в 16:49
поделиться
7
ответ дан Nick Johnson 25 August 2018 в 16:49
поделиться
0
ответ дан nnc 25 August 2018 в 16:49
поделиться
46
ответ дан Pratik Khadloya 25 August 2018 в 16:49
поделиться
2
ответ дан Rajnish 25 August 2018 в 16:49
поделиться
0
ответ дан Sameera R. 25 August 2018 в 16:49
поделиться

Неочищенный путь:

  • В каждом узле X = find, если любой из n1, n2 существует в левой части узла Y = find, если любой из n1, n2 существует на правая сторона узла, если сам узел равен n1 || n2, мы можем назвать это либо найденным слева, либо справа для целей обобщения. Если оба X и Y истинны, то узел является CA

. Проблема с вышеописанным методом заключается в том, что мы будем делать «нахождение» несколько раз, т. Е. Существует возможность каждый узел проходит несколько раз. Мы можем преодолеть эту проблему, если мы сможем записать информацию, чтобы не обрабатывать ее снова (подумайте о динамическом программировании).

Чтобы вместо этого найти каждый узел, мы сохраняем запись о том, что уже было найдено.

Лучший способ:

  • Мы проверяем, есть ли для данного узла, если left_set (что означает, что n1 | n2 найдено в левом поддереве) или right_set в глубине первая мода. (ПРИМЕЧАНИЕ. Мы даем самому корню свойство left_set, если оно либо n1 | n2)
  • Если и left_set, и right_set, то узел является LCA.

Код:

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}
0
ответ дан Shatru Sadhu 25 August 2018 в 16:49
поделиться
0
ответ дан Simon MᶜKenzie 25 August 2018 в 16:49
поделиться
0
ответ дан Sumit Trehan 25 August 2018 в 16:49
поделиться
5
ответ дан Vipin 25 August 2018 в 16:49
поделиться
Другие вопросы по тегам:

Похожие вопросы: