LeetCode刷题记录之数组（1）

43 阅读 0 评论 29 点赞

我是靠谱客的博主活泼口红，最近开发中收集的这篇文章主要介绍LeetCode刷题记录之数组（1），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

顺序按照简单到困难，依次闯关（题目编号为leetcode的序号）

等级：简单

主JAVA

来源：https://leetcode-cn.com/

1.两数之和（1）——哈希表查找

2.删除有序数组中的重复项（26）——双指针

3.移除元素（27）——双指针的优化

4.最大子序和（53）——动态规划

5.买卖股票的最佳时机（121）——动态规划

6.买卖股票的最佳时机II（122）——动态规划

1.两数之和

题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

解题思路：

暴力枚举：寻找数组中是否存在target-x。时间复杂度为O( $n^{2}$ )，空间复杂度为O(1)
哈希表：通过快速寻找数组中的目标元素降低时间复杂度，创建一个哈希表，对于每一个x，首先查询哈希表中是否存在target-x，然后将x插入到哈希表中，以此保证x不与自己匹配。时间复杂度O(n)，空间复杂度O(n)
- 算法：
1. 算出当前数字和目标数字的差
2. 遍历哈希表中是否存在该差，若存在则返回结果
3. 不存在，当前数字作为key，索引作为value存入哈希表

C

struct hashTable{
int key;
int value;
UT_hash_handle hh; //使用uthash
};
struct hashTable* ht;
struct hashTable* find(int ikey){
//寻找哈希表中是否存在ikey
struct hashTable* tmp;
HASH_FIND_INT(ht,&ikey,tmp);
//查找接口
return tmp;
}
void insert(int ikey, int ivalue){
//插入ikey到哈希表中
struct hashTable* it = find(ikey); //避免重复
if(it == NULL){
struct hashTable* tmp = malloc(sizeof(struct hashTable));
//分配空间
tmp->key = ikey;
tmp->value = ivalue;
HASH_ADD_INT(ht,key,tmp);
//插入接口
}else{
it->value = ivalue;
//覆盖
}
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
ht = NULL; //新建空的哈希表
for(int i = 0; i < numsSize; i++){
struct hashTable* it = find(target - nums[i]);
if(it != NULL){
int* ret = malloc(sizeof(int) * 2);
ret[0] = it->value;
ret[1] = i;
*returnSize=2;
return ret;
}
insert(nums[i], i);
}
*returnSize = 0;
return NULL;
}

JAVA

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(); //HashMap对象
for(int i = 0; i < nums.length; i++){
if(hashtable.containsKey(target-nums[i])){ //若哈希表中存在target-x
return new int[]{hashtable.get(target-nums[i]), i};
}
hashtable.put(nums[i],i); //插入
}
return new int[0];
}
}

Python3（用字典模拟哈希表）

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict() #用字典模拟哈希
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target-num], i]
hashtable[nums[i]] = i
return []

2.删除有序数组中的重复项

题目描述：给一个有序数组 nums ，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。【注：不能使用额外的数组空间】

解题思路：

双指针：由于题目要求为原地修改，不额外使用数组空间，因此考虑使用两个指针实现元素的删除和移动。设置两个指针分别为快指针(fast)和慢指针(slow)——快指针用于遍历数组；慢指针用于下一个非重复项要填入的位置。时间复杂度为O(n)
- 算法：
1. 初始时，fast和slow都指向下标1（因为是有序数组，下标为0的数字无比较性，从1开始即可）
2. fast依次遍历1到n-1的每个位置，对于每个位置，若 nums[fast] ≠ nums[fast-1]，说明该元素与之前的非重复，将 nums[fast] 的值复制到 nums[slow]
3. 当且仅当 nums[slow] 被赋值后，slow+1
4. 待fast遍历完后，返回slow

C（JAVA与Python3类似）

