1. 找出只出现了一次的数

ways1是正常的运算，将数组的每个元素都放在数组中遍历，遍历途中，如果有和自己相同的数，则count++，如果该数只出现了一次，则只能匹配到自己本身，count++只执行一次，此次遍历值为1，说明该数只出现了一次

ways2是通过全局进行异或运算，同0异1，精髓的思想在于两个相同的数进行异或运算后值为0(无论这两个数是直接异或还是间接异或，数组内所有数一起异或后剩下的数一定是只出现过一次的数，应为其他的数都两两抵消了)

#include<stdio.h>

int ways1(int* arr, int len) {

	int i = 0, j = 0, count;
	for (i = 0; i < len; i++) {
		count = 0;
		for (j = 0; j < len; j++) {
			if (arr[i] == arr[j])
				count++;
		}
		if (count == 1)
			return arr[i];
	}
	return -1;
}

int ways2(int* arr, int len) {
	int i, res = 0;
	for (i = 0; i < len; i++) {
		res ^= arr[i];				// ^异或运算，同 0 异 1
	}
	return res;
}

int main() {
	int arr[] = { 1,2,2,4,1,4,9,8,8 };
	int len = sizeof(arr) / sizeof(arr[0]);
	printf("result = %d\n", ways1(arr, len));
	printf("result = %d\n", ways2(arr, len));
	system("pause");
	return 0;
}

2. 判断一个数是否为快乐数

方法二，循环遍历后面所有数，直至遇到1或者4，遇到1则说明符合快乐数定义，4是后面循环遍历发现的规律，只要是不会遇到1的死循环，都会经过4，遇到4也会陷入不遇1的死循环，则说明不是快乐数

方法一，和思路一类似，只是巧妙的运用了“追赶思想”。

slow追上fast结束循环，此时有可能是后面陷入无限1循环，或者死循环撞上了
返回的是 判断 slow 是否为1 的bool值

#include <stdio.h>
#include <stdlib.h>

int bitSum(int n) {
    int sum = 0, j;
    while (n) {
        j = n % 10;
        sum += j * j;
        n /= 10;
    }
    return sum;
}

int isHappyWay1(int n) {
    int fast = n, slow = n;
    do {
        slow = bitSum(slow);
        fast = bitSum(bitSum(fast));
        printf("slow = %d, fast = %d\n",slow,fast);
    } while (slow != fast);
    return slow == 1;              
}

void isHappyWay2(int n){
    while (n != 1 && n != 4)   // 之前输出发现规律，死循环必定经过4
    {
        n = bitSum(n);
        int new_n = n;
        printf("%-4d", new_n);
    }
    if (n == 1) printf("\nYES");    // 遇到1为快乐数
    else printf("\n NO");
}

int main() {
    int n;
    scanf_s("%d", &n);

    // isHappyWay2(n);    

    if (isHappyWay1(n)) printf("YES");
    else printf("NO");
    system("pause");
    return 0;
}

3. 求一个数组内最大的一个片段的和

解析：见注解

#include<iostream>
#include<time.h>
using namespace std;
// 求一个数组内和最大的一个片段的和

int MaxSubArr_way1(int * arr, int size) {
	//printf("i\tj\tsum\tmax\n");
	
	int i, j, k, sum, max = arr[0];

	for (i = 0; i < size; i++) {
		for (j = i; j < size; j++) {
			sum = 0;
			for (k = i; k < j; k++) {
				sum += arr[k];
			}
			max = max > sum ? max : sum;
			//printf("%d\t%d\t%d\t%d\n", i, j, sum, max);
		}
	}
	return max;
}

int MaxSubArr_way2(int* arr, int size) {
	//printf("i\tj\tsum\tmax\n");
	int i, j, k, sum, max = arr[0];
	for (i = 0; i < size; i++) {
		sum = 0;
		for (j = i; j < size; j++) {
			sum += arr[j];	  // 范围扩大一位，但是和不需要再从头开始累加，只需要在上一次基础上再加上 arr[j]即可
			max = max > sum ? max : sum;
			//printf("%d\t%d\t%d\t%d\n", i, j, sum, max);
		}
	}
	return max;
}

