LeetCode 专题：数组

知识点总结

二分查找法（二分查找法是弱点）**以及相关的操作：递归实现和非递归实现，floor 和 ceiling，《剑指Offer》上面关于二分查找法的应用（旋转数组中找开始的数）。

二分查找法以及相关的操作：递归实现和非递归实现，floor 和 ceiling，《剑指Offer》上面关于二分查找法的应用。

leetcode 315 逆序数（count of smaller numbers after self）——分治
https://blog.csdn.net/yysave/article/details/85165099

LeetCode 第 239 题：滑动窗口最大值

image-20190112093950121

只关心位置而不关系顺序

LeetCode 第 215 题：数组中的第 K 个最大元素

LeetCode 第 215 题：Kth-Largest-Element-in-an-Array（很重要）。

（1）使用优先队列完成

（2）使用快速排序完成

Java 代码：

public class Solution {

    /**
     * 给定任意一个数组，返回第 k 大的元素，并非索引
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int p = 0;

        int left = 0;
        int right = len - 1;
        while (left <= right) {
            p = partition(nums, left, right);
            if (len - p == k) {
                break;
            } else if (len - p + 1 > k) {
                left = p + 1;
            } else {
                right = p - 1;
            }
        }
        return nums[p];
    }

    /**
     * 4,3,7,8
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] nums, int left, int right) {
        // 就找第 1 个元素作为标定点
        int k = nums[left];

        int i = left + 1; // [left,i)小于 k
        int j = right; // (j,right]大于 k

        for (int l = left + 1; i <= j; l++) {
            if (nums[l] < k) {
                i++;
            } else {//nums[l]>=k
                swap(nums, l, j--);
                l--;
            }

        }
        i--;
        swap(nums, i, left);
        return i;
    }


    private void swap(int[] data, int index1, int index2) {
        if (index1 == index2) return;
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }


    public static void main(String[] args) {
        int[] data = {3, 2, 1, 5, 6, 4};
        int k = 2;
        Solution solution = new Solution();

        solution.partition(data, 2, 4);
        int kthLargest = solution.findKthLargest(data, k);
        System.out.println("kthLargest = >" + kthLargest);
    }
}

LeetCode 第 5 题：最长回文子串。

解法1：中心扩散法；

解法2：动态规划；

解法3：著名的马拉车算法。

LeetCode 第167 题：两数之和 II - 输入有序数组

LeetCode 第 11 题：

LeetCode 第 209 题： 209. 长度最小的子数组

==这道题记住解法。==

LeetCode 第 438 题：找到字符串中所有字母异位词

使用==滑动窗口==解决的典型问题。

LeetCode 第 76 题：最小覆盖子串（困难）

LeetCode 第 630 题：课程调度问题

LeetCode 第 452 题：用最少数量的箭引爆气球。

关键：==画图==。理解按照右端点升序排序的好处。

LeetCode 第 80 题：删除排序数组中的重复项 II

LeetCode 第 80 题：最多保留两个（重刷一下，看看别人的解答）

传送门： https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/。

这个写的比较顺，一下就通过了，但是我的解法只是击败了 35.43% 的选手。

public class Solution {

    /**
     * 如果我们允许重复的元素最多出现两次呢？
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {

        int k = 0;// 从[0,k) 这个区间里的所有元素是一个有序数组，并且重复元素最多出现两次
        int duplicate_time = 0;

        // 首先考虑极端的情况
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        nums[k++] = nums[0];

        if (len == 1) {
            return 1;
        }

        for (int i = 1; i < len; i++) {
            if (nums[i] - nums[i - 1] == 0) {
                duplicate_time++;
                if (duplicate_time < 2) {
                    // 重复次数大于等于 2 次，什么都不做
                    nums[k++] = nums[i];
                }
            } else { // nums[i] - nums[i - 1] > 0
                duplicate_time = 0;
                nums[k++] = nums[i];
            }
        }
        // 把数组的剩余元素赋值为 -1
        for (int i = k; i < len; i++) {
            nums[i] = -1;
        }
        return k;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4};
        Solution solution = new Solution();
        int removeDuplicates = solution.removeDuplicates(arr);
        System.out.println("剩余的数组元素的个数 => " + removeDuplicates);
        System.out.println(Arrays.toString(arr));
    }

}

LeetCode 第 74 题：颜色分类

分析：三路快排，不借助额外空间就排好序，背模板。。

LeetCode 第 88 题：合并两个有序数组

关键：从后向前归并排序，背模板。

LeetCode 第 88 题：

其实就是归并排序，从后面向前面归并排序，扩展：字符串替换空格。

解答：

public class Solution {

    /**
     * @param nums1 一个排好序的数组1
     * @param m
     * @param nums2 一个排好序的数组2
     * @param n     结果放在 nums1 中
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        for (int i = 0; i < m; i++) {
            temp[i] = nums1[i];
        }
        for (int i = 0; i < n; i++) {
            temp[m + i] = nums2[i];
        }


        int left = 0; // 数组1的第1个元素
        int right = m; // 数组2的第1个元素

        // 这种特殊情况要考虑进去
        if (m > 0 && n > 0 && temp[m - 1] <= temp[m]) {
            for (int i = 0; i < m + n; i++) {
                nums1[i] = temp[i];
            }
            return;
        }

        // 要赋值完 m+n 个元素，就要遍历 m+n 个元素
        for (int i = 0; i < m + n; i++) {
            if (left >= m) { // 如果左边用完了，就一直拿右边的元素
                nums1[i] = temp[right];
                right++;
            } else if (right >= m + n) {
                nums1[i] = temp[left];
                left++;
            } else if (temp[left] < temp[right]) {
                nums1[i] = temp[left];
                left++;
            } else { // temp[left] >= temp[right]
                nums1[i] = temp[right];
                right++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1};
        int[] nums2 = {5, 6, 7, 8, 9};

        Solution solution = new Solution();
        solution.merge(nums1, 5, nums2, 5);
        System.out.println(Arrays.toString(nums1));

    }

}

LeetCode 第 56 题：压缩区间（区间个数变少）

传送门：56. 合并区间。

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

注意：对于 list 对象而言，if l 等价于 if len(l) > 0 而不是 l is not Node。

image-20190110155739620

Python 代码：

# Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

    def __str__(self):
        return '[' + str(self.start) + ',' + str(self.end) + ']'


class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        result = []
        # 按照开始端点升序排序
        sorted_intervals = sorted(intervals, key=lambda x: x.start)

        for intv in sorted_intervals:
            if len(result) != 0 and result[-1].end >= intv.start:
                # 说明当前遍历到的区间和结果集中有交集
                result[-1].end = max(result[-1].end, intv.end)
            else:
                result.append(intv)
        return result


if __name__ == '__main__':
    # [[1, 3], [2, 6], [8, 10], [15, 18]]
    i1 = Interval(1, 3)
    i2 = Interval(2, 6)
    i3 = Interval(8, 10)
    i4 = Interval(15, 18)
    intervals = [i1, i2, i3, i4]
    solution = Solution()
    result = solution.merge(intervals)
    for item in result:
        print(item)

LeetCode 第 57 题：插入一个区间（区间个数不变）

传送门：57. 插入区间。

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:
输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
示例 2:
输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

Java 代码：

import java.util.*;

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}


// http://zxi.mytechroad.com/blog/geometry/leetcode-57-insert-interval/

public class Solution {

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int len = intervals.size();
        if (len == 0) {
            intervals.add(newInterval);
            return intervals;
        }
        intervals.add(newInterval);

        // intervals.sort((Interval a, Interval b) -> a.start - b.start);
        intervals.sort(Comparator.comparingInt((Interval i) -> i.start));
        Stack<Interval> stack = new Stack<>();
        stack.add(intervals.get(0));

        for (int i = 1; i <= len; i++) {
            Interval peekInterval = stack.peek();
            Interval curInterval = intervals.get(i);
            if (peekInterval.end < curInterval.start) {
                // [1,3] [4,6] 这种情况，无论如何也合并不了的
                stack.add(curInterval);
            } else {
                // [1,3][3,5]
                // [1,3][2,6]
                // 这两种情况就需要合并
                peekInterval.end = Math.max(curInterval.end, peekInterval.end);
            }
        }
        return stack;
    }

    public static void main(String[] args) {
        // intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
        Interval interval1 = new Interval(1, 2);
        Interval interval2 = new Interval(3, 5);
        Interval interval3 = new Interval(6, 7);
        Interval interval4 = new Interval(8, 10);
        Interval interval5 = new Interval(12, 16);
        List<Interval> intervals = new ArrayList<>();
        intervals.add(interval1);
        intervals.add(interval2);
        intervals.add(interval3);
        intervals.add(interval4);
        intervals.add(interval5);

        Solution solution = new Solution();
        Interval newInterval = new Interval(4, 8);
        List<Interval> list = solution.insert(intervals, newInterval);
        for (Interval interval : list) {
            System.out.println("[" + interval.start + ", " + interval.end + "]");
        }
    }
}

Java 代码：

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (newInterval == null) {
            return intervals;
        }
        List<Interval> res = new ArrayList<>();
        int len = intervals.size();

        // 之前的加起来
        int i = 0;
        while (i < len && intervals.get(i).end < newInterval.start) {
            res.add(intervals.get(i));
            i++;
        }

        //
        // intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
        // 此时 intervals.get(i).end >= newInterval.start
        while (i < len && intervals.get(i).start <= newInterval.end) {
            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            i++;
        }

        res.add(newInterval);

        // 把剩下的加掉
        while (i < intervals.size()) {
            res.add(intervals.get(i));
            i++;
        }
        return res;
    }

    public static void main(String[] args) {
        // intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
        Interval interval1 = new Interval(1, 2);
        Interval interval2 = new Interval(3, 5);
        Interval interval3 = new Interval(6, 7);
        Interval interval4 = new Interval(8, 10);
        Interval interval5 = new Interval(12, 16);
        List<Interval> intervals = new ArrayList<>();
        intervals.add(interval1);
        intervals.add(interval2);
        intervals.add(interval3);
        intervals.add(interval4);
        intervals.add(interval5);

        Solution2 solution2 = new Solution2();
        Interval newInterval = new Interval(4, 8);
        List<Interval> list = solution2.insert(intervals, newInterval);
        for (Interval interval : list) {
            System.out.println("[" + interval.start + ", " + interval.end + "]");
        }
    }
}

LeetCode 第 66 题：数组加 1

注意可以提前终止。

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """

        n = len(digits)
        if n == 0:
            return None
        # 从后向前
        for index in range(n - 1, -1, -1):
            if digits[index] < 9:
                digits[index] += 1
                return digits
            else:
                digits[index] = 0
        return [1] + digits

LeetCode 第 67 题：二进制加法：从尾巴开始加

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        res = ''
        # 分别表示两个数从后向前的索引，后对齐
        i = len(a) - 1
        j = len(b) - 1
        # 表示进位标志
        carry = 0
        while i >= 0 or j >= 0:
            s = carry
            if i >= 0:
                s += ord(a[i]) - ord('0')
                i -= 1
            if j >= 0:
                s += ord(b[j]) - ord('0')
                j -= 1

            res = str(s % 2) + res
            carry = s // 2
        if carry == 1:
            return '1' + res
        return res

LeetCode 第 26 题：删除排序数组中的重复项

Given a sorted array, remove the duplicates（重复） in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,

Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

我的解答：下面展示的是我最直观的想法。

1、首先我们需要一个变量，这里我声明为memory 来保存一个被比较的数。首先，数组的第 1 个元素（index = 0 的那个）被存进去；

2、接着从数组的第 2 位开始遍历，遇到和 memory 的值一样的，就什么都不做，遇到和 memory 不一样的，把当前值更新到 memory 中，并且 j 加 1 ，在原数组 j 这个索引上也更新这个值。

分析：利用了 a sorted array 的特点，新数组的元素个数也一定不会超过原来的数组，所以可以不借助额外的空间来完成题目的要求。

public class Solution {

    public int removeDuplicates(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int memory = nums[0];
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - memory > 0) {
                nums[j] = nums[i];
                j++;
                memory = nums[i];
            } else {
                continue;
            }
        }
        return j;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // int[] nums = new int[]{1,1,1,2,2,2,3,3,3,4,5,6,7,7,7,8,9,10,10};
        int[] nums = new int[]{1};
        int result = solution.removeDuplicates(nums);
        System.out.println(result);
        System.out.println(Arrays.toString(nums));

    }
}

还有一种解法可以参：leet-solution
的解答。不借助额外的空间。一开始 j 在 i 后面一格，然后马上比较两个元素的值，如果元素的值一样，则 j 加 1 ，如果元素的值不一样，j 和 i 都加 1 。

解法2：

public class Solution2 {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int j = 0;
        int i = 1;

        for (; i < nums.length; i++) {
            if (nums[i] == nums[j]) {
                // 什么都不做
            } else {
                nums[++j] = nums[i];
            }
        }
        // 返回的是数组的长度，所以要 + 1
        return j + 1;
    }
}

分析：

要求从一个有序的数组中删除重复的元素。
思考如何定义删除？是从数组中删除？还是放在数组的末尾？
剩余元素的排列是否要保证原有的相对顺序？
是否有空间复杂度的要求？
这里也用到了循环不变量的定义，要明确才能正确写出代码逻辑。

思路

挨个加入到一个 Map 中，判断是否有键值，这个思路没有利用到数组的有序性，故不采纳；
后一个元素减去前一个元素，如果等于0，就说明重复了（我用这种办法）。

public class Solution {

    /**
     * 删除重复的元素，按照 LeetCode 上 Java 对删除数组元素的删除的判定，
     * LeetCode 上的规则就是不判定，只要这个数组前面有效索引上的数是正确的就可以了
     *
     * @param nums
     * @return 不重复的元素个数
     */
    public int removeDuplicates(int[] nums) {
        int k = 0;// 定义 [0,k)是一个没有重复元素的有序数组
        // 从第 1 个元素开始，依次考察前面的元素
        // 特别注意到三个元素连续的情况，例如 [6,6,6,6,7]
        // 判断第 1 个元素该不该进去
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        nums[k++] = nums[0];
        if (len == 1) {
            return 1;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] != 0) {
                nums[k++] = nums[i];
            }
        }
        for (int i = k; i < nums.length; i++) {
            nums[i] = -1;
        }
        return k;
    }

    public static void main(String[] args) {
        //int[] sortedArray = {1, 2};
        //int[] sortedArray = {1, 1};
        int[] sortedArray = {1, 2, 2, 2, 3, 4, 5, 6, 6, 6, 7, 7, 8, 9};
        //int[] sortedArray1 = {1,2,3,2,3,4,5,6,6,6,7,7,8,9};
        Solution solution = new Solution();
        int non_duplicates = solution.removeDuplicates(sortedArray);
        System.out.println("不重复的元素个数有 => " + non_duplicates);
        System.out.println(Arrays.toString(sortedArray));
    }
}

