小景哥哥

世界很大,而我们还需要再成长!

强烈推荐

44.翻转单词顺序列

    44.翻转单词顺序列

    题目描述

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


    public class Solution {
        //利用java中String函数,简单明了
        public String ReverseSentence1(String str) {
            if(str.trim().isEmpty())
                return str;
            String[] temp = str.split(" ");
            String res = "";
            int i = temp.length - 1;
            for(; i > 0; i--){
                res = res + temp[i] + " ";
            }
            return res + temp[0];
        }
        //利用剑指offer上思想,两次反转字符串
        public String ReverseSentence(String str) {
            if(str.trim().isEmpty())
                return str;
            char[] c = str.toCharArray();
            Reverse(c, 0, c.length - 1);
            int pBegin = 0, pEnd = 0;
            while(pBegin < c.length){
                if(c[pBegin] == ' '){
                    pBegin++;
                    pEnd++;
                }else if(c[pEnd] == ' '){
                    Reverse(c, pBegin, pEnd - 1);
                    pBegin = ++pEnd;
                }else if(pEnd == c.length - 1){
                    Reverse(c, pBegin, pEnd);
                    pBegin = ++pEnd;
                }else
                    pEnd++;
            }
            return String.valueOf(c);
        }
        public static void Reverse(char[] c, int begin, int end){
            if(begin >= end)
                return;
            while(begin < end){
                char temp = c[begin];
                c[begin] = c[end];
                c[end] = temp;
                begin++;
                end--;
            }
        }
        
    }

    阅读全文>>

作者:Jason分类:【offer浏览(201评论(0

2018-08-24

52.正则表达式匹配

    52.正则表达式匹配

    题目描述

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


    public class Solution {
        //剑指offer书上算法思想
        public boolean match(char[] str, char[] pattern)
        {
            if(str.length <= 0 && pattern.length <= 0)
                return true;
            
            return matchCore(str,pattern,0, 0);
        }
        
        public static boolean matchCore(char[] str, char[] pattern, int s, int p){
            if(s == str.length && p == pattern.length)
                return true;
            if(s != str.length && p == pattern.length)
                return false;
            //处理遇到*的情况
            if(p + 1 < pattern.length && pattern[p + 1] == '*'){
                if((s != str.length && pattern[p] == str[s]) || (pattern[p] == '.' && s != str.length)){
                    return matchCore(str, pattern, s, p + 2)//相当于*匹配零个,模式串上移动两个
                        || matchCore(str, pattern, s + 1, p);//字符串上移动一个,模式上保持不变
                }else{
                    return matchCore(str, pattern, s, p + 2);
                }
            }
            //两个字符相等,或者匹配.
            if((s != str.length && pattern[p] == str[s]) || (pattern[p] == '.' && s != str.length))
                return matchCore(str, pattern, s + 1, p + 1);
            return false;
        }
        
        //投机取巧法
        public boolean match2(char[] str, char[] pattern){
            String regex = String.valueOf(pattern);
            String s = String.valueOf(str);
            return s.matches(regex);
        }
    }

     

    阅读全文>>

作者:Jason分类:【offer浏览(225评论(0

2018-08-24

51.构建乘积数组

    51.构建乘积数组

    题目描述

    给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
     


    import java.util.ArrayList;
    public class Solution {
        //暴力解决
        public int[] multiply1(int[] A) {
            int[] B = new int[A.length];
            for(int i = 0; i < A.length; i++){
                int temp = 1;
                for(int j = 0; j < B.length; j++){
                    if(i != j){
                        temp *= A[j];
                    }
                }
                B[i] = temp;
            }
            return B;
        }
        //剑指offer上算法思想,时间复杂度O(n)
        public int[] multiply(int[] A){
            int length = A.length;
            int[] B = new int[length];
            if(length != 0 ){
                B[0] = 1;
                //计算下三角连乘
                for(int i = 1; i < length; i++){
                    B[i] = B[i-1] * A[i-1];
                }
                int temp = 1;
                //计算上三角
                for(int j = length-2; j >= 0; j--){
                    temp *= A[j+1];
                    B[j] *= temp;
                }
            }
            return B;
        }
    }

     

    阅读全文>>

作者:Jason分类:【offer浏览(224评论(0

2018-08-24