nev*_*ind 2 c c++ java algorithm stack
我正在努力解决这个问题:http://uva.onlinejudge.org/external/7/732.html.对于给定的示例,它们给我们原始单词,例如TRIT和目标"anagramed"字符串TIRT.
目标:我们必须输出所有有效的'i'和'o'序列(分别是push和pop),它们从源字符串中产生目标字符串.
所以,我正在考虑计算"i"和"o"的所有排列,但是要减少这种情况:
1)如果当前排列以'o'开始,则停止检查,因为所有下一个排列都将以此pop命令开始,并且从空堆栈中弹出一些东西是无效的命令.
2)如果在检查过程中发现'o'命令并且堆栈中没有任何内容,则跳过该情况.
3)如果找到'i'命令并且输入字符串中没有任何内容,则跳过该情况.
4)如果找到'o'命令并且当前预期的字符不是刚刚弹出的字符,则跳过该情况,因为这将永远不会到达目标字符串.
5)不要搜索输入和目标字符串是否有不同的长度.
但我认为无论如何它可能会让我TLE ......
我知道这个理论:也许是一种排列并且一直在回溯.我实施它有太多困难.
有谁可以请与我分享一些代码或想法吗？
PS:当然,欢迎任何可能减少执行时间的建议.
小智 9
这是一个有趣的问题,我相信下面的方法(find all trees which make the *from* string their preorder and the *to* string their inorder,下面有更多细节),如果正确实现将会非常快:比强力递归好得多,因为它只是"很容易"知道每个可能的子问题是什么步.
事实上,我做了一个小实验,并将其与给出的蛮力答案之一进行了比较.(注意:C#代码位于线程的底部).预订/订购的算法不是最佳的,实际上可以更好.当然,强力算法具有简洁的优点,并且对于较小尺寸的问题可能足够好(并且表现更好).
以下是结果.特别是对于较长字符串的最后两个结果,其中预订/顺序方法比蛮力快得多.处理的子问题数量之间存在巨大差异这一事实应该说服您,这不仅仅是由于数据,而是随着字符串变得更长(可能更多的重复字符),强力解决方案本身就必须处理更多不必要的子问题.使用蛮力解决方案进行任何记忆都是可能的,但似乎非常困难.
------------------------
bahama(Length:6)
bahama(Length:6)
PreorderInorder
TimeTaken: 00:00:00.0230000
Number of recursive calls: 20
Number of results returned: 4
Brute Force
TimeTaken: 00:00:00.0030000
Number of recursive calls: 47
Number of results returned: 4
------------------------
madameric(Length:9)
adammcire(Length:9)
PreorderInorder
TimeTaken: 00:00:00
Number of recursive calls: 28
Number of results returned: 4
Brute Force
TimeTaken: 00:00:00
Number of recursive calls: 107
Number of results returned: 4
------------------------
trittrottotr(Length:12)
tirttorttort(Length:12)
PreorderInorder
TimeTaken: 00:00:00.0010000
Number of recursive calls: 103
Number of results returned: 63
Brute Force
TimeTaken: 00:00:00.0010000
Number of recursive calls: 1301
Number of results returned: 63
------------------------
bahamabhahambahamamadambahamabhahambahama(Length:41)
bahamabhahambahamamadambahamabhahammahaba(Length:41)
PreorderInorder
TimeTaken: 00:00:01.1710000
Number of recursive calls: 2059
Number of results returned: 97472
Brute Force
TimeTaken: 00:00:18.2610000
Number of recursive calls: 41784875
Number of results returned: 97472
------------------------
bahamabhahambahamamadambahamabhahambahama(Length:41)
bahamabhahambahamamadambahamabhahambahama(Length:41)
PreorderInorder
TimeTaken: 00:00:00.1790000
Number of recursive calls: 315
Number of results returned: 20736
Brute Force
TimeTaken: 00:00:17.1680000
Number of recursive calls: 41062923
Number of results returned: 20736
对于较短的字符串,蛮力因为开销较小而获胜,但其他算法的速度确实显示字符串变长时.在任何情况下,对于较短的琴弦,您可以使用蛮力并切换到预订/订购方式以获得更长的琴弦以获得两全其美的效果.
现在,关于该方法的书面建议:
考虑以下树:
m
/ \
a m
/ \ / \
. d . .
/ \
. a
/ \
. .
在哪里.是空节点.
考虑一个预订单,您还可以输出空节点(点='.').
这给了我们预订: m a . d . a . . m . .
考虑有序,没有空节点,它是: a d a m m
现在考虑以下内容:
您需要预先订购:m a . d . a .. m .. 每次看到非空(或非点)时,都会进入堆栈.每次看到null(或点)时,都会弹出堆栈的顶部.您可以忽略最后一个.,因为这会导致弹出空堆栈.
我们可以手动运行它:
m a . d . a . . m .. | Stack = | Output =
Push m
a . d . a . . m .. | Stack = m | Output =
Push a
. d . a . . m .. | Stack = a m | Output =
Pop
d . a . . m .. | Stack = m | Output = a
Push d
. a . . m .. | Stack = d m | Output = a
Pop
a . . m .. | Stack = m | Output = a d
Push a
. . m .. | Stack = a m | Output = a d
Pop, Pop (sorry getting a little lazy)
m .. | Stack = | Output = a d a m
Push m, Pop
. | Stack = | Output = a d a m m.
现在将其输出与有序进行比较.它是一样的!
事实上,对于一般的二元树来说,这是正确的,可以使用归纳证明,并且是我们可以利用这个问题的树的一个很好的属性.
证明的简要草图:观察空节点数= 1 +非空节点数.这意味着当您完成弹出左侧树时,由于左侧树的最后一个空值而弹出根,因此所有这些推送和弹出都转换为(左)根(右).
因此,给定一个字符串A(像女士一样),你只需要使用推送和弹出转换为字符串B(如adamm),我们有以下方法解决问题:
Find all trees which have A as the preorder and B as the inorder
该树的预订,输出非空的推送和空节点的弹出(忽略最后一次推送)应该给出所需的序列.
找到预先订购/订购的树是一个标准问题,并有许多快速解决方案.对于这个问题,您可能只需稍微调整其中一个解决方案.
此外,这种方法的一些优点是
我猜你确实想编写自己的C/C++/Java代码,所以我将提供我拥有的C#原型代码.
StackAnagram.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SO
{
public class StackAnagram
{
public static int count = 0;
static Dictionary<string, Dictionary<string, List<string>>> memoized =
new Dictionary<string, Dictionary<string, List<string>>>();
public static List<string> Instructions(string from, string to)
{
count = 0;
if (from.Length != to.Length)
{
return new List<string>();
}
List<string> l = Instructions(from, 0, from.Length, to, 0, to.Length);
return l;
}
private static bool IsAnagram(string from, string to,
int startF, int endF, int startTo, int endTo)
{
Dictionary<char, int> d = new Dictionary<char, int>();
for (int i = startF; i < endF; i++)
{
if (d.ContainsKey(from[i]))
{
d[from[i]]++;
}
else
{
d[from[i]] = 1;
}
}
for (int i = startTo; i < endTo; i++)
{
if (d.ContainsKey(to[i]))
{
d[to[i]]--;
if (d[to[i]] == 0)
{
d.Remove(to[i]);
}
}
else
{
return false;
}
}
if (d.Count > 0)
{
return false;
}
return true;
}
private static List<string> Instructions(string from,
int startF, int endF, string to, int startTo, int endTo)
{
List<string> inst;
// Null tree.
if (startF >= endF || startTo >= endTo)
{
inst = new List<string>();
inst.Add("o ");
count++;
return inst;
}
string subFrom = from.Substring(startF, endF - startF);
string subTo = to.Substring(startTo, endTo - startTo);
Dictionary<string, List<string>> dict;
if (memoized.TryGetValue(subFrom, out dict))
{
if (dict.TryGetValue(subTo, out inst))
{
return inst;
}
}
else
{
memoized[subFrom] = new Dictionary<string, List<string>>();
}
count++;
inst = new List<string>();
if (!IsAnagram(from, to, startF, endF, startTo, endTo))
{
goto ret;
}
for (int j = 0; j < endTo - startTo; j++)
{
// Found possible root
if (from[startF] == to[startTo + j])
{
List<string> leftInst = Instructions(from, startF + 1,
startF + j + 1, to, startTo, startTo + j);
List<string> rightInst = Instructions(from, startF + j + 1,
endF, to, startTo + j + 1, endTo);
if (rightInst.Count <= 0)
{
continue;
}
foreach (string l in leftInst)
{
foreach (string r in rightInst)
{
inst.Add("i " + l + r);
}
}
}
}
ret:
memoized[subFrom][subTo] = inst;
return inst;
}
}
public class StackAnagramBrute
{
public static int count = 0;
static void anagram(String s1, String s2, String stack,
String instr, List<string> insts)
{
count++;
if (s2.Length == 0)
{
if (s1.Length == 0 && stack.Length == 0)
{
insts.Add(instr.Trim());
}
return;
}
if (!(s1.Length == 0))
{
anagram(s1.Substring(1), s2, s1[0] + stack, instr + "i ", insts);
}
if (!(stack.Length == 0) && stack[0] == s2[0])
{
anagram(s1, s2.Substring(1), stack.Substring(1), instr + "o ",
insts);
}
}
public static List<string> anagram(String s1, String s2)
{
count = 0;
if (s1.Length != s2.Length)
{
return new List<string>();
}
List<string> l = new List<string>();
anagram(s1, s2, "", "", l);
return l;
}
}
}
Program.cs中
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
namespace SO
{
class Program
{
static void Main(string[] args)
{
string[] from = { "bahama", "madameric", "trittrottotr",
"bahamabhahambahamamadambahamabhahambahama", "bahamabhahambahamamadambahamabhahambahama" };
string[] to = { "bahama", "adammcire", "tirttorttort",
"bahamabhahambahamamadambahamabhahammahaba", "bahamabhahambahamamadambahamabhahambahama" };
for (int i = 0; i < from.Length; i++)
{
CompareAlgorithms(from[i], to[i]);
}
}
static void CompareAlgorithms(string from, string to)
{
Console.WriteLine("------------------------");
Console.WriteLine(from + "(Length:" + from.Length + ")");
Console.WriteLine(to + "(Length:" + to.Length + ")");
DateTime start = DateTime.Now;
List<string> inst = StackAnagram.Instructions(from, to);
DateTime end = DateTime.Now;
TimeSpan t = end - start;
Display("PreorderInorder", t, StackAnagram.count, inst.Count);
DateTime startBrute = DateTime.Now;
List<string> instBrute = StackAnagramBrute.anagram(from, to);
DateTime endBrute = DateTime.Now;
TimeSpan tBrute = endBrute - startBrute;
Display("Brute Force", tBrute, StackAnagramBrute.count, instBrute.Count);
}
static void Display(string method, TimeSpan t, int callCount, int resultCount)
{
Console.WriteLine(method);
Console.Write("\t");
Console.Write("TimeTaken: ");
Console.WriteLine(t.ToString());
Console.Write("\t");
Console.Write("Number of recursive calls: ");
Console.WriteLine(callCount);
Console.Write("\t");
Console.Write("Number of results returned: ");
Console.WriteLine(resultCount);
}
}
}
第一个迭代解决方案是有益的.它不是最有效的,因为它使用了String所有的地方,但它是一个很好的起点.
import java.util.*;
public class StackAnagram {
static void anagram(String s1, String s2, String stack, String instr) {
if (s2.isEmpty()) {
if (s1.isEmpty() && stack.isEmpty()) {
System.out.println(instr.trim());
}
return;
}
if (!s1.isEmpty()) {
anagram(s1.substring(1), s2, s1.charAt(0) + stack, instr + "i ");
}
if (!stack.isEmpty() && stack.charAt(0) == s2.charAt(0)) {
anagram(s1, s2.substring(1), stack.substring(1), instr + "o ");
}
}
static void anagram(String s1, String s2) {
System.out.println("[");
anagram(s1, s2, "", "");
System.out.println("]");
}
public static void main(String args[]) {
anagram("madam", "adamm");
anagram("bahama", "bahama");
anagram("long", "short");
anagram("eric", "rice");
anagram("ericc", "rice");
}
}