总结：这一版我写得不好，吃过一次晚饭以后，才得到了 Accepted。总结如下：
1、没有考虑极端的情况；
2、第 1 个元素必须加入到结果数组中；
3、既然我是与前一个元素进行比较，那么我的索引最大值就应该是数组长度-1，边界值问题模糊不清也是我经常犯的错误。

《LeetCode》题解上有新的思路，可以学习一下。

LeetCode 第 27 题：删除元素

传送门： https://leetcode.com/problems/remove-element/description/ 。

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate（分配） extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:

Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

要求：在一个数组里面移除指定元素，并返回新的数组的长度。

public class Solution {

    public int removeElement(int[] nums, int val) {
        int i = 0;
        int j = 0;
        for (; i < nums.length; i++) {
            if(nums[i]==val){
                continue;
            }
            nums[j] = nums[i];
            // 只要遇到与 val 不等的元素，就累加 1
            // 所以，直接返回 j 就可以了
            j++;
        }
        return j;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int result = solution.removeElement(new int[]{3,2,2,3},2);
        System.out.println(result);
    }
}

分析：就这道问题，我们要考虑的问题是：

如何定义删除？从数组中删除？还是放在数组的末尾？
剩余元素的排列是否要保证原来的相对顺序？
是否有空间复杂度的要求？

