[C++知识库]顺序表数组OJ题

1、实现顺序表的增删查改
头文件的编写：

#pragma once
#include <stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLDateType;

typedef struct SeqList
{
	SLDateType *a;
	size_t size;
	size_t capacity;
}SeqList;

//数据的增删查改
void SeqListInit(SeqList*ps);
void SeqListDestory(SeqList*ps);
void SeqListPrint(SeqList*ps);
void SeqListPushBack(SeqList*ps);
void SeqListPushFront(SeqList*ps);
void SeqListPopFront(SeqList*ps);
void SeqListPopBack(SeqList*ps);
//顺序表查找
int SeqListFind(SeqList *ps, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList * ps, size_t pos, SLDateType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList *ps, size_t pos);

主要文件的编写：

#include "8.16SeqList.h"
void SeqListInit(SeqList*ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void SeqListDestory(SeqList*ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}
void SeqListPrint(SeqList*ps)
{
	assert(ps);
	for (size_t i = 0; i < ps->size; +i)
	{
		printf("%d", ps->a[i]);
	}
	printf("%\n");
}
void CheckCapacityz(SeqList*ps)
{
	if (ps->size == ps->capacity)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (SLDateType*)realloc(ps->a, newcapacity*sizeof(SLDateType));
		ps->capacity == newcapacity;
	}
}
void SeqListPushBack(SeqList*ps, SLDateType x)
{
	SeqListInsert(ps, ps->size, x);
}
void SeqListPushFront(SeqList*ps, SLDateType x)
{
	assert(ps);
	size_t end = ps->size;
	while (end > 0)
	{
		ps->a[end] = ps->a[end - 1];
		--end;
	}
	ps->a[0] = x;
	++ps->size;

	SeqListInsert(ps, 0, x);
}
void SeqListPopFront(SeqList *ps)
{
	assert(ps);
	SeqListErase(ps, 0);
}
void SeqListPopBack(SeqList*ps)
{
	assert(ps);
	SeqListErase(ps, ps->size - 1);

}

int SeqListFind(SeqList*ps,SLDateType x)
{
	for (size_t i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListInser(SeqList*ps, size_t pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->size);
	CheckCapacity(ps);
	size_t end = ps->size;
	while (end > pos)
	{
		ps->a[end] = ps->a[end - 1];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}
void SeqListErase(SeqList*ps, size_t pos)
{
	assert(ps&&pos < ps->size);
	size_t start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

2、给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
用C语言解决：

#include<stdio.h>
int removElement(int *nums, int numsSize, int val)
{
	int left = 0;
	for (int right = 0; right < numsSize; right++)
	{
		if (nums[right] != val)
		{
			nums[left] = nums[right];
			left++;
		}
	}
	return left;
}

用c++解决：

class Solution
{
public :
	int removeElement(vector<int>&nums, int val)
	{
		int n = nums.size();
		int left = 0;
		for (int right = 0; right < n; right++)
		{
			if (nums[right] != val)
			{
				nums[left] = nums[right];
				left++;
			}
		}
		return left;
	}
};

3、给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
用c语言

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

用c++

class Solution
{
public:
	int removeDuplicates(vector<int>nums)
	{
		int n = nums.size();
		if (n == 0)
		{
			return 0;
		}
		int fast = 1, slow = 1;
		while (fast < n)
		{
			if (nums[fast] != nums[fast - 1])
			{
				nums[slow] = nums[fast];
				++slow;
			}
			++fast;
		}
		return slow;
	}

};

4、两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
C语言

int cmp(int*a, int *b)
{
  	return *a - *b;
}
void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n)
{
	for (int i = 0; i != n; ++i)
	{
		nums1[m + i] = nums2[i];
	}
	qsort(nums1, nums1Size, sizeof(int), cmp);
}

c++

class Solution
{
public:
	void merge(vector<int>&nums1, int m, vector<int>&nums2, int n)
	{
		for (int i = 0; i != n; ++i)
		{
			nums1[m + i] = nums2[i];
		}
		sort(nums1.begin(), nums1.end());
	}
};

这题的思路就是先将两个数组合并，然后再在数组内排序即可。
5、给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
C语言

void rotate(int*nums, int numsSize, int k)
{
	int newArr[numsSize];
	for (int i = 0; i < numsSize; ++i)
	{
		newArr[(i + k) % numsSize] = nums[i];
	}
	for (int i = 0; i < numsSize; ++i)
	{
		nums[i] = newArr[i];
	}
}

c++

class Solution
{
public:
	void rotate(vector<int>&nums, int k)
	{
		int n = nums.size();
		vector<int> newArr(n);
		for (int i = 0; i < n; ++i)
		{
			newArr[(i + k) % n] = nusm[i];
		}
		nums.assign(newArr.begin(), newArr.end());
	}
};

这题的解题思路也是新建一个数组，将原数组的每一个数字依次加上k值%原数组中的元素个数放到新数组中，最后将新数组再拷贝到原数组之中。
6、对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
C语言：

int *addToArrayFrom(int*num, int numSize, int k, int *returnSize)
{
	int *res = malloc(sizeof(int)*fmax(10, numSize + 1));
	*returnSize = 0;
	for (int i = numSize - 1; i > 0; --i)
	{
		int sum = num[i] + k % 10;
		k /= 10;
		if (sum >= 10)
		{
			k++;
			sum -= 10;
		}
		res[(*returnSize)++] = sum;
	}
	for (; k > 0; k /= 10)
	{
		res[*(returnSize)++] = k % 10;
	}
	for (int i = 0; i < (*returnSize) / 2;i++)
	{
		int tmp = res[i];
		res[i] = res[(*returnSize) - 1 - i];
		res[(*returnSize) - 1 - i] = tmp;
	}
	return res;
}

c++：

class Solution
{
public:
	vector<int> addToArrayForm(vector<int>&num, int k)
	{
		vector<int> res;
		int n = num.size();
		for (int i = n - 1; i >= 0; --i)
		{
			int sum = num[i] + k % 10;
			k /= 10;
			if (sum >= 10)
			{
				k++;
				sum -= 10;
			}
			res.push_back(sum);
		}
		for (; k > 0; k /= 10)
		{
			res.push_back(k % 10);
		}
		reverse(res.begin(), res.end());
		return res;
	}
};

解题思路：从数组低位开始相加到高位，若当前位置相加结果大于十将进位的一加到下一高位的计算中。