LeetCode 专题：数组

作者: 李威威 | 来源:发表于2019-05-26 05:29 被阅读0次

知识点总结

二分查找法（二分查找法是弱点）**以及相关的操作：递归实现和非递归实现，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 这两个前提条件。

（本节完）

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 专题：数组

知识点总结

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 题：只出现一次的数字