[数据结构与算法]数据结构与算法：数组和字符串

题目来自LeetBook 系列：《数组和字符串》——https://leetcode-cn.com/leetbook/detail/array-and-string/

1. 数组简介

No.1991 找到数组的中间位置

https://leetcode-cn.com/problems/find-the-middle-index-in-array/

原始思路：先遍历一遍得到总和，再从左开始遍历累加，直到前缀和为总和一半
错误1：for遍历没有遍历第一个数
错误2：没有判断当前和是否为偶数（奇数除以2即可以是也可以是1和-1）

具体代码：
执行用时：21 ms, 在所有 Java 提交中击败了21.73%的用户
内存消耗：41.5 MB, 在所有 Java 提交中击败了5.00%的用户

public int findMiddleIndex3(int[] nums) {
		
		if(nums.length == 1){
			return 0;
		}
		
		
    	int sum = 0;
    	int sum2 = 0;
    	int curr_sum;
    	
    	//数组总和
    	for (int i=0; i<nums.length; i++){
    		sum = sum + nums[i];
    	}
    	System.out.println("数组总和为：" + sum);
    	  	
    	//从左边开始加到一半
    	for (int i=0; i<nums.length; i++){
    		
    		if(i == 0){
    			sum2 = 0;
    		}else{
    			sum2 = sum2 + nums[i-1];
    		}
    		curr_sum = sum - nums[i];
    		if(curr_sum%2 == 1 || curr_sum%2 == -1){
    			continue;
    		}   		
    	
    		System.out.println("下标为" + i + "的数字左边数字之和为：" + sum2 + "，此时数组总和为：" + curr_sum);
    		if(sum2 == curr_sum/2){
    			return i;
    		}
    	}
    	return -1;
    }

优化思路：如果前缀和的2倍等于总和减去当前值则表示找到数组的中间位置

具体代码：
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.5 MB, 在所有 Java 提交中击败了15.12%的用户

public int findMiddleIndex(int[] nums) {
        // 计算nums数组的中所有元素总和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        int preSum = 0;// 前缀和
        for (int i = 0; i < nums.length; i++) {
            // 前缀和 + nums[i] + 后缀和 = 总和
            // if(前缀和==后缀和) return i;
            // 所以：if(2*前缀和=总和-nums[i]) return i;
            // 如果前缀和的2倍等于总和减去当前值则表示找到数组的中间位置
            if (preSum * 2 == sum - nums[i]) {
                return i;
            }
            // 更新前缀和
            preSum += nums[i];
        }

        return -1;
    }

注意：int total = Arrays.stream(nums).sum();可以求和，但是很慢。

No.35 搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/
思路：经典的二分查找题
错误：

1. while判断结束时是（l<r）还是（l<=r）？
2. mid是left + (right-left)/2还是(right + left) / 2？
3. 最后输出是什么？l？l-1？r？r？……

具体代码：

public int searchInsert(int[] nums, int target) {
        int left = 0;
		int right = nums.length -1 ;

		while(left<=right){
			int middle_num = (right + left) / 2
			
			if (target == nums[middle_num]){
				return middle_num;
			}else if(target > nums[middle_num]){
				left = middle_num+1;
			}else if(target < nums[middle_num]){
				right = middle_num-1;
			}
		}
		return left;
    }

注意：左边界的二分查找和右边界的二分查找！https://www.cnblogs.com/kyoner/p/11080078.html

No.56 合并区间（未完成）

https://leetcode-cn.com/problems/merge-intervals/

2. 二维数组

No.48 旋转图像

https://leetcode-cn.com/problems/rotate-image/
解法1：暴力，使用辅助数组
解法2：原地旋转，四个点一组找规律
解法3：先对角线翻转，再上下翻转

public void rotate1(int[][] matrix) {
		int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for(int i=0; i<n; i++){
        	for(int j=0; j<n; j++){
        		matrix_new[j][n-i-1] = matrix[i][j];
        	}
        }
        
        for(int i=0; i<n; i++){
        	for(int j=0; j<n; j++){
        		matrix[i][j] = matrix_new[i][j];
        	}
        }
    }