int removeDuplicates(int* nums, int numsSize){
//对特殊情况进行处理
if(numsSize == 0){
return 0;
}
int fast = 1;
int slow = 1;
while (fast < numsSize){
//遍历
if (nums[fast] != nums[fast-1]){
//基于数组有序的性质
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}

3.移除元素

题目描述：给定一个数组 nums 和一个值 val，要求原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，元素的顺序可以改变。不需要考虑数组中超出新长度后面的元素

解题思路：

双指针：与上一题的思路类似，设置双指针分别为快指针 fast 和慢指针 slow【最多遍历两次序列】
- 算法：
1. 初始时，fast和slow都指向下标0
2. fast依次遍历1到n-1的每个位置，对于每个位置，若 nums[fast] ≠ val，将 nums[fast] 的值复制到 nums[slow]，slow+1
3. 若 nums[fast] = val，slow不动，fast+1
4. 待fast遍历完后，返回slow

C（JAVA与Python3类似）

int removeElement(int* nums, int numsSize, int val){
int fast = 0;
int slow = 0;
for( ; fast < numsSize; fast++){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}

双指针的优化：注意到题目中的【元素的顺序可以改变】，因此考虑到序列中val元素数量较少的情况时，只需将其他元素移动取代val元素，同样满足题目要求。因此将两个指针分别位于数组的首尾，向中间遍历该序列。【最多遍历一次序列】

C（JAVA与Python3类似）

int removeElement(int* nums, int numsSize, int val){
int fast = numsSize;
int slow = 0;
while(slow < fast){
if(nums[slow] == val){
nums[slow] = nums[fast-1];
fast--;
}else{
slow++;
}
}
return slow;
}

4.最大子序和

题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解题思路：

动态规划：用 $f(i)$ 代表以第 $i$ 个数结尾的连续子数组的最大和，因此需要求出每个位置的 $f(i)$ ，然后返回 $f$ 数组中的最大值。重点在于如何求 $f(i)$ ——考虑nums[i] 是单独成为一段还是加入f(i-1) ，这取决于nums[i] 和 f(i−1)+nums[i] 的大小，于是可以写出以下的动态规划转移方程：

$f(i) = max{ f(i-1) + nums[i],nums[i]}$

空间复杂度O(n)，时间复杂度O(n)

注：由于 f(i) 只和 f(i-1)相关，于是可以只用一个变量来维护当前 f(i) 和 f(i-1) 的值，从而让空间复杂度降到O(1)

int maxSubArray(int* nums, int numsSize){
int value = 0; //用于维护f(i)和f(i-1)的值
int max = nums[0];
//最大值
for(int i=0; i < numsSize; i++){
value = fmax(value +nums[i], nums[i]); //求f(i)
max = fmax(value, max);
//在f(i)中比较得到最大值
}
return max;
}

动态规划题目：

使用最小花费爬楼梯：https://leetcode-cn.com/problems/min-cost-climbing-stairs/

5.买卖股票的最佳时机

题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

解题思路：对于每组 i 和 j （其中 j > i），我们需要找出 max( prices[j] - prices[i] )

一次遍历：在历史最低点时买入股票能保证利益最大化，因此遍历prices数组一遍，记录历史最低点，然后比较第 i 天卖出所得的利润：prices[i] - minprice

JAVA

class Solution {
public int maxProfit(int[] prices) {
int minprices = Integer.MAX_VALUE; //最低利润设置为最大值
int maxprofit = 0;
for(int i = 0; i <prices.length; i++){
if(prices[i] < minprices){
minprices = prices[i];
}else if(prices[i] - minprices > maxprofit){
maxprofit = prices[i] - minprices;
}
}
return maxprofit;
}
}

注：动态规划用于求解多阶段决策问题（动态规划问题的文法：只问最优解，不问具体的解）

6.买卖股票的最佳时机II

题目描述：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票），但不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）

解题思路：

动态规划：因为【不能同时参与多笔交易】，因此每天交易结束之后只可能存在手里有一支股票或者没有股票的状态（首先分析状态）。定义dp[i][0]为第i天交易完后手里没有股票的最大利润，dp[i][1]为第i天交易完后手里持有一支股票的最大利润

考虑dp[i][0]的转移方程，当天交易前可能持有一支股票（dp[i-1][1]）并要将其卖出，或者没有股票（dp[i-1][0]），因此列出以下的转移方程：

$dp[i][0] = maxleft { dp[i-1][0], dp[i-1][1] + prices[i]right }$

再考虑dp[i][1]的转移方程： $dp[i][1] = maxleft { dp[i-1][0] - prices[i], dp[i-1][1] right }$

JAVA

class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int [][] dp = new int [n][2];
//或直接用两个变量分别表示即可
//定义初始状态：
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1; i<n; i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][0] - prices[i],dp[i-1][1]);
}
return dp[n-1][0]; //最后手中持有的股票为0
}
}

贪心算法（只用于计算最大利润，计算的过程不是实际的交易过程）：以当前情况为基础根据某个优化测度做出最优选择（常把求解的问题数学模型化，分成若干个子问题，对每个子问题求解，得到子问题的局部最优解）

由于股票的购买次数没有限制，因此整个问题等价于寻找x个不相交的区间 $(l{i}, r{i}]$ 使得如下的等式最大化： $sum_{i=1}^{x}a[r{i}]-a[l{i}]$ （其中 li 表示买入，ri 表示卖出）

同时注意到 $a[r{i}]-a[l{i}]$ 可以简化为x个长度为1的区间 (li,li + 1)

从贪心的角度，每次选择贡献大于0的区间即能使得答案最大化，因此最后答案为：

$sum_{i=1}^{n-1}maxleft {0,a[i] - a[i-1]right }$

JAVA

class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for(int i=1; i< prices.length; i++){
profit = Math.max(0, prices[i] - prices[i-1]) + profit;
}
return profit;
}
}