Leetcode——初级算法（数组篇）

数组

删除排序数组中的重复项

int removeDuplicates(int* nums, int numsSize) 
{
	assert(nums != NULL);
	assert(numsSize != NULL);
	int fast = 1, slow = 1;
	while (fast < numsSize)
	{
		if (nums[fast] != nums[fast - 1])        //找到与fast前驱不重复的元素
		{
			nums[slow] = nums[fast];             //slow始终指向元素第一次出现的位置
			slow++;
		}
		fast++;                                  //向后遍历
	}
	return slow;                                 //真实长度
}

思路：双指针，首先使fast和slow指针指向同一位置，将fast所指向元素进行其前驱元素比较。若不相等（即不重复），slow指向元素更改值为fast指向元素，slow指向其后继元素。fast指向其后继元素，直至数组末尾。

注：nums数组已经有序。

买卖股票的最佳时机 II

int maxProfit(int* prices, int pricesSize) 
{
	assert(prices != NULL);
	assert(pricesSize != NULL);
	int result = 0;
	for (int i = 1; i < pricesSize; i++)
	{
		if (prices[i] > prices[i - 1])                //比前一天多就卖
			result += prices[i] - prices[i - 1];
	}
	return result;
}

思路：贪心算法，只要价格比前一天多就卖。

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

方法一：

void Reverse_Arr(int* nums, int start, int end)    //反转数组
{
	assert(nums != NULL);
	assert(start < end);
	int fast = start - 1, slow = end - 1;
	while (slow > fast)
	{
		int temp = nums[fast];
		nums[fast] = nums[slow];
		nums[slow] = temp;
		fast++;
		slow--;
	}
}
void rotate_2(int* nums, int numsSize, int k)		//反向思维	
{
	assert(nums != NULL);
	assert(numsSize != NULL);

	Reverse_Arr(nums, 1, numsSize);			        //整体反转
	Reverse_Arr(nums, 1, k);				        //前半部分反转
	Reverse_Arr(nums, k + 1, numsSize);		        //后半部分反转
}

如图所示，对于数组 [1,2,3,4,5,6,7]，k = 3。

方法二：

//拷贝整体数组
void rotate(int* nums, int numsSize, int k)
{
	assert(nums != NULL);
	assert(numsSize != NULL);

	int* newArr = (int*)malloc(numsSize * sizeof(int));
	if (newArr == NULL)
		exit(0);
	for (int i = 0; i < numsSize; i++)
		newArr[(i + k) % numsSize] = nums[i];
	for (int i = 0; i < numsSize; i++)
		nums[i] = newArr[i];
	free(newArr);
}

思路：定义新的数组，分析可知，其向右轮转实际是将数组前半部分整体拷贝到末尾，故对其下标进行取模运算，即可完成向后拷贝。

数组

存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现至少两次，返回 true ；如果数组中每个元素互不相同，返回 false 。

bool containsDuplicate_2(vector& nums) 
{                                                   //先排序，比较相邻元素
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 1; i++)       //注意size-1
        if (nums[i] == nums[i + 1])
            return true;
    return false;
}

题解思路：重复出现意味着排序后两个元素相邻，故先进行排序，然后在依次比较。

注：也可使用哈希表记录每个元素的出现次数，若存在次数＞1，则返回true，反之返回false。

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

int singleNumber(vector& nums) {   //查询单个元素
    sort(nums.begin(), nums.end());
    int length = nums.size();
    int fast = 0, slow = 1;
    //for (int i = 0; i < length; i++)
    //    cout << nums[i] << " ";
    //cout << endl;
    //cout << length << endl;
    while (fast < length - 1)
    {
        //cout << nums[fast] << "??" << nums[slow] << endl;
        if (nums[fast] == nums[slow])
        {
            fast += 2;
            slow += 2;
        }
        else
            return nums[fast];
    }
    //cout << fast << "  " << slow << endl;
    if (length % 2 != 0 && slow == length)//  奇数列最后一个元素为单个
        return nums[length - 1];
}

题解思路：和上题类似，先排序，每两个进行一次比较若不相等则为fast所指向的元素（其前一项已经判断过），注意奇数序列的情况。

两个数组的交集Ⅱ

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。

返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