int main() {
	int array1[] = { -2,1,-3,4,-1,2,1,-5,4 }, size1, size2, max1, max2;
	int array2[] = { -3, 5, -7, 2, -6, 9, -4, 1, 0, -2, 7, -5, 3, -8, 6, -1, 4, -3, 8, -6, 10, -7, 5, -4, 2, 9, -3, 0, -1, 7, -5, 4 };
	size1 = sizeof(array1) / sizeof(array1[0]);
	size2 = sizeof(array2) / sizeof(array2[0]);

	max2 = MaxSubArr_way2(array2, size2);

	clock_t startTime, endTime;
	float s_time;

	startTime = clock();	// ---
	for (int i = 0; i < 10000; i++) max1 = MaxSubArr_way1(array2, size2);
	endTime = clock();	// ---
	s_time = float(endTime - startTime) / CLOCKS_PER_SEC;
	printf("MaxSubArr_way1 耗时 %f \n", s_time);

	startTime = clock();	// ---
	for (int i = 0; i < 10000; i++) max1 = MaxSubArr_way2(array2, size2);
	endTime = clock();	// ---
	s_time = float(endTime - startTime) / CLOCKS_PER_SEC;
	printf("MaxSubArr_way2 耗时 %f \n", s_time);

	printf("MaxSum_by MaxSubArr_way1() = %d\n", max1);
	printf("MaxSum_by MaxSubArr_way2() = %d\n", max2);
	system("pause");
	return 0;
}

两方法运行时间对比：

4. 将某个数组的0元素都移到右边，非零都移到左边

交换法流程：

/*
      交换法，遍历数组，如果某个元素为0，右边为非零，则交换位置
      { 1,0,4,0,9,0 }  0 1 2 3 4 5  
      { 1,0,4,0,9,0 } -> { 1,4,0,0,9,0 } -> { 1,4,0,9,0,0 }
      { 1,4,0,9,0,0 } -> { 1,4,9,0,0,0 }
*/

交换法，遍历数组，如果某个元素为0，右边为非零，则交换位置

从交换规律上来看，有一点类似于冒泡排序，但是次数一定小于冒泡，
所以外层遍历arrSize次完全足够，当然也可以通过第三变量，通过第二层循环来判断是否迁移完成

#include<iostream>
using namespace std;

void arrPrint(int* arr, int arrSize) {
	for (int j = 0; j < arrSize; j++) {
		if (j == 0) printf("{ %d,", arr[0]);
		else if (j < arrSize - 1) printf("%d,", arr[j]);
		else printf("%d }\n", arr[arrSize - 1]);
	}
	return;
}

// 将某个数组的0元素都移到右边，非零都移到左边
void moveZero(int* arr, int arrSize) {
	for (int k = 0; k < arrSize; k++) {
		for (int i = 0; i + 1 < arrSize; i++) {
			if (arr[i] == 0 && arr[i + 1] != 0) {
				int t = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = t;
			}
		}
	}

	// 打印输出
	arrPrint(arr, arrSize);
	return;
}


int main() {
	int arr[] = { 1,0,4,0,9,0,88,23,99 };
	moveZero(arr, sizeof(arr) / sizeof(arr[0]));
	system("pause");
	return 0;
}

5. 给出一个股票价格数组，求出最大利润

注意: 股票可以多次买卖，但是只有卖了上次的才能进行下次购买
方法一，递归法，先假设最后一天卖不卖，如果不卖的话，相当于最后一天可有可无

1) 假设最后一天不卖

[7, 1, 5, 3, 6, 4] => maxProfit(prices, 5)    // 等价

2) 假设最后一天卖, 把所有最后一次买的情况都罗列出来，然后把此次和第一天的这个
范围递交出去重新考虑，最后归值都加到prifit上，最后判断那次利润最大，返回最大利润