public void rotate2(int[][] matrix) {
		int n = matrix.length;
        int temp = 0;
        for(int i=0; i<n/2; i++){
        	for(int j=0; j<(n+1)/2; j++){
        		temp = matrix[i][j];
        		matrix[i][j] = matrix[n-j-1][i];
        		matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
        		matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
        		matrix[j][n-i-1] = temp;
        	}
        }
    }

public void rotate3(int[][] matrix) {
		int n = matrix.length-1;
        int temp = 0;
        
        //第一步，对角翻转
        for(int i=0; i<=n-1; i++){
        	for(int j=0; j<=n-i-1; j++){
        		//System.out.println("当前调换对子为：" + i + j + "和" + (n-i) + (n-j));
        		temp = matrix[i][j];
        		matrix[i][j] = matrix[n-j][n-i];
        		matrix[n-j][n-i] = temp;
        	}
        }
        
        //第二步，上下翻转
        for(int i=0; i<=n/2; i++){
        	for(int j=0; j<=n; j++){ 
        		//System.out.println("当前调换对子为：" + i + j + "和" + i + (n-j));
        		temp = matrix[i][j];
        		matrix[i][j] = matrix[n-i][j];
        		matrix[n-i][j] = temp;
        	}
        }
    }

No.73 矩阵置0

https://leetcode-cn.com/problems/set-matrix-zeroes/

1. 解法1：用两个标记数组分别记录每一行和每一列是否有零出现
2. 解法2：我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1)O(1) 的额外空间
3. 解法3：对方法二进一步优化，只使用一个标记变量记录第一列是否原本存在 00。这样，第一列的第一个元素即可以标记第一行是否出现 00

	/**
	 * 解1：大笨方法，全遍历，记录为0的地方，再换为0
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：42.8 MB, 在所有 Java 提交中击败了11.02%的用户
	 * .
	 * 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
	 * 空间复杂度：O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。
	 */
	public void setZeroes1(int[][] matrix) {
		int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
		
		for(int i=0; i<matrix.length; i++){
        	for(int j=0; j<matrix[0].length; j++){
        		if(matrix[i][j] == 0){
        			//如果发现了0  
        			row[i] = col[j] = true;       			
        		}
        	}
		}
		
		for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }

    }

	/**
	 * 解2：两个额外标志位，记录第0行和第0列是否为0
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：42.7 MB, 在所有 Java 提交中击败了12.76%的用户
	 * 时间复杂度：O(mn)，其中 m是矩阵的行数，n是矩阵的列数。我们至多只需要遍历该矩阵两次。
	 * 空间复杂度：O(1)。我们只需要常数空间存储若干变量。
	 */
	public void setZeroes2(int[][] matrix){
		int m = matrix.length, n = matrix[0].length;
		boolean row0 = false;
		boolean col0 = false;
		
		for(int j=0; j<n; j++){
			if(matrix[0][j] == 0){
				row0 = true;
			}
		}
		
		for(int i=0; i<m; i++){
			if(matrix[i][0] == 0){
				col0 = true;
			}
		}
		
		for(int i=1; i<matrix.length; i++){
        	for(int j=1; j<matrix[0].length; j++){
        		if(matrix[i][j] == 0){
        			//如果发现了0  
        			matrix[i][0] = matrix[0][j] = 0;       			
        		}
        	}
		}
		
		for(int i=1; i<matrix.length; i++){
        	for(int j=1; j<matrix[0].length; j++){
        		if(matrix[i][0] == 0 || matrix[0][j] == 0){
        			//如果发现了0  
        			matrix[i][j] = 0;       			
        		}
        	}
		}
		
		if(row0){
			for(int j=0; j<n; j++){
				matrix[0][j] = 0;
			}
		}
		
		if(col0){
			for(int i=0; i<m; i++){
				matrix[i][0] = 0;
			}
		}
	}

