leetCode进阶算法题+解析（二十四）

翻转字符串里的单词

题目：给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶：
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

思路：讲真，这个题像是初级难度的啊，进阶要求是C语言的才有的，，我是java，哈哈。然后单纯的实现其实真的很简单，trim去前后空格，然后空格拆分字符串，然后双指针调换位置，然后stringBuffer加上。就酱，我去实现下
好了，思路没问题，而且很简单，性能超过百分之九十八，我都不敢去看评论了，恐怕再说我不应该用啥。。我先贴代码：

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        String[] arr = s.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int i = arr.length-1;i>=0;i--){
            if(arr[i].equals(" ") || arr[i].equals("") ) continue;
            sb.append(arr[i]+" ");
        }
        return sb.toString().trim();
    }
}

算了，伸头一刀缩头一刀，我去瞅瞅评论说啥了。
额，评论没说啥啊，而且性能排行第一的代码也是这个套路，所以这个题就过了吧！

寻找旋转排序数组中的最小值

题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你可以假设数组中不存在重复元素。

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

思路：这个题我感觉题目肯定是少条件了。不然不能是中等难度啊，不就是一个遍历的事么？应该是时间复杂度logn？常量级是不可能的，，我去按照我想的时间复杂度做了。
第一版本出来了，我先贴出来：

class Solution {
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        while(l<r){
            if(nums[l]<nums[r]) return nums[l];
            if(nums[l]>nums[l+1]) return nums[l+1];
            if(nums[r]<nums[r-1]) return nums[r];
            l++;
            r--;
        }
        return nums[0];
    }
}

这个时间复杂度是n。不太满足我的要求，我再去试试logn实现的。
好了，二分法实现了，我贴下代码：‘

class Solution {
    public int findMin(int[] nums) {
        if(nums.length == 1) return nums[0];
        //说明已经是升序了
        if(nums[0]<nums[nums.length-1]) return nums[0];
        int l = 0;
        int r = nums.length-1;
        while(l<r){
            int mid = (r-l)/2+l;
            if(nums[mid]<nums[r]){//后半段是排好序的。说明旋转点在前半段
                r = mid;
            }else if(nums[mid]>nums[r]){//旋转点在后半段
                l = mid +1;
            }else{
                return nums[mid];
            }
        }
        return nums[l];
    }
}

然后这道题就这样了，不算难，难点就是二分法区间了。没啥好说的，多看看就好了，直接下一题了。

乘积最大子序列

题目：给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路：这道题怎么说呢，乍一看我甚至想到了动态规划，但是仔细瞅了瞅，其实逻辑好处理多了。也可以用dp。第一个数作为开始值，挨个和后面乘，保存其中的最大乘积，第二个数开始，挨个和后面乘，保存最大乘积，反正取最大的就行。我去实现啦。
哎，我自己实现了，然后性能贼可怜，但是我还是要发出来，毕竟是自己想出来的：

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<nums.length;i++){
            int count = nums[i];
            max = Math.max(max,count);
            for(int j = i+1;j<nums.length;j++){
                count *= nums[j];
                 max = Math.max(max,count);
            }
        }
        return max;
    }
}

咳咳，无脑但是一看就懂，我觉得挺好的，但是性能太不给力啊~~~
其实有这个感觉，毕竟做了很多无用功，我去看看怎么能优化一下。
好了，接下来去看性能排行第一的代码了！对，我凭实力优化不出来了。。。膜拜大佬吧

class Solution {
    public int maxProduct(int[] nums) {
        /*求最大值，看被0拆分的各个子数组的最大值
        1.负数为偶数：全部乘积
        2.负数为奇数：最左或最右的负数不在内，从左到右和从右到左分别计算，求最大
        3.存在0，则从1重新开始
        */
        int m=1;
        int max=nums[0];
        for(int num:nums){
            m=m*num;
            max=Math.max(max,m);
            if(num==0){
                m=1;
            }
        }
        m=1;
        for(int i=nums.length-1;i>=0;i--){
            m=m*nums[i];
            max=Math.max(max,m);
            if(nums[i]==0){
                m=1;
            }
        }
        return max;
    }
}

这个思路怎么说呢，代码复杂了点，因为两遍循环。但是比我的n方的时间复杂度好太多。。。我只能说记住了，下次争取自己写也这样写。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注哟~！然后顺便祝大家工作顺顺利利！生活健健康康！