44. 反转单词序列

简单模拟

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

题意分析

题意是反转单词的顺序。“ ”时返回“ ”。

public class Solution {

    public String ReverseSentence(String str) {

        if (str.trim().equals(""))

            return str;//句子由空白字符组成时，原句返回

        String[] strs = str.split("\\s");

        StringBuilder ans = new StringBuilder();

        for (int i = strs.length - 1; i >= 0; i--) {

            ans.append(strs[i]);

            if (i != 0) ans.append(" ");

        }

        return ans.toString();

    }

}

49. 把字符串转换为整数++

模拟，细节，原码，补码

题目描述

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。不考虑指数表达形式。只有 int 范围内的数值合法

输入描述:

输入一个字符串,包括数字字母符号,可以为空。

输出描述:

如果是合法的数值表达则返回该数字，否则返回0

示例1

输入

+2147483647

   1a33

输出

2147483647

   0

题意分析

要考虑要如下问题：

1. 输入可能为空
2. 符号位可能存在
3. 溢出的处理

尤其要考虑以下特殊情况，由于计算机负数采用补码形式，所以 n 位的有符号数的范围是 $ [-2^n-1,2n-1] $，因此，当n = 8时，表示范围就是[-128, 127]，但是如果我们只是记录符号位和数值的绝对值的话，-128的绝对值128会溢出，因此，我们记录数值而非绝对值，并且在程序中加入上下溢出预检查。

Java Code

public class Solution {

    public int StrToInt(String str) {

        if (str == null || str.length() == 0) return 0;

        int neg = 1;// -1 表示为负数

        char first = str.charAt(0);

        int ans = 0, idx = 0;

        if (IsAlphaNumber(first)) ans = first - '0';

        else if (first != '-' && first != '+') {

            return 0;

        }// 字符非法

        else {

            if (str.length() == 1) return 0;//只有符号位即非法

            if (first == '-') neg = -1;

            first = str.charAt(++idx);

            if (!IsAlphaNumber(first)) return 0;//符号位后不是数字即非法

            ans = (first - '0') * neg;// ans中存了第一位数*neg

        }

        idx++;

        // 至此，idx指向了第1个数字之后的字符，ans中存了第一位数*neg

        if (str.length() - idx > 9) return 0;

        while (idx < str.length()) {

            char c = str.charAt(idx);

            if (IsAlphaNumber(c)) {

                int y = c - '0';

                // 如果会产生溢出则非法

                if (neg == 1 && ans * 10 > Integer.MAX_VALUE - y)

                    return 0;

                else if (neg == -1 && ans * 10 < Integer.MIN_VALUE + y)

                    return 0;

                ans = ans * 10 + neg * y;

            } else return 0;

            idx++;

        }

        return ans;

    }

    private boolean IsAlphaNumber(char c) {

        return c >= '0' && c <= '9';

    }

}

52. 正则表达式匹配 ++++

正则表达式，递归，动态规划

题目描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

题意分析

题目中要考虑到比较多的状态转移情况，最复杂的是可能当遇到 abbba 和 ab*bba匹配这种情况时，由于 b*可以匹配 0 个或1 个甚至多个b，要对三种匹配情况分别进行讨论，看三种匹配情况下，后面的字符串是否能继续成功匹配。由此我们可以看出，这里需要将整个字符串是否能匹配的大问题分解成当前匹配情况影响下后面的字符串是否能继续匹配的子问题，需要递归求解。

另一种思路是动态规划。由上面递归解法的分析可知，当前位置字符串匹配问题的子问题是字符串后面部分能否匹配，状态转移的影响因素是当前b*可以匹配 0 个、1 个还是多个b。因此我们可以设置状态 dp[i][j]为str[i:length-1] 与pattern[j:len-1]匹配，从后往前进行状态更新。

public class Solution {

    public boolean match(char[] str, char[] pattern)

    {

        if(str==null || pattern==null)return false;

        return matchHelper(str,pattern,0,0);

    }

    public boolean matchHelper(char[] str,char[] ptn,int p1,int p2){

        if(p2>=ptn.length && p1>=str.length)return true;// ptn无 str无

        if(p2>=ptn.length && p1=str.length){// ptn有 str无，判断ptn是否为(a*)这种组合

            int i=p2+1;

            while(i 

public class Solution {

    public boolean match(char[] str, char[] pattern) {

        if (str == null || pattern == null) return false;

        char[] pt = pattern;

        boolean[][] dp = new boolean[str.length + 1][pt.length + 1];

        dp[str.length][pt.length] = true;// 统一操作

        for (int i = str.length; i >= 0; i--) {// 子串从空开始

            for (int j = pt.length - 1; j >= 0; j--) {// 模式串从非空开始

                if (pt[j] != '*') {

                    dp[i][j] = i != str.length && dp[i + 1][j + 1]

                            && (pt[j] == '.' || pt[j] == str[i]);

                } else {

                    j--;

                    if (i == str.length)

                        dp[i][j] = j == pt.length - 1 || dp[i][j + 2];

                    else if (pt[j] == '.' || pt[j] == str[i]) {// 匹配0个或多个

                        int ii = i;

                        while (ii 

public class Solution {

    public boolean isNumeric(char[] str) {

        String string = String.valueOf(str);

        return string.matches("[\\+-]?[0-9]+(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?")||

                string.matches("[\\+-]?(\\.[0-9]*)(([eE][\\+-]?[0-9]+)?)");

    }

    /*

         为什么是两个反斜杠

         首先字符串中的\\被编译器解释为\ ,然后作为正则表达式，\.又被正则表达式引擎解释为. 如果在字符串里只写\.的话，第一步就被直接解释为.，之后作为正则表达式被解释时就变成匹配任意字符了

     */

}

public class Solution {

    int [] loc=new int[256];

    int id=1;

    //Insert one char from stringstream

    public void Insert(char ch)

    {

        if(loc[ch]==0)loc[ch]=id;

        else loc[ch]=-1;

        id++;

    }

  //return the first appearence once char in current stringstream

    public char FirstAppearingOnce()

    {

        char ans='#';

        int minid=id;

        for(int i=0;i  0 && loc[i]