解3注意先判断matrix[0][0]，再判断标志位，否则第一列容易全0。

	/**
	 * 解3：一个额外标志位，记录第0行是否为0，第0列是否为0记录在[0][0]位置
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：43.1 MB, 在所有 Java 提交中击败了5.58%的用户
	 */
	public void setZeroes3(int[][] matrix){
		int m = matrix.length, n = matrix[0].length;
		boolean row0 = false;
		
		//第0行是否存在0
		for(int j=0; j<n; j++){
			if(matrix[0][j] == 0){
				row0 = true;
			}
		}
		
		//第0列是否存在0
		for(int i=0; i<m; i++){
			if(matrix[i][0] == 0){
				matrix[0][0] = 0;
			}
		}
		for(int i=1; i<matrix.length; i++){
        	for(int j=1; j<matrix[0].length; j++){
        		if(matrix[i][j] == 0){
        			//如果发现了0  
        			matrix[i][0] = matrix[0][j] = 0;       			
        		}
        	}
		}
		for(int i=1; i<matrix.length; i++){
        	for(int j=1; j<matrix[0].length; j++){
        		if(matrix[i][0] == 0 || matrix[0][j] == 0){
        			//如果发现了0  
        			matrix[i][j] = 0;       			
        		}
        	}
		}
		
		if(matrix[0][0] == 0){
			
			for(int i=0; i<m; i++){
				matrix[i][0] = 0;
			}
		}
		
		if(row0){
			for(int j=0; j<n; j++){
				matrix[0][j] = 0;
			}
		}
		
	}

No.498 对角线遍历（未完成）

https://leetcode-cn.com/problems/diagonal-traverse/

3. 字符串

No.14 最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/

1. 横向扫描
2. 纵向扫描
3. 分治（没实现）
4. 二分（没实现）

//解1：横向比较
	public String longestCommonPrefix1(String[] strs) {
		if(strs.length == 0){
			return "";
		}		
		String ans = strs[0];
		for(int i=1; i<strs.length; i++){
			int j=0;//必须放到外面，不然后面ans = ans.substring(0, j)用不了j
			for(; j<ans.length() && j<strs[i].length(); j++){
				if(ans.charAt(j) != strs[i].charAt(j)){
					break;
				}
			}			
			ans = ans.substring(0, j);//截取子串
			if(ans.equals("")){
				return ans;
			}
		}		
		return ans;
    }

public String longestCommonPrefix2(String[] strs) {
		if(strs.length == 0){
			return "";
		}
		
		
		int len = strs[0].length();//第一个字母长度
		int num = strs.length;//单词个数
		
		//1.遍历每一列（按第一个单词的长度）
		for(int i=0; i<len; i++){
			//2.遍历每一列中的每一个字母
			for(int j=0; j<num; j++){
				char c = strs[0].charAt(i);
				//3.如果字母就这么长 或者 不一样了，截断字符串返回
				if(strs[j].length()==i || strs[j].charAt(i)!=c){
					return strs[0].substring(0, i);
				}
			}
			
		}

		
		//4.否则第一个单词就是公共字串长度
		return strs[0];
		
	}

No.5 最长回文子串（未完成）

https://leetcode-cn.com/problems/longest-palindromic-substring/

No.151 翻转字符串里的单词（未完成）

https://leetcode-cn.com/problems/reverse-words-in-a-string/

4. 双指针

No.344 反转字符串

https://leetcode-cn.com/problems/reverse-string/
一遍过的题目，没啥可说的。

public void reverseString(char[] s) {
		int l = 0;
		int r = s.length - 1;
		
		while(l<r){
			char temp = s[l];
			s[l] = s[r];
			s[r] = temp;
			l++;
			r--;
		}

    }

No.561 数组拆分1

https://leetcode-cn.com/problems/array-partition-i/
一遍过的题目，没啥可说的。

public int arrayPairSum(int[] nums) {
		int sum = 0;
		
		Arrays.sort(nums);
		
		
		for(int i=0; i<nums.length; i++){
			sum = sum+nums[i];
			i++;
		}
		
		return sum;

    }

No.167 两数之和 II - 输入有序数组

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

1. 暴力算法，对于每一个数，再遍历一遍数组找，结果就是算法超时。
2. 二分查找。上面有个类似的，但是这题还是没做出来，还是有点问题，不过问题我暂时还没找出来。
3. 双指针。最快的，每次算l+r和target的大小关系，决定是l+1还是r-1

