数组

26-删除重复元素

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
链接：leetcode-cn.com/problems/remove-du...

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        int slow = 1;
        int fast = 1;
        // 1 2 2 3
        while (fast < nums.length) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
            } 
            fast++;
        }
        return slow;
    }
}

27-移除元素

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

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
链接：leetcode-cn.com/problems/remove-el...

方法一：

    public int removeElement(int[] nums, int val) {
        // left代表下一个不等于val的下标
        int left = 0;
        // 遍历数组，只要不等于val的就赋值给num[left]，同事left++
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != val) {
                nums[left] = nums[j];
                left++;
            }
        }
        return left;
    }

方法二：

/**
 * 元素的顺序可以改变,所以可以使用两个下标left、right
 * left从左向右寻找等于val的元素
 * right从右向左寻找不等于val的值
 * 最后令nums[right] = num[right]
 */
public int removeElement(int[] nums, int val) {
        int left = 0, right = nums.length - 1;
        int count = 0;
        while (left <= right) {
            while (left <= right && nums[left] != val && left < nums.length) {
                left++;
                count++;
            }
            while (left <= right && nums[right] == val && right >= 0) {
                right--;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                count++;
                left++;
                right--;
            }
        }
        return count;
    }

方法三：

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

189-旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
链接：leetcode-cn.com/problems/rotate-ar...

暴力法会超时

// 会超时
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        for (int i = 0; i < k; i++) {
            int last = nums[nums.length - 1];
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = last;
        }
    }

通过找规律可以发现，翻转后的数组，将前k个翻转并且将剩下的(l-k)个也翻转，最后得到的数据为原始数组翻转后的结果。

因此我们可以先把整个数组翻转，然后将k个元素翻转，最后将后(l-k)个元素也翻转

public void rotate(int[] nums, int k) {
        k = k % nums.length;
        fun(nums, 0, nums.length - 1);
        fun(nums, 0, k - 1);
        fun(nums, k, nums.length - 1);
    }
    public void fun(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

300-最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

链接：leetcode-cn.com/problems/longest-i...

class Solution {
    /**
     * dp[i] = max(dp[j] + 1, dp[i]), 0 <= j < i
     * [0,3,1,6,2,2,7]
     */
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                // 找到比当前i的值小了
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return max;
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接