狂暴复习之路20160611 String I

344	Reverse String

public String reverseString(String s) {
    return new StringBuilder(s).reverse().toString();
}

哈哈 开玩笑的，下面这个才是。 也可以写递归。

public String reverseString(String s) {
    char[] temp = s.toCharArray();
    for (int i = 0; i <temp.length/2 ; i++) {
        char x = temp[i];
        temp[i] = temp[temp.length-1-i];
        temp[temp.length-1-i] = x;
    }
    return new String(temp);
}

13	Roman to Integer

public int romanToInt(String s) {
    int result = 0;
    int iCount = 0;
    int vCount = 0;
    int xCount = 0;
    int lCount = 0;
    int cCount = 0;
    int dCount = 0;
    int mCount = 0;
    int ivCount = 0;
    int ixCount = 0;
    int xlCount = 0;
    int xcCount = 0;
    int cdCount = 0;
    int cmCount = 0;

    for (int i = 0; i < s.length();i++)
    {
        if (s.charAt(i) == 'I')
        {
            iCount++;
            if (i + 1 != s.length())
            {
                if (s.charAt(i + 1) == 'V')
                    ivCount++;
                if (s.charAt(i + 1) == 'X')
                    ixCount++;
            }

        } else if (s.charAt(i) == 'V')
        {
            vCount++;
        } else if (s.charAt(i) == 'X')
        {
            xCount++;
            if (i + 1 != s.length())
            {
                if (s.charAt(i + 1) == 'L')
                    xlCount++;
                if (s.charAt(i + 1) == 'C')
                    xcCount++;
            }
        } else if (s.charAt(i) == 'L')
        {
            lCount++;
        } else if (s.charAt(i) == 'C')
        {
            cCount++;
            if (i + 1 != s.length())
            {
                if (s.charAt(i + 1) == 'D')
                    cdCount++;
                if (s.charAt(i + 1) == 'M')
                    cmCount++;
            }
        } else if (s.charAt(i) == 'D')
        {
            dCount++;
        } else if (s.charAt(i) == 'M')
        {
            mCount++;
        }
    }
    result = iCount + 5 * vCount + 10 * xCount + 50 * lCount + 100 * cCount
            + 500 * dCount + 1000 * mCount - 2*ivCount - 2* ixCount - 20*xlCount-20*xcCount
            - 200* cdCount - 200*cmCount;
    return result;
}

没啥可说的，按位扫描。

12
Integer to Roman

这个更没意思。

public String intToRoman(int num) {
    String result = "";
    int t = num/1000;
    int h = (num-t*1000)/100;
    int d = (num-t*1000-h*100)/10;
    int u = num-t*1000-h*100-d*10;
    if (num>0&&num<=3999)
    {
        result =
                numberToRoman(t,'M','*','*') +
                        numberToRoman(h,'C','D','M') +
                        numberToRoman(d,'X','L','C') +
                        numberToRoman(u,'I','V','X');
    }
    else    {
        result = null;
    }
    return result;
}

public String numberToRoman(int num, char o, char f, char t)
{
    String result = "";

    switch (num)
    {
        case 0:
        {
            break;
        }
        case 1:
        {
            result = result + o;
            break;
        }
        case 2:
        {
            result = result + o + o;
            break;
        }
        case 3:
        {
            result = result + o + o + o;
            break;
        }
        case 4:
        {
            result = result + o + f;
            break;
        }
        case 5:
        {
            result = result + f;
            break;
        }
        case 6:
        {
            result = result + f + o;
            break;
        }
        case 7:
        {
            result = result + f + o + o;
            break;
        }
        case 8:
        {
            result = result + f + o + o + o;
            break;
        }
        case 9:
        {
            result = result + o + t;
            break;
        }

    }
    return result;
}

22
Generate Parentheses

其实我觉得这道题更应该放到DFS里面

public List<String> generateParenthesis(int n)
{
    if (n <= 0)
        return null;
    ArrayList<String> list = new ArrayList<String>();
    String str = new String();
    dfs(list, str, n, n);
    return list;
}

private void dfs(ArrayList<String> list, String str, int left, int right)
{
    if (left > right)
        return;
    if (left == 0 && right == 0)
    {
        list.add(str);
    }
    if (left > 0)
        dfs(list, str + "(", left - 1, right);
    if (right > 0)
        dfs(list, str + ")", left, right - 1);
}

345
Reverse Vowels of a String

public String reverseVowels(String s) {
    char[] c = s.toCharArray();
    int l = 0;
    int r = c.length-1;
    while(l < r)
    {
        while (!val(c[l])&&l<r)
        {
            l++;
        }
        while (!val(c[r])&&l<r)
        {
            r--;
        }
        char temp = c[l];
        c[l] = c[r];
        c[r] = temp;
        l++;
        r--;
    }
    return new String(c);
}
public boolean val(char c)
{
    if (c=='a'||c=='A'||c=='e'||c=='E'||c=='i'||c=='I'||c=='o'||c=='O'||c=='u'||c=='U')
        return true;
    else        return false;
}
其实写的不太好，应该封装一个直接找出来的算法，稍微有点冗余。


20
Valid Parentheses

public boolean isValid(String s) {
    Stack<Character> stack = new Stack();
    if (s==null||s.length()==0)
        return true;
    char[] temp = s.toCharArray();
    char poped = ' ';
    for (char c:temp)
    {
        switch (c)
        {
            case '(':{ stack.push(c);break;}
            case '[':{ stack.push(c);break;}
            case '{':{ stack.push(c);break;}
            case ')':{ if (stack.size()==0||stack.pop()!='(') return false;break;}
            case ']':{ if (stack.size()==0||stack.pop()!='[') return false;break;}
            case '}':{ if (stack.size()==0||stack.pop()!='{') return false;break;}
        }
    }
    return stack.size()==0?true:false;
}

利用栈，如果是前括号入栈，后括号出栈，并判断符号的正确性。

38	Count and Say

public String countAndSay(int n) {
    String temp = "1";
    for (int i = 1; i <n ; i++) {
        temp = nextString(temp);
    }
    return temp;
}
public String nextString(String s)
{
    int num = 1;
    char cur = s.charAt(0);
    StringBuilder bs = new StringBuilder();
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i)==cur)
            num++;
        else        {
            bs.append(num);
            bs.append(cur);
            cur = s.charAt(i);
            num=1;
        }
    }
    bs.append(num);
    bs.append(cur);
    return bs.toString();
}

这题应该放到dp那里去，典型的简单dp问题。

58
Length of Last Word

public int lengthOfLastWord(String s) {
    if (s==null||s.length()==0)
        return 0;
    String[] temp = s.split(" ");
    if (temp.length==0)
        return 0;
    return temp[temp.length-1].length();
}