[7, 1, 5, 3, 6] + (6, 4) => maxProfit(prices, 5) + (prices[5] - prices[4])
[7, 1, 5, 3] + (3, 4)    => maxProfit(prices, 4) + (prices[5] - prices[3])
[7, 1, 5] + (5, 4)       => maxProfit(prices, 3) + (prices[5] - prices[2])
[7, 1] + (1, 4)          => maxProfit(prices, 2) + (prices[5] - prices[1])
[7] + (7, 4)             => maxProfit(prices, 1) + (prices[5] - prices[0])

当价格数组长度为1的时候，max = 0
(利润最差为0，即使股票价格数组是递减，也可以通过不卖来避免负利润)


方法二，有点复杂，等有空再写解析

方法三，只比较相邻的两天，如果i天比i+1天的便宜，那就买，并计算利润差加到总和
[7, 1, 5, 3, 6, 4]
^ ^
为什么可以这样? (贪心)

代码：

#include<stdio.h>
#include<stdlib.h>
// 给出一个股票价格数组 [7, 1, 5, 3, 6, 4], 求出最大利润
// 注意: 股票可以多次买卖，但是只有卖了上次的才能进行下次购买
int maxProfit(int* prices, int pricesSize) {
	if (pricesSize <= 1) return 0;

	int profit;
	int max = 0;
	// 1) 
	profit = maxProfit(prices, pricesSize - 1);
	if (profit > max) max = profit;
	// 2)
	for (int i = 1; i <= pricesSize - 1; i++) {
		profit = maxProfit(prices, i) + prices[pricesSize - 1] - prices[i - 1];
		if (profit > max) max = profit;
	}
	return max;
}

int maxProfitWay2(int* prices, int pricesSize) {
	if (pricesSize <= 1) return 0;

	int* profits = (int*)malloc((pricesSize + 1) * sizeof(int));
	// 通过动态内存分配来实现变量定义数组长度
	if (profits == NULL) {
		fprintf(stderr, "Memory allocation filed\n");
		return -1;
	}
	profits[1] = 0;

	for (int k = 2; k <= pricesSize; k++) {
		int profit;
		int max = 0;
		profit = profits[k - 1];
		if (profit > max) max = profit;

		for (int i = 1; i <= k - 1; i++) {
			profit = profits[i] + prices[k - 1] - prices[i - 1];
			if (profit > max) max = profit;
		}
		profits[k] = max;
	}
	int result = profits[pricesSize];
	free(profits);
	return result;
}

int maxProfitWay3(int* prices, int pricesSize) {
	int sum = 0;
	for (int i = 0; i + 1 < pricesSize; i++) {
		if (prices[i] < prices[i + 1]) 
			sum += prices[i + 1] - prices[i];
	}
	return sum;
}

int main() {
	int prices[] = { 7, 1, 5, 3, 6, 4 };
	int sz = sizeof(prices) / sizeof(prices[0]);
	printf("最大利润为(maxProfit): %d\n", maxProfit(prices, sz));
	printf("最大利润为(maxProfitWay2): %d\n", maxProfitWay2(prices, sz));
	printf("最大利润为(maxProfitWay3): %d\n", maxProfitWay3(prices, sz));
	system("pause");
	return 0;
}

6. 给定一组字符串，将相同字母的异序词组合在一起

给定一组字符串，将相同字母的异序词组合在一起

Example
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
	["ate", "eat", "tea"],
	["nat", "tan"],
	["bat"]
]

代码如下

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#pragma warning(disable : 4996)

int cmpChar(const void* a, const void* b) {
	return *(const char*)a - *(const char*)b;
}

typedef struct {
	char* original;
	char* sorted;
} Pair;

int comPair(const void* a, const void* b) {
	const Pair* pa = (const Pair*)a;
	const Pair* pb = (const Pair*)b;

	return strcmp(pa->sorted, pb->sorted);
}

