题目：一个好汉三个帮，三个好汉九个帮，九个好汉二十七个帮，…停，今天不是让你算n个好汉几个帮（有兴趣的网友可以自己算），我们来看这个集合

{ 1, 3, 9, 27, 81, … }

这个集合是一个递增的无限集，每个元素都是3的幂。

我们把这个集合的所有子集按照元素和从小到大的顺序排好： {}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 }, { 1, 3, 9 }, …

现在给定一个正整数n，求第n个子集的所有元素，并按从大到小的顺序排列好

例：

n的值    结果
1        { }
4        { 3, 1 }
6        { 9, 1 }
500      { 6561, 2187, 729, 243, 81, 3, 1 }

题目：给出一个包含各种括号的表达式，判断括号是否配对。括号配对的条件：括号必须先左后右，并且左右括号数量相等；对于多重括号，从外到内嵌套顺序为：{} -> [] -> () -> <>。例如{[(<>)]}。

接口： bool match(char* str);   合法返回true， 否则返回false。

输入范例：
{[(<>)]}
{}
<(>)
<()>

返回：
true
true
false
false

来自编程爱好者编程比赛题。

Answer1#region Answer1

思路#region 思路

//为什么这道题是一个有趣的题目？我们看看下面的分析
//1-1的二进制是多少？0000，和答案相符
//4-1的二进制是多少？0011，那就是3^2和3
//6-1的二进制是多少？0101，那就是3^3和3
//看到没？求集合，只要看n-1的二进制位置和3的此方的关系即可
//如500就是，500-1的二进制111110011看看答案是不是题目给
//的所需要的答案呢？这就是技巧。。

#endregion

Code#region Code

namespace FindThree
…{
class Program
…{
static Queue<int> bin;
static List<int> result;

static void Main(string[] args)
…{
MainTest(0);
MainTest(1);
MainTest(4);
MainTest(5);
MainTest(500);
Console.ReadKey();
}

static void MainTest(int number)
…{
bin = new Queue<int>();
result = new List<int>();

//转换为二进制，用队列
ConvertToBin(number);

Queue<int> tempBin = bin;

//从队列弹出，分别计算立方的次数
//这里也可以从正面计算，然后反序
for (int i = tempBin.Count - 1; i >= 0; i–)
…{
result.Add((int)Math.Pow(3, i));
}

OutPutList();
}

转换成二进制#region 转换成二进制

static void ConvertToBin(int number)
…{
number = number - 1;

while (number / 2 > 0 && number > 0)
…{
int temp = number % 2;
number = number / 2;
bin.Enqueue(temp);
}

if (number > 0)
…{
bin.Enqueue(number % 2);
}
}

#endregion

其他的输出函数#region 其他的输出函数

static void OutPut()
…{
Queue<int> temp = bin;

while (temp.Count > 0)
…{
Console.Write(temp.Dequeue());
}
}

static void OutPutList()
…{
if (result.Count == 0)
…{
Console.WriteLine(“{}“);
return;
}

Console.Write(“{“);
for (int i = 0; i < result.Count; i++)
…{
Console.Write(result[i]);

if (i != result.Count - 1)
…{
Console.Write(“ “);
}
}
Console.Write(“}“);
Console.WriteLine();
}

#endregion
}
}

#endregion

#endregion

Answer2#region Answer 2

思路#region 思路
//网上看到很多人用两个栈去维护，一个为字符，一个为状态
//其实可以不用到栈

//语法检查
//先检查语法，分别按顺序赋值1，2，3，4（这里有技巧）
//然后看是否后面的括号的值小于前面的，如小于，语法错误

//匹配检查
//遍历字符串，分别给括号赋值，最后{赋值4，}赋值-4
//求最后的和如果为0则正确

#endregion

Code#region Code

namespace FindThings
…{
class Program
…{
static int a = 0; //{}
static int b = 0; //[]
static int c = 0; //()
static int d = 0; //<>

static void Main(string[] args)
…{
//Return True
MainTest(“{[(<>)]}“);
MainTest(“{[]}“);
MainTest(“{<><><>}“);
MainTest(“{<<>>}“);
MainTest(“{[<][>]}“);
MainTest(“{[][]()<>(<>)}{()}“);
Console.WriteLine(“———–“);
//Return False
MainTest(“{<(><)><>}“);
MainTest(“{[][]()<>(<>)(}“);
MainTest(“{[][]()<>(<>)}{<()>}“);
MainTest(“<(>)“);
MainTest(“<()>“);
MainTest(“{>]“);
Console.ReadKey();
}

static void MainTest(string str)
…{
a = 0;
b = 0;
c = 0;
d = 0;
bool isMatch = CheckGrammer(str);
Console.WriteLine(isMatch);
}

static bool CheckGrammer(string str)
…{
bool isMatch = true;
int last = GetValue(str[0]);
int value = last;

for (int i = 1; i < str.Length; i++)
…{
int tempNum = GetValue(str[i]);
//检查语法，如果后面有大于前面的，并且不为0
//并且当前的值与上一个的值和的和不为0，因为
//为0则抵消
if (tempNum < last && tempNum != 0 && tempNum + last != 0)
…{
isMatch = false;
break;
}

//计算表达式的值
value += tempNum;

//如果前面已经有成对的括号了，就返回原来的值
//如{[][]<，这时候到<这里的时候，值应该是{=-4
if (tempNum + last == 0)
…{
last = value;
}
else
…{
last = tempNum;
}
}
//值为0并且符号配对
if (value != 0 || a != 0 || b != 0 || c != 0 || d != 0)
…{
isMatch = false;
}

return isMatch;
}

//映射不同的值

static int GetValue(char c)
…{
//给相应的值匹配正负对，以便相加后抵消
switch (c)
…{
case ‘{‘: a++; return -4;
case ‘[': b++; return -3;
case '(': c++; return -2;
case '<': d++; return -1;
case '>': d--; return 1;
case ')': c--; return 2;
case ']‘: b–; return 3;
case ‘}‘: a–; return 4;
default: return 0;
}
}
}
}

#endregion

#endregion

以上代码纯属参考，欢迎讨论。