我的解答：有瑕疵，因为在 Java 中数组的长度是固定的。在这个函数中不能移除 Java 数组中的元素。但是居然在 LeetCode 中通过了。

public class Solution {

    // Given input array nums = [3,2,2,3], val = 3

    /**
     * 题目的要求中说，顺序可以改变
     * 不管怎么样，先写出来最要紧
     * 难点：Java 中的数组元素怎么删除，这里我没有实现
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 2, 3};
        int val = 3;
        Solution solution = new Solution();
        int removeElementNum = solution.removeElement(nums, val);
        System.out.println(removeElementNum);
        System.out.println(Arrays.toString(nums));
    }
}

第 2 遍解答，其实本质上是一样的，思路分析：对题目的说明：在一个数组里面移除指定元素，并返回新的数组的长度。
解题思路：给出两个指针 i 和 j，其中 i 就想我们平常遍历数组元素一样，是一个普通的循环遍历。
和 j 就像是一支笔，我们要借助这支笔，往一个新数组里面写数据。
只不过，根据题意，我们恰恰好可以利用原来的数组的空间，这是因为，我们的任务是 Remove Element，新数组的元素个数一定不会超过原数组的元素个数。

Java 代码：

public class Solution {

    public int removeElement(int[] nums, int val) {
        int i = 0;
        int j = 0;
        for (; i < nums.length; i++) {
            if(nums[i]==val){
                continue;
            }
            nums[j] = nums[i];
            // 只要遇到与 val 不等的元素，就累加 1
            // 所以，直接返回 j 就可以了
            j++;
        }
        return j;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int result = solution.removeElement(new int[]{3,2,2,3},2);
        System.out.println(result);
    }
}

LeetCode 第 136 题：只出现一次的数字

LeetCode 第 137 题：只出现一次的数字 II（较难）

要求：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

LeetCode 第 125 题：Valid Palindrome

传送门：https://leetcode.com/problems/valid-palindrome/description/

使用指针对撞的思想：

public class Solution {

    /**
     * "A man, a plan, a canal: Panama"
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        int index_i = 0;
        int index_j = s.length() - 1;

        while (index_i <= index_j) {
            String i = s.charAt(index_i) + "";
            String j = s.charAt(index_j) + "";
            if (!i.matches("[0-9a-zA-Z]")) {
                index_i++;
                continue;
            }
            if (!j.matches("[0-9a-zA-Z]")) {
                index_j--;
                continue;
            }
            if (!j.equalsIgnoreCase(i)) {
                return false;
            } else {
                index_i++;
                index_j--;
            }
        }
        return true;
    }
}

提交以后发现，才击败了 0.85% 的 Java 开发者。
下面改了一版，击败了 19.22% 的 Java 开发者。

Java 代码：

public class Solution {

    /**
     * "A man, a plan, a canal: Panama"
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        // 去掉非数字和字母
        // 全部转换为小写
        s = s.replaceAll("[^0-9a-zA-Z]", "");
        StringBuilder reverse = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            reverse.append(s.charAt(i));
        }
        return s.equalsIgnoreCase(reverse.toString());
    }

    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        Solution solution = new Solution();
        boolean palindrome = solution.isPalindrome(s);
        System.out.println(palindrome);
    }
}

汉明距离

LeetCode 第 836 题：矩形重叠

要求：矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。

如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形，判断它们是否重叠并返回结果。

分析：

不是这种坐标系：

（0,0）（0,1）（0,2）（0,3）

（1,0）（1,1）（1,2）（1,3）

（2,0）（2,1）（2,2）（2,3）

（3,0）（3,1）（3,2）（3,3）

而是直角坐标系

（3,0）（3,1）（3,2）（3,3）

（2,0）（2,1）（2,2）（2,3）

（1,0）（1,1）（1,2）（1,3）

（0,0）（0,1）（0,2）（0,3）

image-20190111002624407

LeetCode 第 344 题：Reverse String

传送门：https://leetcode.com/problems/reverse-string/description/。

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

思路1：使用 Java 语言提供的反转 API 完成

public class Solution {
    public String reverseString(String s) {
        StringBuilder reverse = new StringBuilder();
        for (int i = s.length()-1; i >=0 ; i--) {
            reverse.append(s.charAt(i));
        }
        return reverse.toString();
    }

    // Given s = "hello", return "olleh".
    public static void main(String[] args) {
        String s = "hello";
        Solution solution = new Solution();
        String reverseString = solution.reverseString(s);
        System.out.println(reverseString);
    }
}

思路2：使用指针对撞

Java 代码实现：

public class Solution {
    public String reverseString(String s) {
        char[] cArray = s.toCharArray();
        int i = 0;
        int j = cArray.length - 1;
        while (i < j) {
            swap(cArray, i, j);
            i++;
            j--;
        }
        return new String(cArray);
    }

    private void swap(char[] s, int index1, int index2) {
        if (index1 == index2) return;
        char temp = s[index1];
        s[index1] = s[index2];
        s[index2] = temp;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String result = solution.reverseString("hello world");
        System.out.println(result);
    }
}

LeetCode 第 345 题：Reverse Vowels of a String

反转一个字符串的元音部分。

传送门：https://leetcode.com/problems/reverse-vowels-of-a-string/description/

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Example 2:
Given s = "leetcode", return "leotcede".

Note:
The vowels does not include the letter "y".

分析：

使用指针对撞，遇到元音字符的时候就听下来交换，交换以后指针继续向前；
这样的代码其实是套路，多写几遍就不会忘记了，我们在基础算法的学习中，曾经也有遇到过。

Java 代码：

public class Solution {
    /**
     * 写多了就知道，这是套路了
     *
     * @param s
     * @return
     */
    public String reverseVowels(String s) {
        if (s.length() == 0) return "";
        char[] chars = s.toCharArray();
        int i = 0;
        int j = chars.length - 1;
        while (true) {
            // 如果走到最后一位都不符号要求的话，就不能再前进了。代码实现如下
            while (i < chars.length && !checkVowels(chars[i])) {
                i++;
            }
            while (j >= 0 && !checkVowels(chars[j])) {
                j--;
            }
            if (i < j) {
                swap(chars, i, j);
                i++;
                j--;
            } else {
                break;
            }
        }
        return new String(chars);
    }

