int removeDuplicates(int* nums, int numsSize){
	int fast, last;	// 双指针

    if(numsSize==0){
        return 0;
    }
    
	for (last=0,fast = 1; fast < numsSize; fast++){

		if (nums[last] != nums[fast]) {
            /* 如果指的元素不同，就将fast所指的元素给last所指的后一个元素，当然，需要last事先增一 */
			nums[++last] = nums[fast];
		}

	}

	return last + 1;
}

int maxProfit(int* prices, int pricesSize) {

    /* 不要忘记特殊情况 */
	if (pricesSize < 2) {
		return 0;
	}

	int td_price = prices[0];	// td_price为当天价格，从第 prices[0]开始
	int pro = 0;				// 初始利润设置为 pro=0

	for (int i = 1; i < pricesSize; i++)
	{
        /* 从第二天开始，如果明天的价格高于今天，就买，利润增加 */
		if (prices[i] > td_price) {
			pro += (prices[i] - td_price);
		}
        /* 过一天，明天变今天 */
		td_price = prices[i];

	}
	return pro;
}

/* 逆序函数，注意下标的操作 */
void reverse(int *arr, int left, int right) {

	for (int i = 0; i < (right - left + 1) / 2; i++)
	{
		int temp = arr[right - i];
		arr[right - i] = arr[left + i];
		arr[left + i] = temp;
	}

}
/* 进行旋转 */
void rotate(int* nums, int numsSize, int k) {

    // 注意特殊情况的处理
	if (numsSize == 0 || !nums) {
		return;
	}

    // 以防循环次数 > numsSize
     k = k % numsSize;
    
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, numsSize - k, numsSize - 1);
	reverse(nums, 0, numsSize - 1);
}

#define MAX 1000000
int temp_arr[MAX] = { 0 };

/* merge two arr */
void merge(int begin, int middle, int end, int arr1[], int arr2[]);
/* sort arr with merge sort */
void merge_sort(int arr[], int begin, int end);

bool containsDuplicate(int* nums, int numsSize) {

	if (numsSize <= 1) return false;	// 注意特殊情况
	
	merge_sort(nums, 0, numsSize - 1);	// 先进行排序

	for (int i = 0; i < numsSize - 1; i++) {
		if (nums[i] == nums[i+1]) {
			return true;
		}
	}
	return false;
}

/* merge two arr */
void merge(int begin, int middle, int end, int arr1[], int arr2[]) {

	int i = begin;
	int j = middle + 1;
	int k = begin;

	while (i <= middle && j <= end) {
		if (arr1[i] <= arr1[j]) {

			arr2[k++] = arr1[i++];

		}
		else
		{
			arr2[k++] = arr1[j++];
		}
	}

	while (i <= middle)	arr2[k++] = arr1[i++];
	while (j <= end)	arr2[k++] = arr1[j++];

}

/* sort arr with merge sort */
void merge_sort(int arr[], int begin, int end) {

	int m;

	if (begin == end) {

		return;	// if begin==end -> arr has one number,over

	}
	else {

		m = (begin + end) / 2;
		merge_sort(arr, begin, m);		// sorted front part of arr
		merge_sort(arr, m + 1, end);	// sorted latter part of arr 
		merge(begin, m, end, arr, temp_arr);	//merge arr
		for (int i = begin; i <= end; i++) {
			arr[i] = temp_arr[i];
		}
	}
}

int singleNumber(int* nums, int numsSize) {

    // 特殊情况的处理
	if (numsSize == 1)
	{
		return nums[0];
	}

	// 先排序
	merge_sort(nums, 0, numsSize - 1);

    // 首末元素不好判断，就先进行判断
	if (nums[0] != nums[1] && nums[1]==nums[2]) {
		return nums[0];
	}
	else if (nums[numsSize-1] != nums[numsSize-2]) {
		return nums[numsSize - 1];
	}

	// 在这之前先判断第一个数和最后一个数
	for (int i = 1; i < numsSize - 1; i++)
	{
        // 判断前后元素是否等于这个数
		if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
			return nums[i];
		}

	}
    
    // 如果此处没有返回，会报错，便随便加上一句，理论上不会走到这里
    return -1;
	
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/* 判断元素在数组中出现几次 */
int If_In_Array(int number, int numsSize, int *nums) ；

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {

	/* 以nums1的长度构建数组 */
	int *numret = (int*)malloc(sizeof(int)*nums1Size);

	int i3 = 0;	// i3作为结果数组的下标，刚好可以统计结果数组中元素的个数

	for (int i1 = 0; i1 < nums1Size; i1++)
	{
		int n1 = 0, n2 = 0, n3 = 0;
		n1 = If_In_Array(nums1[i1], nums1Size, nums1);
		n2 = If_In_Array(nums1[i1], nums2Size, nums2);
		n3 = If_In_Array(nums1[i1], i3, numret);

		if (n3 == 0) {
			if (n1 == n2) for (int p = 0; p < n1; p++) numret[i3++] = nums1[i1];
			else if (n1 > n2) for (int p = 0; p < n2; p++) numret[i3++] = nums1[i1];
			else if (n1 < n2)for (int p = 0; p < n1; p++) numret[i3++] = nums1[i1];
		}
	}

	*returnSize = i3;

	return numret;

}
/* 判断元素在数组中出现几次 */
int If_In_Array(int number, int numsSize, int *nums) {

	int count = 0;

	for (int i = 0; i < numsSize; i++)
	{
		if (nums[i] == number) count++;
	}

	return count;

}