char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
	// strs: ["eat", "tea", "tan", "ate", "nat", "bat"], strsSize: 6
	Pair* pairs = malloc(sizeof(Pair) * strsSize);
	for (int i = 0; i < strsSize; i++) {

		char* sorted_str = malloc(sizeof(char) * (strlen(strs[i]) + 1));
		strcpy(sorted_str, strs[i]);
		qsort(sorted_str, strlen(strs[i]), sizeof(char), cmpChar);

		pairs[i].original = strs[i];
		pairs[i].sorted = sorted_str;
		
	}
	qsort(pairs, strsSize, sizeof(Pair), comPair);

	char*** returnResult = NULL;
	*returnSize = 0;
	*returnColumnSizes = NULL;

	for (int i = 0; i < strsSize; i++) {
		if (i == 0 || strcmp(pairs[i].sorted, pairs[i - 1].sorted) != 0) {
			int lastGroupIndex = *returnSize;
			returnResult = realloc(returnResult, sizeof(char**) * (*returnSize + 1));
			returnResult[lastGroupIndex] = malloc(sizeof(char*) * 1);
			returnResult[lastGroupIndex][0] = pairs[i].original;

			(*returnSize)++;
			*returnColumnSizes = realloc(*returnColumnSizes, sizeof(int) * (*returnSize));
			(*returnColumnSizes)[lastGroupIndex] = 1;
		}
		else {
			int lastGroupIndex = *returnSize - 1;
			int lastGroupSize = (*returnColumnSizes)[lastGroupIndex];
			returnResult[lastGroupIndex] 
				= realloc(returnResult[lastGroupIndex], sizeof(char*)* (lastGroupSize + 1));
			returnResult[lastGroupIndex][lastGroupSize] = pairs[i].original;
			(*returnColumnSizes)[lastGroupIndex] = lastGroupSize + 1;
		}
	}

	return returnResult;
}

int main() {
	char* input[] = { "eat", "tea", "tan", "ate", "nat", "bat","wxy","xyw"};
	int strsSize = sizeof(input) / sizeof(input[0]);
	int returnSize;
	int* returnColumnSizes;

	char*** result = groupAnagrams(input, strsSize, &returnSize, &returnColumnSizes);

	printf("[\n");
	for (int i = 0; i < returnSize; i++) {
		printf("  [");
		for (int j = 0; j < returnColumnSizes[i]; j++) {
			printf("\"%s\"", result[i][j]);
			if (j < returnColumnSizes[i] - 1) {
				printf(", ");
			}
		}
		printf("]\n");
	}
	printf("]\n");

	// Free allocated memory for result and returnColumnSizes
	for (int i = 0; i < returnSize; i++) {
		free(result[i]);
	}
	free(result);
	free(returnColumnSizes);

	system("pause");
	return 0;
}

输出测试：

7. 数组内的数，值+1 后在原数组内是否还存在，记录存在的数的个数

示例与分析

    Example 1
    Input: arr =[1, 1, 3, 3, 5, 5, 7, 7]
    Output: 0
    Explanation: No numbers are counted, cause there's no 2,4,6,or 8 in arr

    Example 2
    Input: arr = [1, 3, 2, 3, 5, 0]
    Output: 3
    Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr

    way1: 正常的思维就是两层for循环遍历的做法，这里就不使用这种方法了
    
    way2: 用表来记录, 例如 hashList[1002] = 0; 遍历赋值hashList[arr[i]] = 1
    if(hashList[arr[i]+1]) == 1; count++;

    ways3: 通过排序来做，排序后，如果 arr[i] != arr[i+1] 且 arr[i+1] - arr[i] == 1,     
    则将前面相同数的个数加到count里面，前面相同的数用numbers统计，numbers在遇到不同数时重置为1

代码：

#include<bits/stdc++.h>
using namespace std;

int cmp(const void* a, const void* b) {
    return *(const int*)a - *(const int*)b;
}
int main() {
    int arr[] = { 1,1,2,2,5,5,7,7 };
    //int arr[] = { 6,9,3,6,11,8,34,2 };
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, arrSize, sizeof(int), cmp);

    //for (int i = 0; i < arrSize; i++) {
    //    printf("%d ",arr[i]);
    //}

    int count = 0;
    int number = 1;
    for (int i = 1; i < arrSize; i++) {
        if (arr[i] != arr[i - 1]) {
            if (arr[i] == arr[i - 1] + 1) {
                count += number;
            }
            number = 1;
        }
        else {
            number++;
        }
    }
    cout << count << endl;
    system("pause");
    return 0;
}