LeetCode基础算法-数组
算法 LeetCode 数组相关
1. 从排序数组中删除重复项
描述：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
解答思路：
- 双指针法，index指针指向当前已无重复数字数组的最后一位；i指针遍历nums数组。
- i与index处值相同时，i指针继续向后遍历。
- i与index处值相同时，将i处值复制给++index处。
- 无重复数组的长度为index+1。
代码：
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// index从索引0开始
int index = 0;
// i从索引1开始遍历
for (int i = 1; i < nums.length; i++) {
// 不相同则进行扩展，index永远指向符合条件数组的最后一个索引
if (nums[i] != nums[index]) {
nums[++index] = nums[i];
}
}
return index + 1;
}
2. 买卖股票的最佳时机
描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解答思路(贪心算法)：
- minPrice指向当前的最低价(假设为买入)，sum记录当前盈利的最大值。
- minPrice初始化为数组第一个值。
- 当前值<minPrice，此时卖出会赔钱，因此不能卖出，将当前值赋值给minPrice。
- 当前值>minPrice,此时卖出可以赚钱，因此卖出，将当前值赋值给minPrice。
代码实现:
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0){
return 0;
}
int sum = 0;
int minPrice = prices[0];
for(int i = 1;i<prices.length;i++){
if(prices[i]>minPrice){
// 此时卖出。
sum += prices[i] - minPrice;
minPrice = prices[i];
}else{
// 以当前价格买入
minPrice = prices[i];
}
}
return sum;
}
3. 旋转数组
描述：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [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]
解题思路：
- 如果K为数组长度的整倍数，那么无需做任何操作。
- k = k%length
- 循环右移数组，将数组的最后一个值赋值给数组第一个值。
public void rotate(int[] nums, int k) {
if (null == nums || nums.length == 0) {
return;
}
if (k % nums.length == 0) {
return;
}
k = k % nums.length;
int last;
for (int i = 0; i < k; i++) {
last = nums[nums.length - 1];
for (int j = nums.length - 1; j > 0; j--) {
nums[j] = nums[j - 1];
}
nums[0] = last;
}
}
4. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解题思路：
- 使用数学上的异或的特点，两个相同的数字异或等于0；
- 11=0,11^2=2
代码：
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int sigleNum = nums[0];
for (int i = 1; i < nums.length; i++) {
sigleNum ^= nums[i];
}
return sigleNum;
}
5. 两个数组的交集
描述：
给定两个数组，编写一个函数来计算它们的交集。
解题思路：
- 先排序，然后使用三个指针：i,j,z来遍历保存数据。
// 两个数组的交集
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return new int[0];
}
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] result;
if (nums1.length > nums2.length) {
result = new int[nums2.length];
} else {
result = new int[nums1.length];
}
int i = 0, j = 0, z = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
result[z++] = nums1[i];
i++;
j++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
i++;
}
}
int realResult[] = new int[z];
for (int index = 0; index < z; index++) {
realResult[index] = result[index];
}
return realResult;
}
6. 加1
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
解题思路：
- 从数组尾部遍历，职要当前位不为9，那么当前位+1，循环结束。
- 如果当前位为9，则当前位设置为0，继续向前遍历。
public int[] plusOne(int[] digits) {
if (digits == null || digits.length == 0) {
return new int[0];
}
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] == 9) {
digits[i] = 0;
} else {
digits[i] += 1;
return digits;
}
}
int[] newDigits = new int[digits.length + 1];
for (int i = 0; i < digits.length; i++) {
newDigits[i] = digits[i];
}
newDigits[0] = 1;
return newDigits;
}
7. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
解题思路：
- 使用双指针循环遍历。
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int index = 0, start = 0;
while (start < nums.length) {
if (nums[start] != 0) {
nums[index++] = nums[start];
}
start++;
}
while (index < nums.length) {
nums[index] = 0;
index++;
}
}
8. 两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
解题思路：
- 使用Map，遍历放入时检查map中是否已经存在余数值，存在立即返回；不存在继续遍历。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
if (map.get(target - nums[i]) != i) {
return new int[]{map.get(target - nums[i]), i};
}
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}
9. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
解题思路：
使用三个数组来记录是否已经存在该值的信息。
rowFlag[9][9]:rowFlag[i][c],第i行是否出现了值c。
colFlag[9][9]:rowFlag[c][j],c出现在第j列。
cellFalg[9][9]:cell[3(i/3)+j/3],第3(i/3)+j/3个单元中出现了c。
public boolean isValidSudoku(char[][] board) {
boolean rowFlag[][] = new boolean[9][9];
boolean colFlag[][] = new boolean[9][9];
boolean cellFlag[][] = new boolean[9][9];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; i++) {
if (board[i][j] >= '1' && board[i][j] <= '9'){
int c = board[i][j] - '1';
if (rowFlag[i][c] || colFlag[j][c] || cellFlag[3 * (i / 3) + j / 3][c]) {
return false;
}
rowFlag[i][c] = true;
colFlag[j][c] = true;
cellFlag[3 * (i / 3) + j / 3][c] = true;
}
}
}
return true;
}
10. 旋转数组
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
public void rotate(int[][] matrix) {
// 首先沿着对角线旋转
for (int i = 0; i < matrix.length; i++) {
for (int j = i + 1; j < matrix.length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 再沿着数组垂直中线进行旋转
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - 1 - j];
matrix[i][matrix.length - 1 - j] = temp;
}
}
}
网友评论