    private void swap(char[] chars, int index1, int index2) {
        if (index1 == index2) return;
        char temp = chars[index1];
        chars[index1] = chars[index2];
        chars[index2] = temp;
    }

    private boolean checkVowels(char c) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
                c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U'   ) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        //String result1 = solution.reverseVowels("hello");
        //System.out.println(result1);
        //String result2 = solution.reverseVowels("leetcode");
        //System.out.println(result2);

        String result3 = solution.reverseVowels(" ");
        System.out.println(result3);

    }
}

要注意的地方

极端的情况要考虑到：if (s.length() == 0) return "";；
还有一种极端的情况要考虑到，就是 i 和 j 可以一直走到底的情况，翻译成大白话就是：如果走到最后一位都不符号要求的话，就不能再前进了。代码实现如下：

while (i < chars.length && !checkVowels(chars[i])) {
    i++;
}
while (j >= 0 && !checkVowels(chars[j])) {
    j--;
}

上述代码特别容易忽略掉：i < chars.length 和 j >= 0 这两个前提条件。

（本节完）

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350

LeetCode 专题：数组

知识点总结

LeetCode 第 239 题：滑动窗口最大值

只关心位置而不关系顺序

LeetCode 第 215 题：数组中的第 K 个最大元素

LeetCode 第 215 题：Kth-Largest-Element-in-an-Array（很重要）。

