1. 翻转数组
翻转数组，就是要把数组中元素的顺序全部反过来。比如一个数组{1,2,3,4,5,6,7,8}，翻转之后就是{8,7,6,5,4,3,2,1}。
（1）另外创建数组，反向填入元素
数组是将元素按照顺序依次存放的，长度固定。所以如果想要让数组“翻转”，一种简单的思路是：直接创建一个相同长度的新数组，然后遍历所有元素，从末尾开始依次反向填入就可以了。
#include<iostream>
using namespace std;
int main()
{
const int n = 8;
int arr[n] = { 1,2,3,4,5,6,7,8 };
// 1. 直接创建一个新数组，遍历元素反向填入
int newArr[n];
for (int i = 0; i < n; i++)
{
newArr[n-i-1] = arr[i];
}
// 打印数组
for (int i = 0; i < n; i++)
{
cout << newArr[i] << "\t";
}
cout << endl;
cin.get();
}
需要注意原数组下标为i的元素，对应翻转后的新数组下标为n-i-1（n为数组长度）。
（2）基于原数组翻转
另建数组的方式很容易实现，但有明显的缺点：需要额外创建一个数组，占用更多的内存。最好的方式是，不要另开空间，就在原数组上调整位置。
这种思路的核心在于：我们应该有两个类似“指针”的东西，每次找到头尾两个元素，将它们调换位置；而后指针分别向中间逼近，再找两个元素对调。由于数组中下标是确定的，因此可以直接用下标代替“指针”。
// 2. 双指针分别指向数组头尾，元素对调
int head = 0, tail = n - 1;
while(head < tail)
{
int temp = arr[head];
arr[head] = arr[tail];
arr[tail] = temp;
// 指针向中间移动
++head;
--tail;
}
// 打印数组
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
2. 检验幻方
“幻方”是数学上一个有趣的问题，它让一组不同的数字构成一个方阵，并且每行、每列、每个对角线的所有数之和相等。比如最简单的三阶幻方，就是把1~9的数字填到九宫格里，要求横看、竖看、斜着看和都是15。
口诀：二四为肩，六八为足，左三右七，戴九履一，五居中央。
我们可以给定一个n×n的矩阵，也就是二维数组，然后判断它是否是一个幻方：
#include<iostream>
using namespace std;
int main()
{
const int n = 3;
int arr[n][n] = {
{4, 9, 2},
{3, 5, 7},
{8, 1, 6}
};
// 目标和
int target = (1 + n * n) * n / 2;
bool isMagic = true;
// 检验每一行
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = 0; j < n; j++)
{
sum += arr[i][j];
}
// 如果和不是target，说明不是幻方
if (sum != target)
{
isMagic = false;
break;
}
}
// 检验每一列
for (int j = 0; j < n; j++)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i][j];
}
if (sum != target)
{
isMagic = false;
break;
}
}
// 检验两个对角线
int sumDiag1 = 0;
int sumDiag2 = 0;
for (int i = 0; i < n; i++)
{
sumDiag1 += arr[i][i];
sumDiag2 += arr[i][n-i-1];
}
if (sumDiag1 != target || sumDiag2 != target)
{
isMagic = false;
}
// 判断结果
cout << "给定的矩阵arr" << (isMagic ? "是" : "不是") << n << "阶幻方！" << endl;
cin.get();
}
3. 大整数相加
实际应用中，有时会遇到非常大的整数，可能会超过long、甚至long long的范围。这时就需要用不限长度的字符串保存数据，然后进行计算。
最简单的需求就是“大整数相加”，即给定两个字符串形式的非负大整数 num1 和num2 ，计算它们的和。
我们可以把字符串按每个字符一一拆开，相当于遍历整数上的每一个数位，然后通过“乘10叠加”的方式，就可以整合起来了。这相当于算术中的“竖式加法”。
#include<iostream>
using namespace std;
int main()
{
string num1 = "32535943020935527435432875";
string num2 = "9323298429842985843509";
// 用一个空字符串保存结果
string result;
// 获取两数个位的索引
int p1 = num1.size() - 1;
int p2 = num2.size() - 1;
// 设置一个进位标志
int carry = 0;
while (p1 >= 0 || p2 >= 0 || carry > 0)
{
int x = (p1 >= 0) ? (num1[p1] - '0') : 0;
int y = (p2 >= 0) ? (num2[p2] - '0') : 0;
int sum = x + y + carry;
result += (sum % 10 + '0'); // 和的个位写入结果
carry = sum / 10; // 和的十位保存在进位上
// 继续遍历下一位
--p1;
--p2;
}
// 结果需要做翻转
int i = 0, j = result.size() - 1;
while (i < j)
{
char temp = result[j];
result[j] = result[i];
result[i] = temp;
++i;
--j;
}
cout << num1 << " + " << num2 << endl << endl;
cout << " = " << result;
cin.get();
}
4. 旋转图像
旋转图像的需求，在图片处理的过程中非常常见。我们知道对于计算机而言，图像其实就是一组像素点的集合，所以图像旋转的问题，本质上就是一个二维数组的旋转问题。
我们可以给定一个二维数组，用来表示一个图像，然后将它顺时针旋转90°。例如，对于4×4的矩阵：
{
{ 5, 1, 9, 11},
{ 2, 4, 8, 10},
{ 13, 3, 6, 7},
{ 15, 14, 12, 16}
}
旋转之后变为：
{
{ 15, 13, 2, 5},
{ 14, 3, 4, 1},
{ 12, 6, 8, 9},
{ 16, 7, 10, 11}
]
根据数学上矩阵的特性，可以把矩阵A先做转置得到AT，然后再翻转每一行就可以了。
#include<iostream>
using namespace std;
int main()
{
const int n = 4;
int image[n][n] = {
{ 5, 1, 9, 11},
{ 2, 4, 8, 10},
{ 13, 3, 6, 7},
{ 15, 14, 12, 16}
};
// 矩阵转置
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
// 以对角线为对称轴，两边互换
int temp = image[i][j];
image[i][j] = image[j][i];
image[j][i] = temp;
}
}
// 每一行翻转
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n / 2; j++)
{
int temp = image[i][j];
image[i][j] = image[i][n-j-1];
image[i][n - j - 1] = temp;
}
}
// 打印输出
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << image[i][j] << "\t";
}
cout << endl;
}
cin.get();
}
5. 翻转链表
链表（Linked List）是一种常见的基础数据结构，它是一种线性表，但是并不会像数组那样按顺序存储数据，而是在每一个节点里存指向下一个节点的指针。
对于数组，可以通过下标访问每个元素；如果想要翻转一个数组，只要不停地把头尾元素互换就可以了。
而链表并没有“下标”，所以想要访问元素只能依次遍历；如果要翻转一个链表，关键就在于“next”指针需要反向。
我们可以先定义一个结构体类型ListNode，用来表示链表中的每个节点：
#pragma once
struct ListNode
{
int value;
ListNode* next;
};
自定义一个头文件list_node.h，将结构体TreeNode的定义放在里面，这样之后如果需要使用它，就可以直接引入：
#include "list_node.h"
这里的#prama once是一条预处理指令，表示头文件的内容只被解析一次，不会重复处理。
接下来就可以实现翻转链表的过程了。
#include<iostream>
#include "list_node.h"
using namespace std;
int main()
{
// 定义一个链表 1->2->3->4->5->NULL
ListNode node5 = { 5, nullptr };
ListNode node4 = { 4, &node5 };
ListNode node3 = { 3, &node4 };
ListNode node2 = { 2, &node3 };
ListNode node1 = { 1, &node2 };
ListNode* list = &node1;
ListNode* curr = list;
ListNode* prev = nullptr;
// 翻转链表
while (curr)
{
ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
ListNode* newList = prev;
// 打印链表
ListNode* np = newList;
while (np)
{
cout << np->value << "\t->\t";
np = np->next;
}
cout << "null" << endl;
cin.get();
}
这里对指向结构体对象的curr指针，需要先解引用，然后取它所指向ListNode对象里的next指针。这个过程本应该写作：
(*curr).next;
这个写法比较麻烦，所以一般会用另一种简化写法：
curr->next;
这两个写法完全等价。这里的“->”叫做“箭头运算符”，它是解引用和访问成员两个操作的结合；这样就可以很方便地表示“取指针所指向内容的成员”。