刷leetCode算法题+解析（五）

闲聊两句，说一句很可怕的事情，昨天做的几道题，今天早晨再看了一遍，发现并没有完全记住，居然还是想了几分钟做了几个测试才再次通关。不知道是我的记忆力差了还是大家都这样，挺受伤的反正。继续刷题吧。

实现 strStr()

题目：实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

这个题怎么说呢，是指在不用已经封装好的方法的情况下实现indexOf（）的功能。题目没什么好解释的了。说 我自己的思路吧。
思路：首先判断包含关系的原串要长于子串，其次子串为空返回0，再其次因为不知道从原串那个字符开始的，所以要逐个判断，所以要遍历原串。反正大概是这样，接下来上代码（我一直习惯于代码中的注释很墨迹）

    public int strStr(String haystack, String needle) {
        int len = needle.length();
        //题目要求，子串是空串直接返回0
        if(len == 0){
            return 0;
        }
        //遍历原串开始比较，加入原串长10，要匹配的长5，只要判断到第五个是不是匹配，再往后不用判断了，因为长度不够了
        for(int j =0;j<haystack.length()-len+1;j++){
            //这个是作为needle的下标的，从0开始
            int i = 0;
            //一个字符一个字符的匹配
            while(haystack.charAt(j+i)==needle.charAt(i)){
                i++;
                //走到这说明needle的每一个字符都匹配完了，并且都匹配上了
                if(i==len){
                    //返回第一个下标，也就是j
                    return j;
                }
            }
        }
        return -1;        
    }

解析上大多说什么KMP，BM，Horspool，反正我数学的底子仅限于初中，这些是什么也都不知道，反正用自己的方法实现了功能了。

搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0、

思路：这个没啥说的，反正我第一版很简单的就写完了。代码逻辑也清楚：

    public int searchInsert(int[] nums, int target) {
        for(int i = 0;i<nums.length;i++){
            if(nums[i]>=target){
                return i;
            }
        }
        //走到这说明所有的元素都没这个插入元素大，所以这个插入元素放到最后
        return nums.length;      
    }

就是怎么说呢，看了解析发现我这个答案太low了，暴力遍历，如果数组大会浪费很多性能，这个题虽然没标准答案，但是用二分法才是不low的解法（委屈），其实也不是不能理解，如果一千个元素切插入元素最大，这个方法要从第一个判断到最后一个，判断一千次，但是如果用了二分法则不用了，下面是二分法的逻辑：
注：我理解的二分法：判断是否大于第一个小于第一千个，如果是则判断是否大于第二个小于第五百个。如果是则在2-500中比对，不是则在501-999中比对，反正就是这么个逻辑。
其实这个我看了好几个二分法的解法，各有各的思路，居然很神奇的多个都略微不一样，然后我也没一个具体的看着思路特别清楚的demo，所以自己直接撸代码了，（如果有不太合理或者冗余的欢迎指出）

    public int searchInsert(int[] nums, int target) {
        if(nums[0]>=target){
            return 0;
        }
        if(nums[nums.length-1]<target){
            return nums.length;
        }
        //走到这里说明大于最小的小于最大的
        int left = 1;
        int right = nums.length-1;
        while((right-left)>1){
            //中位数大于target。则往左半部分查找
            if(nums[(left+right)/2]>target){ 
                 right = (left+right)/2;
            }else if(nums[(left+right)/2]<target){
                 left = (left+right)/2;
            }else{
                //不大于不小于才能到这里
                return (left+right)/2;
            }
        }
//其实这一步到底是选择左还是右好像是有规律的，但是我和实在是困的懵逼了，所以直接再用一个三目比较吧。就酱
        return target<=nums[left]?left:right;      
    }

报数

题目：报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1 1
2 11
3 21
4 1211
5 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例 1:
输入: 1
输出: "1"
示例 2:
输入: 4
输出: "1211"

说真的，做完为止觉得题目不咋难，解题贼鸡儿费劲。我是群里问了人，百度搜了题目才理解了这个规律。其实就是拆上一个数。1是第一个数.11是一个一.21是两个一,1211是一个二一个一。111221是一个一一个二两个一。我觉得我这么说应该都能理解这个规律了，也不想说什么递归不递归的反正规律就是这样（网上一些人恶心吧啦的上来就说递归，MLGB啊，不说声拆数直接递归个JB，草）
接下来好好说解题思路：就是从第一个数开始一点点升，升到需要报的那个数。

    public String countAndSay(int n) {
        //明显这个报数是两个一组，一个是个数一个是数值（第一个不算）
        return n==1?"1":nextSay(n);
    }
    //获取第n个报数的内容
    public static String nextSay(int n){
        //以n为条件递归，省的死循环
        String s = "1";//如果是1的答案
        while(n>1){
            String  result = "";
            int m = 1;
            for(int i = 0;i<s.length();i++){            
                if(i!=s.length()-1 &&s.charAt(i)==s.charAt(i+1)){
                    m++;
                }else{
                   result += m+""+s.charAt(i);
                    //计数归1，因为只要有了就是1
                    m=1;
                }
            } 
            s = result;
            n--;
        }
        return s;
    } 

直接上代码，明天再看大神的思路和解析。我这个跑是没问题，但是性能不太好。但是这种递归的，也不知道怎么优化了。明天再说。

image.png

好的，今天来写个续集，看了大神的思维，代码百分之九十五的逻辑一样，区别就是我用的string来回来去追加赋值，人家用的是StringBuffer来追加，其实看了恍然大悟，这个确实result是一直在追加的，用普通的String是一次次改指针，如果这个单独提出来，一个经常更改的字符串应该用什么类型的字符串，肯定是能想到用变长的StringBuffer或StringBuilder，但是因为这个是自己的方法里，所以就忽略了这一点，或者直接说没有这个意识。然后因为代码逻辑的几乎相同，所以我这里就不重写代码了，我觉得跟大佬差的就是这些细节。

然后但凡帮助到你麻烦点个喜欢点个关注，祝大家工作顺顺利利！