|
锁定老帖子 主题：华为面试题！
精华帖 (0) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (5)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-05-25
最后修改：2011-05-25
只针对题目而言，只需要有2个计数。从第一个字符读取到最后一个字符，记录当前'{'数量n，当前'}'数量m。只需要在读取每个字符时判断n>=m，并且最后一个字符n==m就可，不必太复杂的算法
|
| 返回顶楼 | |
|
发表时间：2011-05-25
最后修改：2011-05-25
public class Demo {
private String input;
private Stack<Character> stack;
private List<String> outputs;
public Demo(String in) {
if (in == null) {
throw new IllegalArgumentException("input not null");
}
this.input = in;
stack = new Stack<Character>();
outputs = new ArrayList<String>();
}
public List<String> doTrans() {
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
switch (ch) {
case '{':
stack.push(ch);
break;
case '}':
gotParen(ch);
break;
default:
stack.push(ch);
break;
}
}
return outputs;
}
public void gotParen(char ch) {
String output = "";
while (!stack.isEmpty()) {
char chx = stack.pop();
if (chx == '{') {
break;
} else {
output = chx + output;
}
}
outputs.add(output);
}
public static void main(String[] args) {
Demo demo1 = new Demo("{abc}");
for (String string : demo1.doTrans()) {
System.out.println(string);
}
System.out.println("--------------------------------------");
//
Demo demo2 = new Demo("{abc{123{999{}}}}");
for (String string : demo2.doTrans()) {
System.out.println(string);
}
System.out.println("--------------------------------------");
}
}
|
| 返回顶楼 | |
|
发表时间：2011-05-25
import java.util.Stack;
public class StackTest {
public static void main(String[] args) {
System.out.println(isMatch("{}"));
System.out.println(isMatch("{"));
System.out.println(isMatch("{kljdfj}}fj;fj"));
System.out.println(isMatch("{}}"));
System.out.println(isMatch("{{fdsfs}}{}"));
System.out.println(isMatch("}"));
}
public static boolean isMatch(final String str) {
boolean flag = false;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '{' && stack.size() == 0) {
stack.push(str.charAt(i));
continue;
}
if (str.charAt(i) != '}' && stack.size() != 0) {
stack.pop();
continue;
}
if (str.charAt(i) == '}' && stack.size() != 0) {
flag = true;
break;
}
}
return flag;
}
}
|
| 返回顶楼 | |
|
发表时间：2011-05-25
public static void match(String srt,String str1,String str2){
srt+="X"; int i = srt.split(str1).length-1; int j = srt.split(str2).length-1; if(i==j) System.out.println(str1+"与"+str2+"标签匹配成功"); else System.out.println(str1+"与"+str2+"标签匹配失败"); } |
| 返回顶楼 | |
|
发表时间：2011-05-25
当年我面试的时候就是考的这个东西，华为的面试题大部分是学校里的数据结构，编译原理的东西，呵呵
|
| 返回顶楼 | |
|
发表时间：2011-05-25
marshaldong 写道 涉及到什么什么匹配的问题，我就想到正则表达式，用这个很方便，下面是个例子：
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class TestCurlyBraces
{
private Pattern pattern = Pattern.compile("[^{}]*(\\{[^{}]*(\\{[^{}]*\\}[^{}]*)*\\}[^{}]*)*[^{}]*");
/**
* @param args
*/
public static void main(String[] args)
{
TestCurlyBraces instance = new TestCurlyBraces();
String input = "asda{asd{fsfsff}sdfab245}2{32}";
instance.match(input);
}
public void match(String input)
{
Matcher match = pattern.matcher(input);
if (match.matches())
System.out.println(match.group());
else
System.out.println("not matched.");
}
}
不过用正则表达式有个缺点，就是要明确嵌套的层数，因为无法写出匹配任意层的表达式来，这个就是不太通用，用stack就能做的通用。通过压栈({)和出栈(})，结合递归是个很好的解决方案。后续再分享下代码。 用递归把简单的问题搞复杂了，不必用递归，简单的方法就行： import java.util.LinkedList;
public class CurlyBracesMatcher
{
private LinkedList<Character> stack = new LinkedList<Character>();
/**
* @param args
*/
public static void main(String[] args)
{
CurlyBracesMatcher matcher = new CurlyBracesMatcher();
System.out.println(matcher.matches("{{{{}}a}a}"));
}
public boolean matches(String string)
{
if (string == null || string.length() == 0 || string.trim().equals(""))
return true;
int i = 0;
while (i < string.length())
{
char ch = string.charAt(i);
if (ch == '{')
{
stack.push(ch);
}
else if (ch == '}')
{
if (stack.isEmpty())
return false;
stack.pop();
}
i++;
}
if (!stack.isEmpty())
return false;
return true;
}
}
以前也想过这种问题，对以上解决方法比较认同！ |
| 返回顶楼 | |
|
发表时间：2011-05-25
考这种题，测不出技术水平！
|
| 返回顶楼 | |
|
发表时间：2011-05-26
最后修改：2011-05-26
考察数据结构的stack
public static boolean match(String expression) {
char[] array = expression.toCharArray();
LinkedList<Character> stack = new LinkedList<Character>();
for (int i = 0; i < array.length; i++) {
if (array[i] == '{') {
stack.addFirst(new Character(array[i]));
} else {
if (array[i] == '}') {
if (!stack.isEmpty()) {
stack.removeFirst();
} else {
return false;
}
}
}
}
if (!stack.isEmpty()) {
return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(match("}{{}=sdfds{}===={}}"));
}
|
| 返回顶楼 | |
|
发表时间：2011-05-26
最后修改：2011-05-27
仅仅是判断吗？我这个行不
public static boolean judge(String s) {
int i = 0;
for(int c :s.toCharArray())
if((i+=Math.abs(c-='|')==1?c:0)>0)
return false;
return i==0;
}
自己又想了想优化了下，这个代码更简单性能更好 public static boolean judge2(String s) {
int k =0,c,i=0,l=s.length();
for(;i<l&&k<=0;k+=(Math.abs(c=s.charAt(i++)-'|')==1?c:0));
return k==0;
}
沿用楼上的用例
System.out.println(judge("{}"));
System.out.println(judge("{"));
System.out.println(judge("{kljdfj}}fj;fj"));
System.out.println(judge("{}}"));
System.out.println(judge("{{fdsfs}}{}"));
System.out.println(judge("}"));
结果 true false false false true false |
| 返回顶楼 | |
|
发表时间：2011-05-26
最后修改：2011-05-26
我觉得华为考这样个题目还是蛮有用意的。
考察数据结构中的栈(stack) 在《java数据结构和算法》中第4章， “栈和队列”的栈部分的几个实例运用中有详细的源码。 |
| 返回顶楼 | |
