LeetCode_Array

Easy

Array Partition I

给定一个2n整数的数组，你的任务是把这些整数分成n对整数，比如（a1，b1），（a2，b2），…，（an，bn），这使得min（ai， bi）的和尽可能大。

思路

排序，再以步长为2遍历数组，取每组中的较小值相加。
代码：

class Solution
{
    public int arrayPairSum(int[] nums)
    {
        Arrays.sort(nums);  //自带排序比我写的快排还好用。。。。。在此场景下
        int res = 0;
        for (int i = 0; i < nums.length; i += 2)
        {
            res += nums[i];
        }
        return res;
    }
}

Toeplitz Matrix

如果从左上角到右下角的每个对角线具有相同的元素，则矩阵是Toeplitz。
现在给出一个M×N矩阵，当且仅当矩阵是Toeplitz时才返回True。

思路一

对于二维数组（即矩阵）int[][] matrix
遍历第一行和第一列的元素，分别向右下角扩散，依次判断每条对角线元素是否全相等。
代码

public class ToeplitzMatrix
{
    public boolean isToeplitzMatrix(int[][] matrix)
    {
        for (int j = 0; j < matrix[0].length - 1; j++) //遍历行
        {
            int y = j;
            for (int x = 0; x < matrix.length - 1 && y < matrix[0].length - 1; x++, y++)
            {
                if (matrix[x][y] != matrix[x + 1][y + 1])
                {
                    return false;
                }
            }
        }
        for (int i = 1; i < matrix.length - 1; i++)  //遍历列
        {
            int x = i;
            for (int y = 0; y < matrix[0].length - 1 && x < matrix.length - 1; x++, y++)
            {
                if (matrix[x][y] != matrix[x + 1][y + 1])
                {
                    return false;
                }
            }
        }
        return true;
    }
}

27. 移除元素

给定一个数组 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。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

思路

双指针，一头一尾，头指针遇到val后，尾指针左移到第一个不等于val的位置，尾指针的值赋予头指针，头指针右移，尾指针左移。

代码

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i = 0 # 头指针
        n = len(nums)-1 # 尾指针
        while(i<=n):
            if nums[i] == val:
                while nums[n] == val and n >= 0: # 尾指针向前找
                    n -= 1
                if i < n:
                    nums[i] = nums[n]
                    n -= 1
                    i += 1
            else:
                i += 1
        return i

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

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

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

示例 1:

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

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

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

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

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

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

思路

见第80题

代码

见第80题

80. 删除排序数组中的重复项 II

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

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

示例 1:

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

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

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

思路

快慢指针，慢指针从0位置开始，快指针遍历数组
当快指针指向的数字等于慢指针左边第x个数字或者慢指针的位数小于x时
快指针指向的数字赋值给慢指针指向的位置
慢指针右移一位
上述思路为解决此类问题的模板，x为保留的重复数字的个数
所以第26的思路与此相同

代码

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for num in nums:
            if i < 2 or nums[i-2] != num:
                nums[i] = num
                i +=1

        return i