//解1：暴力算法，超时
	public int[] twoSum1(int[] numbers, int target) {
		int[] ans = new int[]{0,0};//初始化
		int len = numbers.length;//数组长度
		
		for(int i=0; i<len; i++){
			for(int j=len-1; j>0; j--){
				//System.out.println("ij之和为：" + (numbers[i]+numbers[j]));
				if(numbers[i]+numbers[j] == target){
					ans[0] = i+1;
					ans[1] = j+1;
					return ans;
				}
			}
		}
		return ans;	
    }

	/**
	 * 解2：二分查找
	 * 
	 * 
	 */
	public int[] twoSum3(int[] numbers, int target){
		int[] ans = new int[]{0,0};//初始化
		
		for(int i=0; i<numbers.length; i++){
			int rest = target - numbers[i];
			System.out.println("当前处理第" + (i+1) + "个数"+ numbers[i] +"，他的rest的值是" + rest);
			
			int l = i;
			int r = numbers.length-1;
			
			while(l<=r){
				int mid = l + (r-l)/2;
				System.out.println("当前l为" + l + "，当前r为" + r + "，当前mid为" + mid);
				if(rest == numbers[mid]){
					ans[0] = i+1;
					ans[1] = mid+1;
					System.out.println("找到答案" );
					return ans;
				}else if(rest > numbers[mid]){
					
					l = mid + 1;
					System.out.println("rest比mid大，所以l = mid + 1。l变为" + l + "，r仍为" + r);
				}else if(rest < numbers[mid]){
					
					r = mid -1;
					System.out.println("mid比rest大，所以r = mid -1。l仍为：" + l + "，r变为" + r);
				}
			}
			System.out.println("***********************");
		}
		return ans;
	}
	//二分正解
	public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

	/**
	 * 解3：双指针
	 * 执行用时：2 ms, 在所有 Java 提交中击败了36.04%的用户
	 * 内存消耗：43.9 MB, 在所有 Java 提交中击败了8.57%的用户
	 */
	public int[] twoSum2(int[] numbers, int target) {
		int[] ans = new int[]{0,0};//初始化
		int l = 0;
		int r = numbers.length-1;
		
		while(l<r){
			if(numbers[l]+numbers[r] == target){
				ans[0] = l+1;
				ans[1] = r+1;
				return ans;
			}else if(numbers[l]+numbers[r] > target){
				r--;
			}else if(numbers[l]+numbers[r] < target){
				l++;
			}
		}
		return ans;
	}

No.27 移除元素

https://leetcode-cn.com/problems/remove-element/submissions/
解：双指针，首尾各一个，往中间凑，该删的放最后。
注意：while终止条件需要等于号，最后return需要算一下

		public int removeElement(int[] nums, int val) {
		int l = 0;
		int r = nums.length-1;

		while(l<=r){
			System.out.println("a.r的值为：" + r);
			//如果靠近末尾的数就是val，那末尾标志左移一个
			if(nums[r] == val){
				//System.out.println("b.r的值为：" + r);
				nums[r] = 0;
				r--;
			}else{
				if(nums[l] == val){
					nums[l] = nums[r];
					nums[r] = 0;
					r--;
				}
				l++;
			}
		}
		//System.out.println("c.r的值为：" + r);
		return r+1;
    }

No.485 最大连续 1 的个数

https://leetcode-cn.com/problems/max-consecutive-ones/
简单题我重拳出击，一遍过。
注意：最后一个1算上之后有可能不加入计算，利用||的性质。

public int findMaxConsecutiveOnes(int[] nums) {
		int one_num = 0;//连续的1的数量
		int max_num = 0;//当前最大连续的1的数量
		
		for (int i=0; i<=nums.length; i++){
			//System.out.println("i=" + i);
			if (i == nums.length || nums[i] == 0){
				if(one_num > max_num){
					max_num = one_num;
				}
				one_num = 0;
				//System.out.println("当前最大数为：" + max_num);
			}else{
				one_num++;
			}
			//System.out.println("one_num=" + one_num);
		}	
		return max_num;
    }

