小景哥哥

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

强烈推荐

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浏览(180评论(0

2018-08-24

1035. 插入与归并(25)-浙大PAT乙级真题java实现

     

    1035. 插入与归并(25) 
    根据维基百科的定义: 
    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。 
    归并排序进行如下迭代操作:首先将原始序列看成N个只包含1个元素的有序子序列,然后每次迭代归并两个相邻的有序子序列,直到最后只剩下1个有序的序列。 
    现给定原始序列和由某排序算法产生的中间序列,请你判断该算法究竟是哪种排序算法? 
    输入格式: 
    输入在第一行给出正整数N (<=100);随后一行给出原始序列的N个整数;最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。 
    输出格式: 
    首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序;然后在第2行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔,且行末不得有多余空格。 
    输入样例1: 
    10 
    3 1 2 8 7 5 9 4 6 0 
    1 2 3 7 8 5 9 4 6 0 
    输出样例1: 
    Insertion Sort 
    1 2 3 5 7 8 9 4 6 0 
    输入样例2: 
    10 
    3 1 2 8 7 5 9 4 0 6 
    1 3 2 8 5 7 4 9 0 6 
    输出样例2: 
    Merge Sort 
    1 2 3 8 4 5 7 9 0 6


    阅读全文>>

作者:Jason分类:【pat浏览(191评论(0

2018-01-23

28.数组中出现次数超过一半的数字

    28.数组中出现次数超过一半的数字

    题目描述

    数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。



    import java.util.Arrays;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            if(array.length <= 0)
                return 0;
            if(array.length == 1)
                return array[0];
            Arrays.sort(array);
            int length = array.length;
            if(length % 2 == 0 && array[length / 2 - 1] == array[length / 2]){
                return array[length / 2];
            }else if(length % 2 == 1 && array[length / 2] == array[length / 2 + 1])
                return array[length / 2];
            else 
                return 0;
        }
    }

    //方法二,基于快速排序算法思想

        public int MoreThanHalfNum_Solution(int[] array) {

            if (array == null || array.length == 0)

                return 0;

            int middle = array.length >> 1;

            int start = 0;

            int end = array.length - 1;

            int index = Partition(array, start, end);

     

            while (index != middle) {

                if (index > middle) {

                    end = index - 1;

                    index = Partition(array, start, end);

                } else {

                    start = index + 1;

                    index = Partition(array, start, end);

                }

            }

            int result = array[middle];

            if (!CheckMoreThanHalf(array, result))

                result = 0;

            return result;

        }

     

        public static boolean CheckMoreThanHalf(int array[], int number) {

            int times = 0;

            for (int i = 0; i < array.length; ++i) {

                if (array[i] == number)

                    times++;

            }

            boolean isMoreThanHalf = true;

            if (times * 2 <= array.length) {

                isMoreThanHalf = false;

            }

            return isMoreThanHalf;

        }

     

        public static int Partition(int array[], int start, int end) {

            int pivotkey = (int) start + (int) Math.random() * (end - start);

            while (start < end) {

                while (start < end && array[end] >= array[pivotkey])

                    end--;

                int temp = array[start];

                array[start] = array[end];

                array[end] = temp;

                while (start < end && array[start] <= array[pivotkey])

                    start++;

                temp = array[start];

                array[start] = array[end];

                array[end] = temp;

            }

            return start;

        }

    阅读全文>>

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

2018-08-23

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浏览(175评论(0

2018-08-24

27.字符串的排序

    27.字符串的排序

    题目描述

    输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

    输入描述:

    输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

     

    //字典生成算法

        public ArrayList<String> Permutation(String str) {

            ArrayList<String> res = new ArrayList<>();

     

            if (str != null && str.length() > 0) {

                char[] seq = str.toCharArray();

                Arrays.sort(seq); // 排列

                res.add(String.valueOf(seq)); // 先输出一个解

     

                int len = seq.length;

                while (true) {

                    int p = len - 1, q;

                    // 从后向前找一个seq[p - 1] < seq[p]

                    while (p >= 1 && seq[p - 1] >= seq[p])

                        --p;

                    if (p == 0)

                        break; // 已经是“最小”的排列,退出

                    // 从p向后找最后一个比seq[p]大的数

                    q = p;

                    --p;

                    while (q < len && seq[q] > seq[p])

                        q++;

                    --q;

                    // 交换这两个位置上的值

                    swap(seq, q, p);

                    // 将p之后的序列倒序排列

                    reverse(seq, p + 1);

                    res.add(String.valueOf(seq));

                }

            }

     

            return res;

        }

     

        public static void reverse(char[] seq, int start) {

            int len;

            if (seq == null || (len = seq.length) <= start)

                return;

            for (int i = 0; i < ((len - start) >> 1); i++) {

                int p = start + i, q = len - 1 - i;

                if (p != q)

                    swap(seq, p, q);

            }

        }

     

        public static void swap(char[] cs, int i, int j) {

            char temp = cs[i];

            cs[i] = cs[j];

            cs[j] = temp;

        }

        

        //递归实现

        public ArrayList<String> Permutation2(String str) {

            ArrayList<String> res = new ArrayList<>();

     

            if (str != null && str.length() > 0) {

                PermutationHelper(str.toCharArray(), 0, res);

                Collections.sort(res);

            }

     

            return res;

        }

     

        private static void PermutationHelper(char[] cs, int i, ArrayList<String> list) {

            if(i == cs.length - 1) { //解空间的一个叶节点

                list.add(String.valueOf(cs)); //找到一个解

            } else {

                for(int j = i; j < cs.length; ++j) {

                    if(j == i || cs[j] != cs[i]) {

                        swap(cs, i, j);

                        PermutationHelper(cs, i + 1, list);

                        swap(cs, i, j); //复位

                    }

                }

            }

        }

    阅读全文>>

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

2018-08-23

1045. 快速排序(25)-浙大PAT乙级真题java实现

    1045. 快速排序(25) 
    著名的快速排序算法里有一个经典的划分过程:我们通常采用某种方法取一个元素作为主元,通过交换,把比主元小的元素放到它的左边,比主元大的元素放到它的右边。 给定划分后的N个互不相同的正整数的排列,请问有多少个元素可能是划分前选取的主元? 
    例如给定N = 5, 排列是1、3、2、4、5。则: 
    1的左边没有元素,右边的元素都比它大,所以它可能是主元; 
    尽管3的左边元素都比它小,但是它右边的2它小,所以它不能是主元; 
    尽管2的右边元素都比它大,但其左边的3比它大,所以它不能是主元; 
    类似原因,4和5都可能是主元。 
    因此,有3个元素可能是主元。 
    输入格式: 
    输入在第1行中给出一个正整数N(<= 105); 第2行是空格分隔的N个不同的正整数,每个数不超过109。 
    输出格式: 
    在第1行中输出有可能是主元的元素个数;在第2行中按递增顺序输出这些元素,其间以1个空格分隔,行末不得有多余空格。 
    输入样例: 

    1 3 2 4 5 
    输出样例: 

    1 4 5


    分析:对原序列sort排序,逐个比较,排序前后元素没有变化,并且它左边的所有值的最大值都比它小的时候它一定是主元。


    阅读全文>>

作者:Jason分类:【pat浏览(249评论(0

2018-01-24

61.序列化二叉树

    61.序列化二叉树

    题目描述

    请实现两个函数,分别用来序列化和反序列化二叉树
    算法思想:根据前序遍历规则完成序列化与反序列化。所谓序列化指的是遍历二叉树为字符串;所谓反序列化指的是依据字符串重新构造成二叉树。依据前序遍历序列来序列化二叉树,因为前序遍历序列是从根结点开始的。当在遍历二叉树时碰到Null指针时,这些Null指针被序列化为一个特殊的字符“#”。另外,结点之间的数值用逗号隔开。


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public int index = -1;
        public String Serialize(TreeNode root) {
            StringBuffer sb = new StringBuffer();
            if(root == null){
                sb.append("#,");
                return sb.toString();
            }
            sb.append(root.val + ",");
            sb.append(Serialize(root.left));
            sb.append(Serialize(root.right));
            return sb.toString();
            
       }
        public TreeNode Deserialize(String str) {
            index++;
            int len = str.length();
            if(index >= len)
                return null;
            String[] strr = str.split(",");
            TreeNode node = null;
            if(!strr[index].equals("#")){
                node = new TreeNode(Integer.valueOf(strr[index]));
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            }
            return node;
       }
    }
    阅读全文>>

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

2018-08-25

刻意人生

    当说到完美人生的时候,肯定不是说咸鱼翻身,升职加薪,当上总经理,出任CEO,迎娶白富美,走上人生巅峰,获得完美人生。人生在世,一帆风顺的人生是不存在的也是没有意义的。但是当我们刻意去追寻一种我们想要的生活时,就能在刻意努力中获得趋于完美的结局,这是一个正态均匀分布。

    完美人生并不是风平浪静的享受,刻意完美即完整,体验过美好也体验过苦涩,懂得付出也乐于享受,经历过风风雨雨也热衷于平平淡淡,Be a man who has known human joys and sorrows, and has achieved whatever work it was in him to do.

    我们的普世价值观好像都是倾向于完美,上完美的大学,找完美的爱人,做完美的工作……我们每个人都不是十全十美的,我们经历过的事儿,说过的话也不是完美的,所以注定会完美地落空。刻意是一种态度,刻意去追求一种精神境界,即使达不到你想要的高度,但也会在这个过程中趋于心中的目标极点,就像函数收敛无限接近的时候,那和完美没什么两样,就如100%和99.99%的概念是一样的,根据概率论的中心大数定理,不管你用切比雪夫大数定理还是用辛钦大数定理,我们可以用99.99%的概率来模拟描述那个真切的100%,极大似然估计并不是完全没有意义的啊。

    情怀不分贵贱,生活没有高低。人生不在于你出发的时候有多糟糕,也不在于你在人生的前一阶段有多糟糕,而在于你在你想优雅的活着的时候,刻意付出的代价与努力,即使脚在淤泥里,心也要向光明。虽然有句催人心寒的古话说,努力了不一定成功,(你放心,我肯定不会说不努力一定失败),可是根据bayes概率统计模型,我们知道,你成功的概率在你努力的前提下,那是极大的提高啊,条件概率就是定理啊,定理是啥?定理就是无需证明的真理!即使你不相信贝叶斯,那你总要相信马尔科夫吧,马尔科夫链式法则告诉我们,你前面步骤的概率越大,累加起来的概率也是越大的啊,即使你说你不懂,但是你肯定听说过马尔科夫数据模型,要不人口增长我们怎么预测,家喻户晓的马尔科夫是现实中真真切切的真理啊,比马克思还真。

    很多时候,我们总是,持续性的混吃等死,间接性的踌躇满志。我们的普世价值观好像在什么时候出现了不可描述的问题,可我们还浑然不知,就像温水煮青蛙,最后已经被现实蒙骗而不自知。我是一个非常接地气的人,平时说话都是趴着那种,所以我说的话都是妇孺皆知的大白话,即使像RNN这样的网络都知道要借鉴先前的数值来描述当下的模型,而且还会把当下的权值和偏移量传递下去,那我们岂不是也是一样的么?不要因为害怕遍体鳞伤,而拒绝了本可以实现的飞翔。你不刻意改变,没人为你坚强!虽然别人有背景,可是你有刻意努力的背影啊。舒适感是成长最大的敌人,而痛苦才是成长的标志。最好的投资就是投资现在,迎接未来。尽你所能,刻意seize the moment,就像死亡诗社里的罗宾·威廉姆斯一样,心中的珍惜时间刻意追求的意识从未泯灭。

    其实刻意人生就像数学,你不知道现在是微积分还是离散数学,就在你觉得连续性高涨的时候,社会就在不经意间离散了你的人生三观。当你还在纠结命题逻辑不知道怎么表达自己的时候,有些人早已开始了自己的归纳和推理,更有甚者已经开始了反证。其实每个人的一生都是一个函数,你把自己的努力作为定义域,映射出来的不一定是指数增长,也有可能是一个笛卡尔函数,其丰富性和灵活性就在于,婉转回旋的方程,总比你一个符号函数那样来的丰富和热烈。刻意的人生就在于其迂回蜿蜒,要是每个人都简简单单平平凡凡,那我们还费尽心思研究人生算法的复杂度干嘛?世界的丰富性就在于,有的人活的很自在,时间复杂度不是n的平方,也不是指数增长,而是对数递减,这就好比是你在sigmoid的时候,我早已构建出了消除梯度消失的Relu优化函数。

    我愿刻意生活,刻意改变,用我的归纳和递归,找到我自己的KMP匹配算法,来书写我的泰勒收敛函数展开式的刻意人生。

     

     

     

    阅读全文>>

作者:Jason分类:【人生浏览(320评论(0

2018-04-10