LeetCode算法练习-数组篇

1
2
3
给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

1
2
1.遍历数组
2.用(快慢)两个角标记录，当元素重复时，跳过重复的位置，当不重复的时候，把元素放到正确的位置上去

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int a = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[a] != nums[i]) nums[++a] = nums[i];
        }
        return a + 1;
    }
}

1
2
3
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

1
贪心法 允许多次买卖股票获取最大收益，只要今天比昨天的价格高了我就卖

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        //贪心法 允许多次买卖股票获取最大收益，只要今天比昨天的价格高了我就卖
        int m = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) m += prices[i] - prices[i - 1];
        }
        return m;
    }
}

1
循环K次遍历数组，倒叙遍历将每个位置的数字角标抬高一位，并将最后一位赋值到第1位

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void rotate(int[] nums, int k) {
       int len = nums.length;
        while (k > 0) {
            int cache = nums[len - 1];//缓存数组最后一位数
            for (int x = len - 2; x >= 0; x--) {
                nums[x + 1] = nums[x];//倒叙遍历将每个位置的数字角标抬高一位
            }
            nums[0] = cache;
            --k;//完成一个循环
        }
    }
}

1
[5,3,1,2,4,2,6,10] 这个数组存在2并且至少出现了2次 应该返回true

1
//先排序 再判断相邻元素是否相同

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean containsDuplicate(int[] nums) {
        //先排序 再判断相邻元素是否相同
        Arrays.sort(nums);
        for (int x = 1; x < nums.length; x++) {
            if (nums[x] == nums[x-1]) return true;
        }
        return false;
    }
}

1
2
3
//异或运算的可交换性 
// a ^ b = b ^ a
// a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        if (len == 1) return nums[0];
        int result = nums[0];
        for (int i = 1; i < len; i++) {
            result ^= nums[i];//异或运算的可交换性 
           // a ^ b = b ^ a
           // a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
        }
        return result;
    }
}

1
2
3
4
5
1.输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
2.我们可以不考虑输出结果的顺序。
3.如果给定的数组已经排好序呢？你将如何优化你的算法？
4.如果 nums1 的大小比 nums2 小很多，哪种方法更优？
5.如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？

1
哈希表来解决问题，将数组nums1哈希到哈希表中，然后继续将数组nums2哈希到哈希表中，如果发生哈希碰撞则统计加1，最后可以得出数组的交集。时间复杂度也就是哈希所有元素的复杂度O(n)。这里我使用HashMap来处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        ArrayList<Integer> temp = new ArrayList<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            Integer value = hashMap.get(nums1[i]);
            hashMap.put(nums1[i], (value == null ? 0 : value) + 1);
        }
​
        for (int i = 0; i < nums2.length; i++) {
            if (hashMap.containsKey(nums2[i]) && hashMap.get(nums2[i]) != 0) {
                temp.add(nums2[i]);
                hashMap.put(nums2[i], hashMap.get(nums2[i]) - 1);
            }
        }
        int[] result = new int[temp.size()];
        for (int i = 0; i < temp.size(); i++) {
            result[i] = temp.get(i);
        }
        return result;
    }
}

1
2
3
4
5
6
7
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
​
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
解法的关键在于弄明白什么情况下会产生进位
​
想让个位+1进位，那么个位必须为9
​
想让十位+1进位，那么十位必须为9，想要产生进位carry，那么必须由个位进位而来。想让个位进位，个位必须为9.
​
想让百位+1进位，那么百位必须为9，想要产生进位carry，那么必须由十位进位而来，想让十位进位，那么十位必须为9，想要产生进位，个位必须为9。
​
根据以上可以推论得出两种情况：
1.最高位进位
2.最高位不进位
​
最高位进位 
//若最高位进位，那么比他低的位数字都为9，且加1后都为0，需要初始化一个长度为(lenght+1)的新数组，0位置为1代表进位
​
最高位不进位 
//若最高位不进位，那么不需要产生新数组，后续数字由更低位计算而来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] plusOne(int[] digits) {
       int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (carry == 0) {
                return digits;
            }
            int tmp = digits[i] + carry;
            carry = tmp / 10;
            digits[i] = tmp % 10;
        }
        if (carry != 0) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result;
        }
        return digits;
    }
}

1
2
1.遍历数组，使用慢指针去记录非零整数的个数，同时并移动位置
2.得到0的个数 倒序遍历数组 补位0 知道个数满足记录下的0的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void moveZeroes(int[] nums) {
        int unZeroCount = 0;//慢指针去记录非0整数的个数，同时并移动位置
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                nums[unZeroCount] = nums[i];
                ++unZeroCount;
            }
        }
        //数组末尾有这么多个0  去补位
        int zeroCount = len - unZeroCount;
        for (int i = len - 1; i > 0; i--) {
            if (zeroCount == 0) return;
            nums[i] = 0;
            --zeroCount;
        }
    }
}

1
2
3
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

1
我希望通过O(n)的时间复杂度完成要求。第一遍O(n)的算法将每个数据a对应的target-a建立查询的数据结构，例如Hash表；第二遍遍历时，查询每个数是否在Hash表中，每次查询时间复杂度为O(1)，总的时间复杂度是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) map.put(nums[i], i);
        for (int i = 0; i < nums.length; i++) {
            int value = target - nums[i];
            //差值存在哈希表中且角标不是当前被减数自己 防止 6-3=3这种的清空的出现
            if (map.containsKey(value) && map.get(value) != i) {
                int index = map.get(value);
                if (i < index) return new int[]{i, index};
                return new int[]{index, i};
            }
        }
        return new int[0];
    }
}

1
//你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
​
原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
​
给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 
​
原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]
​

1
2
3
4
5
坐标旋转(顺时针)
90°（相当于逆时针270°）：a[i][j]=b[j][n-i-1];
//转置矩阵  行变列
创建一个新的矩阵：b[i][j] = a[j][i];
对原矩阵进行求转置矩阵，转置矩阵每一行进行反转即可得到旋转90°后的矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        int length = matrix.length;
        for (int i = 0; i < length / 2; i++) {
            for (int j = 0; j < (length + 1) / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[length - j - 1][i];
                matrix[length - j - 1][i] = matrix[length - i - 1][length - j - 1];
                matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
                matrix[j][length - i - 1] = tmp;
            }
        }
    }
}