No.209 长度最小的子数组

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

1. 暴力
2. 前缀和+二分查找（没实现）
3. 滑动窗口，判断终止条件花了很多时间

	/**
	 * 解1：暴力
	 * 执行用时：489 ms, 在所有 Java 提交中击败了5.04%的用户
	 * 内存消耗：41 MB, 在所有 Java 提交中击败了18.72%的用户
	 * 
	 * 在>=部分优化之后
	 * 执行用时：135 ms, 在所有 Java 提交中击败了9.70%的用户
	 * 内存消耗：41.2 MB, 在所有 Java 提交中击败了12.96%的用户
	 */
	public int minSubArrayLen1(int target, int[] nums) {
		int short_len = 10000;
		for(int i=0; i<nums.length; i++){
			int now_len = 0; // 当前符合条件的连续子串长度
			int sum = 0;
			for(int j=i; j<nums.length; j++){
				sum = sum + nums[j];
				System.out.println(i + " " + j + "，sum = " + sum);
				now_len++;
				if(sum >= target){
					System.out.println("抓住一个符合条件的子串长为：" + now_len);
					if(short_len > now_len){
						short_len = now_len;
					}
					now_len = 0;
					sum = 0;
					break;
				}else if(sum < target){
					continue;
				}
			}
		}
		
		if(short_len == 10000){
			return 0;
		}
		return short_len;
    }

	/**
	 * 解2：双指针滑动窗口
	 * 执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
	 * 内存消耗：41.2 MB, 在所有 Java 提交中击败了14.74%的用户
	 * 
	 */
	public int minSubArrayLen2(int target, int[] nums) {
		int ans = 10000; //最小连续个数
		int sum = nums[0]; //当前总和。sum不够target时候加nums[r]
		int l = 0;
		int r = 0;
		//终止条件：1.
		//r已经到达最右，sum还是不够target
		while(r<nums.length){			
			System.out.println("新一轮开始，" + l + " " + r + "，当前sum = " + sum);
			//如果当前sum不够target，则r右移，count加一
			if(sum < target){
				r++;
				if(r>=nums.length){
					break;
				}
				sum += nums[r];
				
				System.out.println("当前sum不够target，l不变r右移。" + l + " " + r + "，当前sum = " + sum);
				
				
				//如果当前sum够target，则l右移，count减一，sum减去nums[l]
			}else if(sum >= target){
				//System.out.println(sum + "大于等于" + target);
				
				System.out.println("抓住一个符合条件的子串长为：" + (r-l+1));
				if((r-l+1) < ans){
					ans = (r-l+1);
				}
				sum -= nums[l];
				l++;
				System.out.println("当前sum够target，l右移r不变。" + l + " " + r + "，当前sum = " + sum);			
			}
		}
		
		if(ans == 10000){
			return 0;
		}
		return ans;
	}

/**
	 * 官方解
	 * 两个优点：Integer.MAX_VALUE和双while
	 */
	public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

小结

No.118 杨辉三角

https://leetcode-cn.com/problems/pascals-triangle/
没什么难的，就是掌握List<List>的声明创建getset方法。

	List<List<Integer>> ans=new ArrayList<List<Integer>>();
		for(int i=0; i<numRows; i++){
			List<Integer> row = new ArrayList<Integer>();
			for(int j=0; j<=i; j++){
				if(i == 0 || i == 1 || j ==0 || j == i){
					row.add(1);
					continue;
				}
				int now = ans.get(i-1).get(j-1) + ans.get(i-1).get(j);
				row.add(now);
			}
			ans.add(row);
		}
		
		return ans;

No.119 杨辉三角 II

https://leetcode-cn.com/problems/pascals-triangle-ii/
解：