int* plusOne(int* digits, int digitsSize, int* returnSize) {

	//  基本思路 逢 9 进一 不为9 +1 然后结束

	// 1 先判断是否全为9 分两种情况 1）全为9 2） 第一位不是9
	int is9 = 1;
	for (int i = 1; i < digitsSize; i++) 
		if (digits[i] != 9) {
			is9 = 0;
			break;
		}
	if (is9 == 1) {
		if (digits[0] == 9) {
			// 如果第一位也是9
			// 此时全为9
			int *redigits = (int*)malloc(sizeof(int)*(digitsSize + 1));
			redigits[0] = 1;
			for (int i = 1; i < digitsSize + 1; i++)
			{
				redigits[i] = 0;
			}
			*returnSize = digitsSize + 1;
			return redigits;
		}
		else{
			// 此时第一位不是9
			int *redigits = (int*)malloc(sizeof(int)*(digitsSize));
			redigits[0] = digits[0] + 1;
			for (int i = 1; i < digitsSize; i++)
			{
				redigits[i] = 0;
			}
			*returnSize = digitsSize;
			return redigits;
		}
		
	}

	// 如果有一位不是9
	int *redigits = (int*)malloc(sizeof(int)*(digitsSize));
	redigits = digits;
	/*for (int n = 0; n < digitsSize; n++) {
		redigits[n] = digits[n];

	}*/
	for (int p = digitsSize - 1; p > -1; p--) {
		if (redigits[p] == 9) {
			redigits[p] = 0;
            continue;
		}
		if (redigits[p] != 9) {
			redigits[p] = redigits[p] + 1;
            break;
		}
	}
	*returnSize = digitsSize;
	return redigits;
}

void moveZeroes(int* nums, int numsSize) {
	int k = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (nums[i] != 0) {
            int t = nums[k];
			nums[k++] = nums[i];
			nums[i] = t;
		}
	}
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
	/* 先处理一下特殊情况 */
    if (numsSize == 0) {
		*returnSize = 0;
		return NULL;
	}
	else if (numsSize == 1) {
		int *ret1 = (int*)malloc(sizeof(int) * 1);
		ret1[0] = 0;
		*returnSize = 1;
		return ret1;
	}
    
	int *ret = (int*)malloc(sizeof(int) * 2);
    
	for (int i = 0; i < numsSize; i++)
	{
		for (int j = 0; j < numsSize; j++) {
	
			if (i == j) continue;
			else{
				if (nums[i] + nums[j] == target) {
					ret[0] = i;
					ret[1] = j;
				}
			}
		}
	}
	*returnSize = 2;
	return ret;
}

bool isValidSudoku(char** board, int boardSize, int* boardColSize) {

	int row[9][10] = { 0 };
	int arr[9][10] = { 0 };
	int box[9][10] = { 0 };

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] != '.') {
				int num = board[i][j] - '0';		// 得到此数字对应的整数值
				row[i][num]++;						// 代表 在第i行 数字 num 出现次数 +1
				arr[j][num]++;						// 代表 在第j列 数字 num 出现次数 +1
				box[(i / 3) * 3 + (j / 3)][num]++;	// 代表 在第(i / 3) * 3 + (j / 3)个小九宫格中 数字 num 出现次数 +1
				if ((row[i][num] > 1) || (arr[j][num] > 1) || (box[(i / 3) * 3 + (j / 3)][num] > 1)) {	
					return false;
				}
			}
		}
	}
	return true;
}

void rotate(int** matrix, int matrixSize, int* matrixColSize) {

	// 先变换行，因为每一行可以作为一整块，在存储操作上比较方便
	for (int i = 0, j = matrixSize - 1; i < j; ++i, --j)   /* 将矩阵的第i行和第j行互换 */
		swap_row(matrix, matrixSize, i, j);

	// 再对矩阵进行转置
	transposed_matrix(matrix, matrixSize);
	
}

/* 求转置矩阵 */
void transposed_matrix(int **matrix, int matrixSize) {

	for (int i = 0; i < matrixSize; i++) {
		for (int j = i; j < matrixSize; j++) {
			int temp = matrix[i][j];
			matrix[i][j] = matrix[j][i];
			matrix[j][i] = temp;
		}
	}
}

/* 将矩阵第i行和第size-i行互换 */
void swap_row(int **matrix, int matrixSize, int i, int j) {

	// 申请存储单元，方便按行存储，只需交换指针，即可每次操作改变一行
	int *t = (int*)malloc(sizeof(int)*matrixSize);
	t = matrix[i];
	matrix[i] = matrix[j];
	matrix[j] = t;

}