[算法] leetcode顺序表相关题目详解

ゞ浴缸里的玫瑰 2023-01-21 10:27 16阅读 0赞

### 目录 ###

*  1. leetcode 203.移除数组元素
 *   *  解法一
     *  解法二
 *  2. leetcode 26. 删除有序数组中的重复项
 *   *  解法
 *  3. leetcode88. 合并两个有序数组
 *   *  解法一
     *  解法二(推荐)
 *  4. 189. 旋转数组
 *   *  解法一
     *  解法二
 *  5. 989. 数组形式的整数加法
 *   *  解法

# 1. leetcode 203.移除数组元素 #

/*203. 移除数组元素 * 示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 https://leetcode-cn.com/problems/remove-element/

该题分三种思路

## 解法一 ##

数组中元素多少是固定的，可以通过遍历数组的方法，将数组遍历一编，将满足条件的元素继续放入数组中，不满足条件的元素不放入数组，最后返回数组与数组大小。

// 遍历数组，将不用删除的元素放入数组
    int removeElement1(int* nums, int numsSize, int val) { 
        int j = 0;
        for (int i = 0; i < numsSize; i++)
        { 
            if (nums[i] != val)
            { 
                nums[j++] = nums[i];
            }
        }
        return j;
    }

## 解法二 ##

使用计数器记录待删除元素出现次数，判断当前元素是否为待删除元素，如果是，则计数器自增1，如果不是，将该元素向前搬移`计数器大小`步，，计数器大小代表了当前元素应向数组的什么位置存放数据

// 使用计数器记录元素出现个数，如果当前值不是删除的元素则将该元素向前移动count步
    int removeElement2(int* nums, int numsSize, int val)
    { 
        int count = 0;
    
        for (int i = 0; i < numsSize; i++)
        { 
            if (val == nums[i])
                count++;
            else
                nums[i - count] = nums[i];
        }
    
        return numsSize - count;
    }

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

* 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
    不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     
    示例 1：
    输入：nums = [1,1,2]
    输出：2, nums = [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]
    解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
    * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

## 解法 ##

原地搬移数组中元素，因为数组为有序数组，则使用两个指针，两个指针都指向数组头，一个指针用来表示已存放数据的多少，一个指针用来表示当前遍历到数组的第几位。通过两个指针进行判断。  
  第一步，将数组第一位直接放入数组，第二步，判断待加入数组与以放入数组的元素是否相同，相同则跳过。

// 因为数组有序，则将第一项加入数组，判断新加入项是否等于已构造好的数组最后一项，相同则不加入
    int removeDuplicates(int* nums, int numsSize) 
    { 
    	// 如果长度为1 则数组不重复
    	if (numsSize < 2)
    		return numsSize;
    
    	int count = 0;
    
    	//nums[count++] = nums[0];
    	for (int i = 1; i < numsSize; i++)
    	{ 
    		if (nums[count] != nums[i])
    			nums[++count] = nums[i];
    	}
    
    	return ++count;
    }

# 3. leetcode88. 合并两个有序数组 #

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
    初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
    
    示例 1：
    输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    输出：[1,2,2,3,5,6]
    示例 2：
    输入：nums1 = [1], m = 1, nums2 = [], n = 0
    输出：[1] 
    
    提示：
    	nums1.length == m + n
    	nums2.length == n
    	0 <= m, n <= 200
    	1 <= m + n <= 200
    	-109 <= nums1[i], nums2[i] <= 109
    
    * https://leetcode-cn.com/problems/merge-sorted-array/

## 解法一 ##

根据题目要求，要将所有数据放入num1数组中，所以使用双指针来进行计算。  
  两个指针分别遍历两个数组，其中比较两个下标位置元素值大小，哪个元素小，就将哪个元素放入数组。直到遍历完一个数组，最后将没有遍历完的数组元素一次放入num1中。  
  该方法需要新开辟一个数组空间，空间复杂度较高。

// 1. 使用两个下标，分别遍历两个数组，哪个下标的元素小，就将哪个小标元素放入数组\
    // 需要辅助空间，不然在比较时会导致错误的数据读取
    void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
    { 
    	int pnums1 = 0;
    	int pnums2 = 0;
    	int count = 0;
    	int* arr = (int*)malloc(sizeof(int) * (m + n));
    
    	// 逐个比较，将较大值放入数组
    	while (pnums1 < m && pnums2 < n)
    	{ 
    		if (nums1[pnums1] >= nums2[pnums2])
    		{ 
    			arr[count++] = nums2[pnums2++];
    		}
    		else
    		{ 
    			arr[count++] = nums1[pnums1++];
    		}
    	}
    
    	// 判断两个数组中哪个没有完成数据的转移，将剩余数据进行转移
    	while (pnums1 < m)
    		arr[count++] = nums1[pnums1++];
    	while(pnums2 < n)
    		arr[count++] = nums2[pnums2++];
    
    	nums1 = arr;
    }

## 解法二(推荐) ##

该方法与上述方法大致相同，但是不用开辟新的空间。  
  因为nums1中的空间已经足够存储，所以从两个数组的最后开始遍历，将较大元素放入，num1中的最后一个位置。

// 2.同样使用两个下标，第一个下标指向第一个数组的最后一个元素的位置，第二个下标指向第二个数字中最后一个元素的位置
    // 使用一个指针指向最后一个空间的位置，将两个下标指向的元素最大值放到，空间最后一个位置处
    void merge2(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
    { 
    	int end = m + n - 1;
    	int i = m - 1;
    	int j = n - 1;
    
    	// nums1 数组长度较长，所以数据会存储在该数组中，存储时数据有序，所以在比对完nums2时，nums1有可能没有比对到头的位置
    	// 要保证nums2全部插入到nums1中，nusm1中本身按照顺序存有数据，所以nums1 没有比对到头也不影响结果
    	while (j >= 0)
    	{ 
    		if (i >= 0 && nums1[i] > nums2[j])
    		{ 
    			nums1[end--] = nums1[i--];
    		}
    		else
    		{ 
    			nums1[end--] = nums2[j--];
    		}
    	}
    }

# 4. 189. 旋转数组 #

189. 旋转数组
    给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
    
    示例 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]
    
    示例 2:
    输入：nums = [-1,-100,3,99], k = 2
    输出：[3,99,-1,-100]
    解释: 
    向右旋转 1 步: [99,-1,-100,3]
    向右旋转 2 步: [3,99,-1,-100]
    
    * https://leetcode-cn.com/problems/rotate-array/

## 解法一 ##

可以将旋转个数的元素，进行存储，最后对原数组内容进行移动，最后将旋转的元素存入数组中

## 解法二 ##

采用先局部逆置，后整体逆置的思想进行解决  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

void reverse(int* nums, int start, int end)
    { 
    	while (start < end)
    	{ 
    		int num = nums[start];
    		nums[start] = nums[end];
    		nums[end] = num;
    		start++;
    		end--;
    	}
    }
    
    // 先局部逆置元素，最后整体逆置数组元素，即可达到旋转效果
    void rotate(int* nums, int numsSize, int k) 
    { 
    	reverse(nums, 0, numsSize - k - 1);
    	reverse(nums, numsSize - k, numsSize - 1);
    	reverse(nums, 0, numsSize - 1);
    }

# 5. 989. 数组形式的整数加法 #

989. 数组形式的整数加法
    * 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
    
    给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
    
    示例 1：
    输入：A = [1,2,0,0], K = 34
    输出：[1,2,3,4]
    解释：1200 + 34 = 1234
    
    示例 2：
    输入：A = [2,7,4], K = 181
    输出：[4,5,5]
    解释：274 + 181 = 455
    
    示例 3：
    输入：A = [2,1,5], K = 806
    输出：[1,0,2,1]
    解释：215 + 806 = 1021
    
    示例 4：
    输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
    输出：[1,0,0,0,0,0,0,0,0,0,0]
    解释：9999999999 + 1 = 10000000000
    
    提示：
    1 <= A.length <= 10000
    0 <= A[i] <= 9
    0 <= K <= 10000
    如果 A.length > 1，那么 A[0] != 0
    
    https://leetcode-cn.com/problems/add-to-array-form-of-integer/

## 解法 ##

1. 申请存储空间，因为待加数长度不定，所以要申请足够的空间
    	`size > 5 ? szie+1 : 5+1`
    2. 取出数组中的最后一位与数字的个位，进行相加，将加数地位存入数组，并存储进位
    3. 判断待加数是否为0，如果k不为0，并且数组中元素已经加完，则将待加数按位存入数组
    4. 判断数组中最前方元素是否含有空余位置，如果有则将数组向前搬移

// 输入：A = [1,2,0,0], K = 34
    // 思路：取出数组最后一个元素，和k中的个位数值相加，有进位则将进位存储到进位标志位中，并且将计算结果放入数组
    int* addToArrayForm(int* num, int numSize, int k, int* returnSize) 
    { 
    	// 申请保存数据的空间
    	int size = numSize > 5 ? numSize + 1 : 5 + 1;
    
    	int* returnArr = (int*)calloc(size, sizeof(int));
    
    	int arrLen = size - 1;
    	int count = 0;
    	// 按位计算
    	while(numSize > 0)
    	{ 
    		k += num[numSize - 1];
    		returnArr[arrLen] = k % 10;
    		k /= 10;
    		arrLen--;
    		count++;
    		numSize--;
    	}
    
    	// 如果k没有被除尽
    	while (k > 0)
    	{ 
    		returnArr[arrLen--] = k % 10;
    		k /= 10;
    		count++;
    	}
    
    	// 判断是否用完了申请的空间，如果有空余空间没有使用，则将后方数据向前移动
    	if (*returnSize < size)
    	{ 
    		memmove(returnArr, returnArr+(size - count), sizeof(int) * count);
    	}
    	*returnSize = count;
    
    	return returnArr;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/5a00550841a04954858733dc512ea7de.png