LeetCode 第 5 题：最长回文子串。

LeetCode 第167 题：两数之和 II - 输入有序数组

LeetCode 第 11 题：

LeetCode 第 209 题： 209. 长度最小的子数组

LeetCode 第 438 题：找到字符串中所有字母异位词

LeetCode 第 76 题： 最小覆盖子串（困难）

LeetCode 第 630 题：课程调度问题

LeetCode 第 452 题：用最少数量的箭引爆气球。

LeetCode 第 80 题：删除排序数组中的重复项 II

LeetCode 第 80 题：最多保留两个（重刷一下，看看别人的解答）

LeetCode 第 74 题：颜色分类

LeetCode 第 88 题：合并两个有序数组

LeetCode 第 88 题：

LeetCode 第 56 题：压缩区间（区间个数变少）

LeetCode 第 57 题：插入一个区间（区间个数不变）

LeetCode 第 66 题：数组加 1

LeetCode 第 67 题：二进制加法：从尾巴开始加

LeetCode 第 26 题：删除排序数组中的重复项

LeetCode 第 27 题：删除元素

LeetCode 第 136 题： 只出现一次的数字

LeetCode 第 137 题：只出现一次的数字 II（较难）

LeetCode 第 125 题：Valid Palindrome

LeetCode 第 836 题：矩形重叠

LeetCode 第 344 题：Reverse String

LeetCode 第 345 题：Reverse Vowels of a String

要注意的地方

推荐阅读更多精彩内容

LeetCode 第 76 题：最小覆盖子串（困难）

LeetCode 第 136 题：只出现一次的数字