1. 和上面118类似，求全部，输出最后，小优化滚动数组每次保留一行省点空间
2. 倒着求解，挺妙，一个空间，倒着为了前面数不变
3. 直接数学算出相邻数的关系

	/**
	 * 解一：全求出来整体三角。有个小优化只留两行
	 * 执行用时：2 ms, 在所有 Java 提交中击败了25.29%的用户
	 * 内存消耗：39.3 MB, 在所有 Java 提交中击败了5.03%的用户
	 */
	public List<Integer> getRow1(int rowIndex) {
		List<List<Integer>> ans=new ArrayList<List<Integer>>();
		for(int i=0; i<rowIndex+1; i++){
			List<Integer> row = new ArrayList<Integer>();
			for(int j=0; j<=i; j++){
				if(i == 0 || i == 1 || j ==0 || j == i){
					row.add(1);
					continue;
				}
				int now = ans.get(i-1).get(j-1) + ans.get(i-1).get(j);
				row.add(now);
			}
			ans.add(row);
		}
		
		return ans.get(rowIndex);
    }

	/**
	 * 解二，挺妙，创建一个串，倒着求
	 * 
	 */
	public List<Integer> getRow2(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add(0);
            System.out.println(row);
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
                System.out.println(row);
            }
        }
        return row;
    }

	/**
	 * 解3
	 * 直接求出每一个数
	 */
	public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
            System.out.println(row);
        }
        return row;
    }

No.557 反转字符串中的单词 III

https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
由于java语言的特性，string类型不可变，不能原地操作，需要开辟额外空间。

	//暴力解
	public String reverseWords1(String s) {
		StringBuffer sb = new StringBuffer();
		int i=0;
		int p=0;//连续非空格字母数量
		while(i<=s.length()){
			if(i==s.length()-1){
				for(int j=0; j<p+1; j++){
					sb.append(s.charAt(i-j));
					//System.out.println(j);
					//System.out.println(sb.toString() + "，增加的是第" + (i-j) + "个字符！");
				}
				return sb.toString();
			}
			if(s.charAt(i) == ' '){
				//System.out.println("碰到空格了");
				for(int j=1; j<=p; j++){
					sb.append(s.charAt(i-j));
					//System.out.println(sb.toString() + "，增加的是第" + (i-j) + "个字符");
				}
				sb.append(' ');
				p=0;
			}else if(s.charAt(i) != ' '){
				p++;
			}
			i++;
		}
		return sb.toString();
    }

//官方解，i++写在前面，不需要额外考虑最后一个
	public String reverseWords(String s) {
        StringBuffer ret = new StringBuffer();
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s.charAt(i) != ' ') {
                i++;
            }
            for (int p = start; p < i; p++) {
                ret.append(s.charAt(start + i - 1 - p));
            }
            while (i < length && s.charAt(i) == ' ') {
                i++;
                ret.append(' ');
            }
        }
        return ret.toString();
    }

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

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
一次过的，没啥说的。不过还有二分法没实现。

public int findMin(int[] nums) {
		int ans = 0;
		int len = nums.length;
		if(len == 1){
			return nums[0];
		}
		//先判断首尾情况
		if(nums[1]>nums[0] && nums[len-1]>nums[0]){
			return nums[0];
		}
		if(nums[len-2]>nums[len-1] && nums[len-1]<nums[0]){
			return nums[len-1];
		}
		//判断中间
		for(int i=1; i<nums.length-1; i++){
			if(nums[i]<nums[i-1] && nums[i]<nums[i+1]){
				ans = nums[i];
				break;
			}
		}		
		return ans;
    }

No.26 删除有序数组中的重复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
双指针，一遍过。

public int removeDuplicates(int[] nums) {
        int a = 0; //无重复数组位置
		int now = nums[0]; //当前比较数字
		for(int i=1; i<nums.length; i++){
			if(nums[i] != now){
				nums[a+1] = nums[i];
				now = nums[i];
				a++;
			}
		}				
		return a+1;

    }

No.283 移动零

https://leetcode-cn.com/problems/move-zeroes/
解：非零按顺序前移，后面补0。还有一种更快的双指针，比较简单没写。

	public void moveZeroes(int[] nums) {
		if(nums.length == 1){
			return;
		}
		
		int a=0; //非零数字位置
		for(int i=0; i<nums.length; i++){
			if(nums[i] != 0){
				nums[a] = nums[i];
				a++;
			}
		}
		for(int j=a; j<nums.length; j++){
			nums[j] = 0;
		}
    }