vector intersect(vector& nums1, vector& nums2) {
    vector result;
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());       //排序

    int fast = 0, slow = 0;                 //分别为nums1，nums2的下标
    int i = 0;
    while (fast != nums1.size()&&slow != nums2.size())      //两个都遍历完成
    {
        if (nums1[fast] == nums2[slow])
        {
            result.push_back(nums1[fast]);
            fast++;
            slow++;
        }
        else if (nums1[fast] > nums2[slow])
            slow++;
        else
            fast++;
    }
    return result;
}

题解思路：和上两题类似，先对数组进行排序，若相等则赋值到新数组，若不想等，则较小的序列下标自增，直至两个数组都遍历完成。

加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

vector plusOne(vector& digits) {
    int length = digits.size();
    int flag = 0, temp = length - 1;
    vector result;
    for (int i = 0; i < length; i++)
        if (digits[i] == 9)
            flag++;
    if (flag == length)                 //进位
    {
        result.push_back(1);
        for (int i = 0; i < length; i++)
            result.push_back(0);
    }
    else if(digits[0] == 0)
    {
        result.push_back(1);            //0
    }
    else
    {
        temp = length - 1;
        while (digits[temp] == 9)       //+1要进位
        {
            digits[temp] = 0;
            temp--;
        }
        digits[temp] += 1;
        for (int i = 0; i < length; i++)
            result.push_back(digits[i]);
    }
    return result;
}

题解思路：首先考虑全为9的情况，结果为1*10^n；然后是为0的情况，直接赋值1即可；其他情况只需要从后向前遍历即可遇到非9只对其自增，遇到9则需要将此位置赋0，其前一位+1即可。

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

void moveZeroes(vector& nums) 
{
    int n = nums.size();
    int fast = 0, slow = 0;
    while (fast < n)
    {
        if (nums[fast])
        {
            swap(nums[fast], nums[slow]);
            slow++;
        }
        fast++;
    }
}

题解思路：双指针，使得slow再抵达终点前始终指向0，fast向后遍历。

若fast所指向的值不为零，则两者元素互换，且同时自增，反之只有自身向后，slow不动

直至fast触碰到尾部。

两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

vector twoSum(vector& nums, int target) {
    vector result;
    int left = 0, right = 0;
    int n = nums.size();
    //int flag = 0;
    while (left < n - 1)
    {
        right = left + 1;
        while (right < n)
        {
            if (nums[left] + nums[right] == target)
            {
                result.push_back(left);
                result.push_back(right);
                return result;                        //flag++
            }
            right++;
        }
        left++;
    }
    return result;
}

题解思路：双指针，从左向右，每一个left与其后的所有元素各加一次，与目标值比较即可。若求多个结果，只需设置标志数组，表示出多少对结果即可。

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

bool isValidSudoku(vector>& board) {
    int rows[9][9] = { 0 };
    int columns[9][9] = { 0 };
    int subboxes[3][3][9] = { 0 };

    memset(rows, 0, sizeof(rows));
    memset(columns, 0, sizeof(columns));
    memset(subboxes, 0, sizeof(subboxes));

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            char c = board[i][j];
            if (c != '.')
            {
                int index = c - '0' - 1;    //出现的数
                rows[i][index]++;
                columns[j][index]++;
                subboxes[i / 3][j / 3][index]++;
                if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1)
                    return false;
            }
        }
    } 
    return true;
}

题解思路：使用三个矩阵，分别记录每行、每列、每3×3模块的数字0~9出现次数，若任意一个大于1，则返回false，反之为true。

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。

请不要使用另一个矩阵来旋转图像。

如图所示：

void rotate(vector>& matrix) {
    int n = matrix.size();
    //cout << n << endl;
    auto new_matrix = matrix;       //拷贝整体矩阵
    for (int i = 0; i < matrix.size(); i++)
        for (int j = 0; j < matrix.size(); j++)
            new_matrix[j][n - i - 1] = matrix[i][j];
    matrix = new_matrix;
}

题解思路：先将3×3矩阵整体拷贝，然后根据旋转所对应的下标关系对新矩阵进行依次赋值。赋值完成之后将新矩阵拷贝到原矩阵即可。

不难看出，一种对应关系为新矩阵的第一列对应原矩阵的第三行，新矩阵第二列为原矩阵第二行，新矩阵第三列为原矩阵第一行。也可以认为其关系为其他。

2022年5月22日

Leetcode——初级算法（数组篇）

C/C++/C#相关栏目本月热门文章