Array

1.Remove Element

题目描述：

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

自己解（出错未解决）：感觉思路不对。。

提交记录

输入：[0,1,2,2,3,0,4,2] 2
输出：[0,1,2,3,0,4]
预期：[0,1,4,0,3]

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        for (int i=0; i<nums.length; i++) {
            if (val == nums[i]) {
                len--;
                for(int j=i+1; j<nums.length; j++) {
                    nums[j-1] = nums[j];
                }
            }
        }
        return ++len;
    }
}

官方题解：
方法一：双指针

class Solution {
    public int removeElement(int[] nums, int val) {
        // 慢指针i, 快指针j
        int i = 0; 
        for (int j=0; j<nums.length; j++) {
            if (nums[j] != val) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

复杂度分析

• 时间复杂度：O(n)，
  假设数组总共有 nn 个元素，ii 和 jj 至少遍历 2n2n 步。
  
• 空间复杂度：O(1)。

方法二：双指针—当要删除的元素很少时。
思路：考虑两种情况

• num=[1，2，3，5，4]，Val=4。
• num=[4，1，2，3，5]，Val=4。

public int removeElement(int[] nums, int val) {
    int i = 0; 
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n-1];
            n--;
        } else {
            i++;
        }
    }
    return n;
}

复杂度分析

• 时间复杂度：O(n)O(n)，ii 和 nn 最多遍历 nn 步。在这个方法中，赋值操作的次数等于要删除的元素的数量。因此，如果要移除的元素很少，效率会更高。
• 空间复杂度：O(1)O(1)。

2.Remove Duplicates from Sorted Array

题目描述：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

题解：

还是使用双指针，如果快指针与慢指针对应的值不相等则说明不重复，添加进数组。

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j=1; j<nums.length; j++) {
            if (nums[i] != nums[j]) {
                nums[++i] = nums[j];
            }
        }
        return i+1;
    }
}

3.Remove Duplicates from Sorted Array II

题目描述：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

思路：

自己想象有两排数组。
一个索引从i=2开始，另一个从j=2开始，如果第i=2个与第0个不同，则可以进行赋值，利用此时i的位置可以将j=2的位置的值赋给它，之后i自增，进入下轮循环判断。
本质上就是双指针法。

代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 2) {
            return len;
        }
        int i = 2;
        for (int j=2; j<len; j++) {
            if (nums[j] != nums[i-2]) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

4.Rotate Array

题目描述：

Given an array, rotate the array to the right by k steps, where k is non-negative.

题解：

①Brute Force：
进行k次循环，每次循环往右移一位。
②Using Extra Array：
将原数组中的值直接放到新建数组对应的值，在赋值给原来数组。
③Using Reverse：
先整体转置，在局部分别转置。

代码：

// Brute Force
class Solution {
    public void rotate(int[] nums, int k) {
        int temp, previous;
        for (int i=0; i<k; i++) {
            previous = nums[nums.length-1];
            for (int j=0; j<nums.length; j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
}

// Using Extra Array
class Solution {
    public void rotate(int[] nums, int k) {
        int[] a = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            a[(i+k) % nums.length] = nums[i];
        }
        for (int i=0; i<nums.length; i++) {
            nums[i] = a[i];
        }
    }
}

// Using Cyclic Replacements
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
}

5.First Missing Positive 困难

题目描述：

Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1

6.Gas Station Medium

Example 1:
Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Solution:

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sumGas = 0;
        int sumCost = 0;
        int start = 0; 
        int tank = 0;

        for (int i = 0; i < gas.length; i++){
            sumGas += gas[i];
            sumCost += cost[i];
            int temp = gas[i] - cost[i];
            tank += temp;
            if (tank < 0){
                start = i + 1;
                tank = 0;
            }
        }
        if (sumGas < sumCost) {
            return -1;
        } else {
            return start;
        }
    }
}