1. 找出数组中重复的数字
题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
- 排序后遍历
- 利用hash表，遍历数组，判断当前数字是否是在hash表中，没有，加入。有，则是重复数字。
- n长的数组，数字范围0-n-1，则排好序的话，i位置上存放i值才是没有重复的。遍历数组，扫描到i位置，如果arr[i]==i,则扫描下一个位置，否则和第m=arr[i]的位置比较，如果相等，找到重复。如果不相等，交换两者。
bool duplicate(int numbers[], int length, int* duplication)
{
if(numbers == nullptr || length <= 0)
return false;
for(int i = 0; i < length; ++i)
{
if(numbers[i] < 0 || numbers[i] > length - 1)
return false;
}
for(int i = 0; i < length; ++i)
{
while(numbers[i] != i)
{
if(numbers[i] == numbers[numbers[i]])
{
*duplication = numbers[i];
return true;
}
// 交换numbers[i]和numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
2. 不修改数组找出重复的数字
题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。不能修改数组
数字范围是0-n-1，我们试着不在原数组里找重复元素，而是思考0-n-1内到底哪个重复了。二分0-n-1；0-m，m-n-1；如果前者在原数组中出现次数超过了m，则0-m内一定有重复出现的。之后在0-m内再二分。二分的思想。
int getDuplication(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;
int start = 1;
int end = length - 1;
while(end >= start)
{
int middle = ((end - start) >> 1) + start;
int count = countRange(numbers, length, start, middle);
if(end == start)
{
if(count > 1)
return start;
else
break;
}
if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}
int countRange(const int* numbers, int length, int start, int end)
{
if(numbers == nullptr)
return 0;
int count = 0;
for(int i = 0; i < length; i++)
if(numbers[i] >= start && numbers[i] <= end)
++count;
return count;
}
3. 有序二维数组中找是否存在某个整数
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
从右上角那个数字开始，如果是，返回true。如果大于，则这一列不考虑，向左移动。如果小于，则整行不考虑，向下移动。
bool Find(int* matrix, int rows, int columns, int number)
{
bool found = false;
if(matrix != nullptr && rows > 0 && columns > 0)
{
int row = 0;
int column = columns - 1;
while(row < rows && column >=0)
{
if(matrix[row * columns + column] == number)
{
found = true;
break;
}
else if(matrix[row * columns + column] > number)
-- column;
else
++ row;
}
}
return found;
}
4 替换空格
题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。
从开头遍历的话，会重复移动字符。首先遍历字符串，找到一共有几个空格，则新的字符大小就是n+2*m, 从末尾开始遍历数组。两个指针，i指向原始数组末尾，j指向新字符串末尾（已知大小）。i，j同时向前移动，j复制i，直到遇到空格，i向前，j插入%20。如果i和j指向同一个位置，则所有空格填充完毕。
void ReplaceBlank(char str[], int length)
{
if(str == nullptr && length <= 0)
return;
/*originalLength 为字符串str的实际长度*/
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while(str[i] != '\0')
{
++ originalLength;
if(str[i] == ' ')
++ numberOfBlank;
++ i;
}
/*newLength 为把空格替换成'%20'之后的长度*/
int newLength = originalLength + numberOfBlank * 2;
if(newLength > length)
return;
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
{
if(str[indexOfOriginal] == ' ')
{
str[indexOfNew --] = '0';
str[indexOfNew --] = '2';
str[indexOfNew --] = '%';
}
else
{
str[indexOfNew --] = str[indexOfOriginal];
}
-- indexOfOriginal;
}
}
5. 从尾到头打印链表
题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
很自然可以想到使用栈，从头开始遍历，遍历到一个节点，先不要输出，先把value压栈。最后遍历完，依次出栈。
可以使用栈的方法都可以使用递归，当我们遍历到一个节点时，先递归输出它前面的节点，再输出自己的节点
void PrintListReversingly_Iteratively(ListNode* pHead)
{
std::stack<ListNode*> nodes;
ListNode* pNode = pHead;
while(pNode != nullptr)
{
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while(!nodes.empty())
{
pNode = nodes.top();
printf("%d\t", pNode->m_nValue);
nodes.pop();
}
}
void PrintListReversingly_Recursively(ListNode* pHead)
{
if(pHead != nullptr)
{
if (pHead->m_pNext != nullptr)
{
PrintListReversingly_Recursively(pHead->m_pNext);
}
printf("%d\t", pHead->m_nValue);
}
}
6.先序中序重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，
先序遍历第一个值就是根节点，根据这个值可以在中序中划分左右子树，我们这里已经将一个数划分成两颗子树，那么在递归的使用刚刚的分析可以继续分开，直到叶子节点。
BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);
BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
{
if(preorder == nullptr || inorder == nullptr || length <= 0)
return nullptr;
return ConstructCore(preorder, preorder + length - 1,
inorder, inorder + length - 1);
}
BinaryTreeNode* ConstructCore
(
int* startPreorder, int* endPreorder,
int* startInorder, int* endInorder
)
{
// 前序遍历序列的第一个数字是根结点的值
int rootValue = startPreorder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = nullptr;
if(startPreorder == endPreorder)
{
if(startInorder == endInorder && *startPreorder == *startInorder)
return root;
else
throw std::exception("Invalid input.");
}
// 在中序遍历中找到根结点的值
int* rootInorder = startInorder;
while(rootInorder <= endInorder && *rootInorder != rootValue)
++ rootInorder;
if(rootInorder == endInorder && *rootInorder != rootValue)
throw std::exception("Invalid input.");
int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPreorder + leftLength;
if(leftLength > 0)
{
// 构建左子树
root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd,
startInorder, rootInorder - 1);
}
if(leftLength < endPreorder - startPreorder)
{
// 构建右子树
root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,
rootInorder + 1, endInorder);
}
return root;
}
7.二叉树的下一个结点
给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
分三种情况
如果当前节点有右子树，则下一个节点是右子树的最左边的节点。
如果当前节点没有右子树，并且它是它父节点的左孩子，那么下一个节点就是它的父节点。
如果当前节点没有右子树，并且它是它父节点的右孩子，那么一直向上找父节点，直到找到一个节点是其父节点的左孩子，则这个父节点就是下一个孩子。
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
BinaryTreeNode* m_pParent;
};
BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
if(pNode == nullptr)
return nullptr;
BinaryTreeNode* pNext = nullptr;
if(pNode->m_pRight != nullptr)
{
BinaryTreeNode* pRight = pNode->m_pRight;
while(pRight->m_pLeft != nullptr)
pRight = pRight->m_pLeft;
pNext = pRight;
}
else if(pNode->m_pParent != nullptr)
{
BinaryTreeNode* pCurrent = pNode;
BinaryTreeNode* pParent = pNode->m_pParent;
while(pParent != nullptr && pCurrent == pParent->m_pRight)
{
pCurrent = pParent;
pParent = pParent->m_pParent;
}
pNext = pParent;
}
return pNext;
}
8.用栈实现队列。
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
使用两个栈，一个push栈，和一个pop栈。用于实现队列的push和pop操作，队列push时，只要将数据压入push栈，pop时，把push栈里的东西一次压入pop再弹出。但是要注意两个注意点，如果push栈里有东西，一定不能从pop栈理出，要先到push栈。同时，push栈必须一次全部倒完。
template<typename T> void CQueue<T>::appendTail(const T& element)
{
stack1.push(element);
}
template<typename T> T CQueue<T>::deleteHead()
{
if(stack2.size()<= 0)
{
while(stack1.size()>0)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size() == 0)
throw new exception("queue is empty");
T head = stack2.top();
stack2.pop();
return head;
}
9.斐波那契数列
题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。
递归的方法很好写，但是递归的方法效率极低，会有很多重复计算，尤其是n很大的时候。
使用迭代的方法，记录前面计算的值。
通项
long long Fibonacci_Solution1(unsigned int n)
{
if(n <= 0)
return 0;
if(n == 1)
return 1;
return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}
long long Fibonacci_Solution2(unsigned n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
long long fibNMinusOne = 1;
long long fibNMinusTwo = 0;
long long fibN = 0;
for(unsigned int i = 2; i <= n; ++ i)
{
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
10.在旋转数组中查找某个数字
谈到查找，立刻想到顺序查找，二分查找，hash查找，搜索二叉树。顺序查找O(N),二分查找O(logN)，hash O(1)但是以空间为代价。
这题可以使用二分法，先将数组二分，那么两边必定有一边是顺序的，那么在顺序一边查找，如果找到，则返回。如果找不到，则在另一边继续二分。
class Solution {
public:
int search(vector<int>& nums, int target) {
// 线性表搜索问题一般都会用到二分法
// 二分法涉及三个指针min max mid
int min = 0, max = nums.size()-1, mid = 0;
// 二分法最终的停止条件
while(min <= max){
// 初始第一次二分的mid
int mid = (min+max)/2;
// 如果mid恰好是target(最终target都会到mid这里)
if(nums[mid] == target) return mid;
// 如果左半部分有序,则在此半部分（有序字符串）进行二分查找
if(nums[min] <= nums[mid]){
if(nums[min]<=target && target<nums[mid])
max = mid - 1;
else
min = mid + 1;
}
// 如果右半部分有序
else{
if(nums[mid]< target && target<=nums[max])
min = mid + 1;
else
max = mid - 1;
}
}
// 不满足最高二分条件min<=max时
return -1;
}
};
11.矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
回溯加递归：初始index为0，然后随机选取矩阵上一点，判断该点是否是str(index),是的话，index+1.判断其它四个方向的点是否是str(index+1),只要有一个是，则继续。如果不是，则返回上一个点。注意需要一个和矩阵大小一样的表来帮助记录哪些点已经访问过。
#include <cstdio>
#include <string>
#include <stack>
using namespace std;
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited);
bool hasPath(const char* matrix, int rows, int cols, const char* str)
{
if(matrix == nullptr || rows < 1 || cols < 1 || str == nullptr)
return false;
bool *visited = new bool[rows * cols];
memset(visited, 0, rows * cols);
int pathLength = 0;
for(int row = 0; row < rows; ++row)
{
for(int col = 0; col < cols; ++col)
{
if(hasPathCore(matrix, rows, cols, row, col, str,
pathLength, visited))
{
return true;
}
}
}
delete[] visited;
return false;
}
bool hasPathCore(const char* matrix, int rows, int cols, int row,
int col, const char* str, int& pathLength, bool* visited)
{
if(str[pathLength] == '\0')
return true;
bool hasPath = false;
if(row >= 0 && row < rows && col >= 0 && col < cols
&& matrix[row * cols + col] == str[pathLength]
&& !visited[row * cols + col])
{
++pathLength;
visited[row * cols + col] = true;
hasPath = hasPathCore(matrix, rows, cols, row, col - 1,
str, pathLength, visited)
|| hasPathCore(matrix, rows, cols, row - 1, col,
str, pathLength, visited)
|| hasPathCore(matrix, rows, cols, row, col + 1,
str, pathLength, visited)
|| hasPathCore(matrix, rows, cols, row + 1, col,
str, pathLength, visited);
if(!hasPath)
{
--pathLength;
visited[row * cols + col] = false;
}
}
return hasPath;
}
12.机器人的运动范围
地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动，它每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格(35, 37)，因为3+5+3+7=18。
但它不能进入方格(35, 38)，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
一般在矩阵中走路的题目都是i回溯法+递归。判断最大行走路径，先判断一个点是否是可以行走的，是的，则路径=1+其它四个路径的点最大路径的和。注意也要用一个数组记录每一个点是否已经访问过。
// 很有意思
#include <cstdio>
int movingCountCore(int threshold, int rows, int cols, int row, int col, bool* visited);
bool check(int threshold, int rows, int cols, int row, int col, bool* visited);
int getDigitSum(int number);
// 主函数
int movingCount(int threshold, int rows, int cols)
{
if(threshold < 0 || rows <= 0 || cols <= 0)
return 0;
bool *visited = new bool[rows * cols];
for(int i = 0; i < rows * cols; ++i)
visited[i] = false;
int count = movingCountCore(threshold, rows, cols,
0, 0, visited);
delete[] visited;
return count;
}
// 计算矩阵最长行走路径
int movingCountCore(int threshold, int rows, int cols, int row,
int col, bool* visited)
{
int count = 0;
if(check(threshold, rows, cols, row, col, visited))
{
visited[row * cols + col] = true;
count = 1 + movingCountCore(threshold, rows, cols,
row - 1, col, visited)
+ movingCountCore(threshold, rows, cols,
row, col - 1, visited)
+ movingCountCore(threshold, rows, cols,
row + 1, col, visited)
+ movingCountCore(threshold, rows, cols,
row, col + 1, visited);
}
return count;
}
// 检查当前点是否可以进入
bool check(int threshold, int rows, int cols, int row, int col,
bool* visited)
{
if(row >= 0 && row < rows && col >= 0 && col < cols
&& getDigitSum(row) + getDigitSum(col) <= threshold
&& !visited[row* cols + col])
return true;
return false;
}
// 检查当前点数为之和
int getDigitSum(int number)
{
int sum = 0;
while(number > 0)
{
sum += number % 10;
number /= 10;
}
return sum;
}
13.剪绳子
题目：给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…*k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
动态规划的思想，长度为n的剪为两半最大乘积，可以分解为两半各自剪断的最大值。所以可以不断分解成子问题，直到最小的子问题。但是从上到下的方式会计算重复子问题。所以可以从自问题出发，计算最小子问题解，次最下，。。。后面的子问题都是依赖前面的。所以可以不断根据前面计算的子问题解计算后面的问题。这些从第向上的子问题的解都存放在一个数组里。
贪婪的思想，当n>5时，尽可能剪断3，n=4时，剪2.贪婪的算法都是可以用数学求解的。
#include <iostream>
#include <cmath>
// ====================动态规划====================
int maxProductAfterCutting_solution1(int length)
{
if(length < 2)
return 0;
if(length == 2)
return 1;
if(length == 3)
return 2;
int* products = new int[length + 1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
for(int i = 4; i <= length; ++i)
{
max = 0;
for(int j = 1; j <= i / 2; ++j)
{
int product = products[j] * products[i - j];
if(max < product)
max = product;
products[i] = max;
}
}
max = products[length];
delete[] products;
return max;
}
// ====================贪婪算法====================
int maxProductAfterCutting_solution2(int length)
{
if(length < 2)
return 0;
if(length == 2)
return 1;
if(length == 3)
return 2;
// 尽可能多地减去长度为3的绳子段
int timesOf3 = length / 3;
// 当绳子最后剩下的长度为4的时候，不能再剪去长度为3的绳子段。
// 此时更好的方法是把绳子剪成长度为2的两段，因为2*2 > 3*1。
if(length - timesOf3 * 3 == 1)
timesOf3 -= 1;
int timesOf2 = (length - timesOf3 * 3) / 2;
return (int) (pow(3, timesOf3)) * (int) (pow(2, timesOf2));
}
14.二进制中1的个数
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。
这题可以理解为二进制的位运算，求一个数中1的个数，可以将这个数与1与，如果是1，则末尾为1，num++，然后1左移一位，再和这个数与，判断第二位是否为1.
注意是1左移，而不是数右移，是因为右移需要考虑有符号数的情况。
上面的解法需要遍历每一个位置，有一个方法可以有几个1就进行几次。基于这样的想法：把一个整数减去1，再和原来的整数与，就可以把最右边的1变成0。
上面的想法还可以用于这样的题目：判断一个数是不是2的整数次方，因为满足的情况，所有为只有一位是1，其它都是0.那么经过上面的一次计算即可。
#include <cstdio>
int NumberOf1_Solution1(int n)
{
int count = 0;
unsigned int flag = 1;
while (flag)
{
if (n & flag)
count++;
flag = flag << 1;
}
return count;
}
int NumberOf1_Solution2(int n)
{
int count = 0;
while (n)
{
++count;
n = (n - 1) & n;
}
return count;
}
15.数值的k次方
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
需要思考：指数如果是负数，指数如果是负数，可以先对指数取绝对值，算出k次方，再取倒数。取到数时也要注意，底数为0时的情况。
递归的思想，n求k次方，如果k是偶数，则求n的k/2次方再平方即可。如果k是奇数，求n的k-1/2的平方再乘n即可。这类似与费波纳且
#include <iostream>
#include <cmath>
bool g_InvalidInput = false;
bool equal(double num1, double num2);
double PowerWithUnsignedExponent(double base, unsigned int exponent);
double Power(double base, int exponent)
{
g_InvalidInput = false;
if (equal(base, 0.0) && exponent < 0)
{
g_InvalidInput = true;
return 0.0;
}
unsigned int absExponent = (unsigned int) (exponent);
if (exponent < 0)
absExponent = (unsigned int) (-exponent);
double result = PowerWithUnsignedExponent(base, absExponent);
if (exponent < 0)
result = 1.0 / result;
return result;
}
double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
// 使用右移代替除2
double result = PowerWithUnsignedExponent(base, exponent >> 1);
result *= result;
// 使用与运算判断奇偶
if ((exponent & 0x1) == 1)
result *= base;
return result;
}
// 判断两个小数是否相等不能使用==
bool equal(double num1, double num2)
{
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
return true;
else
return false;
}
16.打印1到最大的n位数
题目：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。
如果用int或long存储数字，那么n稍微大一点就会越界。对于大数问题，我们使用字符串表示数字。对于一个n位的整数，我们可以有n+1位的字符串表示。同时，n位的所有十进制数其实就是n个从0到9的全排列。
全排列可以使用递归，数字的每一位都可能是0-9的一个数，然后设置下一个数，递归结束的条件就是我们设置了而最后一位数字。
void Print1ToMaxOfNDigits_2(int n)
{
if (n <= 0)
return;
char* number = new char[n + 1];
number[n] = '\0';
for (int i = 0; i < 10; ++i)
{
number[0] = i + '0';
Print1ToMaxOfNDigitsRecursively(number, n, 0);
}
delete[] number;
}
void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index)
{
if (index == length - 1)
{
PrintNumber(number);
return;
}
for (int i = 0; i < 10; ++i)
{
number[index + 1] = i + '0';
Print1ToMaxOfNDigitsRecursively(number, length, index + 1);
}
}
void PrintNumber(char* number)
{
bool isBeginning0 = true;
int nLength = strlen(number);
for (int i = 0; i < nLength; ++i)
{
if (isBeginning0 && number[i] != '0')
isBeginning0 = false;
if (!isBeginning0)
{
printf("%c", number[i]);
}
}
printf("\t");
}
17 在O(1)时间删除链表结点
题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
一般得删除方法，需要首先遍历到需要删除的节点，这样的操作就是O（n），其实我们可以直接获得删除节点下一个得位置，再把下一个位置复制给删除节点，再删除刚刚得下一个位置，就是O(1)得时间。
#include <cstdio>
#include "..\Utilities\xsList.h"
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
if(!pListHead || !pToBeDeleted)
return;
// 要删除的结点不是尾结点
if(pToBeDeleted->m_pNext != nullptr)
{
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext;
delete pNext;
pNext = nullptr;
}
// 链表只有一个结点，删除头结点（也是尾结点）
else if(*pListHead == pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted = nullptr;
*pListHead = nullptr;
}
// 链表中有多个结点，删除尾结点
else
{
ListNode* pNode = *pListHead;
while(pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
}
pNode->m_pNext = nullptr;
delete pToBeDeleted;
pToBeDeleted = nullptr;
}
}
18. 调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
其实我们只要使得所有偶数都在奇数得后面即可
思路一：我们遍历数组，每当遇到一个偶数就把该偶数放到数组后面，具体做法，每当遇到一个偶数，将该偶数后面得数字往前移动一格，再把该偶数放到末尾。
思路二：上面的方法每遇到一个偶数就要移动一次，需要O(N2).现在我们设立两个指针i j，分别指向数组得头和尾，如果前面得指针指向偶数，后面得指向奇数，则交换他们。
#include <cstdio>
void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);
// ====================方法一====================
void ReorderOddEven_1(int *pData, unsigned int length)
{
if(pData == nullptr || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;
while(pBegin < pEnd)
{
// 向后移动pBegin，直到它指向偶数
while(pBegin < pEnd && (*pBegin & 0x1) != 0)
pBegin ++;
// 向前移动pEnd，直到它指向奇数
while(pBegin < pEnd && (*pEnd & 0x1) == 0)
pEnd --;
if(pBegin < pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
// ====================方法二====================
void ReorderOddEven_2(int *pData, unsigned int length)
{
Reorder(pData, length, isEven);
}
void Reorder(int *pData, unsigned int length, bool (*func)(int))
{
if(pData == nullptr || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;
while(pBegin < pEnd)
{
// 向后移动pBegin
while(pBegin < pEnd && !func(*pBegin))
pBegin ++;
// 向前移动pEnd
while(pBegin < pEnd && func(*pEnd))
pEnd --;
if(pBegin < pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
bool isEven(int n)
{
return (n & 1) == 0;
}
22.链表中倒数第k个结点
题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。
由于是单链表，直接找到倒数k个节点是不能的。可是我们可以把找倒数k个，可以想成找正数第n-k+1个，这样只要我们确定了链表长度n即可。但是这种方法需要遍历链表两次（确定链表长度一次）。
只需遍历链表一次的方法：两个指针，初始时两个都在开头，之后一个不动，一个向前走k-1步。然后两者一起动。当在前面的指针先到尾部时，第一个指针就在链表倒数k个位置。 但要注意：链表位空，k=0的情况
这种两个确定距离指针移动来确定链表某个位置的方法很常见。（确定距离快慢指针）
还有一种方法，两个指针初始都在开头，快指针一次走两个，慢指针一次走一个。当快指针到末尾时，慢指针恰好可以到链表中间。（不同速度的快慢指针）
#include <cstdio>
#include "..\Utilities\List.h"
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
if(pListHead == nullptr || k == 0)
return nullptr;
ListNode *pAhead = pListHead;
ListNode *pBehind = nullptr;
for(unsigned int i = 0; i < k - 1; ++ i)
{
if(pAhead->m_pNext != nullptr)
pAhead = pAhead->m_pNext;
else
{
return nullptr;
}
}
pBehind = pListHead;
while(pAhead->m_pNext != nullptr)
{
pAhead = pAhead->m_pNext;
pBehind = pBehind->m_pNext;
}
return pBehind;
}
23.链表中环的入口结点
题目：一个链表中包含环，如何找出环的入口结点？例如，在图3.8的链表中，环的入口结点是结点3。
首先我们应该是先判断一个链表是否有环，如果有环再判断入环节点
判断有环：快慢两个指针，快2步，慢一步，如果快走到null，无环。如果快慢相遇则有环。
入环节点其实就是链表倒数第k个节点（环的长度）。这就是上一条题目。所以我们需要先确定环的长度。
确定环的长度：上面已经得到快慢指针相遇的地方，这个相遇的地方一定是在环内，所以继续移动该位置，如果相遇，记录移动的次数就是环的大小。
求入口u节点：相当于求倒数第k的节点。距离固定的快慢指针法。
#include <cstdio>
#include "../Utilities/list.h"
ListNode* MeetingNode(ListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
ListNode* pSlow = pHead->m_pNext;
if(pSlow == nullptr)
return nullptr;
ListNode* pFast = pSlow->m_pNext;
while(pFast != nullptr && pSlow != nullptr)
{
if(pFast == pSlow)
return pFast;
pSlow = pSlow->m_pNext;
pFast = pFast->m_pNext;
if(pFast != nullptr)
pFast = pFast->m_pNext;
}
return nullptr;
}
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* meetingNode = MeetingNode(pHead);
if(meetingNode == nullptr)
return nullptr;
// 得到环中结点的数目
int nodesInLoop = 1;
ListNode* pNode1 = meetingNode;
while(pNode1->m_pNext != meetingNode)
{
pNode1 = pNode1->m_pNext;
++nodesInLoop;
}
// 先移动pNode1，次数为环中结点的数目
pNode1 = pHead;
for(int i = 0; i < nodesInLoop; ++i)
pNode1 = pNode1->m_pNext;
// 再移动pNode1和pNode2
ListNode* pNode2 = pHead;
while(pNode1 != pNode2)
{
pNode1 = pNode1->m_pNext;
pNode2 = pNode2->m_pNext;
}
return pNode1;
}
24.反转链表
题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
我们需要定义三种指针：当前遍历到的节点，前一个节点，后一个节点
#include <cstdio>
#include "..\Utilities\List.h"
ListNode* ReverseList(ListNode* pHead)
{
ListNode* pReversedHead = nullptr;
ListNode* pNode = pHead;
ListNode* pPrev = nullptr;
while(pNode != nullptr)
{
ListNode* pNext = pNode->m_pNext;
if(pNext == nullptr)
pReversedHead = pNode;
pNode->m_pNext = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
25.合并两个排序的链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图3.11中的链表1和链表2，则合并之后的升序链表如链表3所示。
首先我们比较两个链表的头节点，选择较小的头节点加入排序的节点。之后我们继续在两个剩下的链表上找较小的头节点。这就是一个递归的过程。但是要注意空链表的情况
#include <cstdio>
#include "..\Utilities\List.h"
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == nullptr)
return pHead2;
else if(pHead2 == nullptr)
return pHead1;
ListNode* pMergedHead = nullptr;
if(pHead1->m_nValue < pHead2->m_nValue)
{
pMergedHead = pHead1;
pMergedHead->m_pNext = Merge(pHead1->m_pNext, pHead2);
}
else
{
pMergedHead = pHead2;
pMergedHead->m_pNext = Merge(pHead1, pHead2->m_pNext);
}
return pMergedHead;
}
26.树的子结构
题目：输入两棵二叉树A和B，判断B是不是A的子结构。
首先我们看B的父节点，然后在A中找是否存在该节点。然后再以此判断。很容易就此写成一个递归的版本。
#include <cstdio>
struct BinaryTreeNode
{
double m_dbValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);
bool Equal(double num1, double num2);
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
bool result = false;
if(pRoot1 != nullptr && pRoot2 != nullptr)
{
if(Equal(pRoot1->m_dbValue, pRoot2->m_dbValue))
result = DoesTree1HaveTree2(pRoot1, pRoot2);
if(!result)
result = HasSubtree(pRoot1->m_pLeft, pRoot2);
if(!result)
result = HasSubtree(pRoot1->m_pRight, pRoot2);
}
return result;
}
bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
if(pRoot2 == nullptr)
return true;
if(pRoot1 == nullptr)
return false;
if(!Equal(pRoot1->m_dbValue, pRoot2->m_dbValue))
return false;
return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}
bool Equal(double num1, double num2)
{
if((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
return true;
else
return false;
}
27.二叉树的镜像
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
先序遍历这棵树的节点，对于遍历到的每一个节点，如果它有子节点，就交换它的子节点。直到交换完所有非叶子节点的子节点。
#include <cstdio>
#include "..\Utilities\BinaryTree.h"
#include <stack>
void MirrorRecursively(BinaryTreeNode *pNode)
{
if((pNode == nullptr) || (pNode->m_pLeft == nullptr && pNode->m_pRight))
return;
BinaryTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
if(pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);
if(pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}
void MirrorIteratively(BinaryTreeNode* pRoot)
{
if(pRoot == nullptr)
return;
std::stack<BinaryTreeNode*> stackTreeNode;
stackTreeNode.push(pRoot);
while(stackTreeNode.size() > 0)
{
BinaryTreeNode *pNode = stackTreeNode.top();
stackTreeNode.pop();
BinaryTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);
if(pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}
28.对称的二叉树
题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
第一个思路，既然判断一棵二叉树对称是看他是否和他的镜像一样，那么我们可以借助上面的方法，先构建这颗树的镜像，再依次判断两个树是否一样。
第二个思路，先序遍历都是根左右，如果另一只先序遍历是根右左，如果这两种遍历结果一样，则对称。但是存在一种情况，就是所有节点都一样但结构不一样，所以我们需要在遍历的过程中，也要遍历入nullptr
#include <cstdio>
#include "../Utilities/BinaryTree.h"
bool isSymmetrical(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);
bool isSymmetrical(BinaryTreeNode* pRoot)
{
return isSymmetrical(pRoot, pRoot);
}
bool isSymmetrical(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
if(pRoot1 == nullptr && pRoot2 == nullptr)
return true;
if(pRoot1 == nullptr || pRoot2 == nullptr)
return false;
if(pRoot1->m_nValue != pRoot2->m_nValue)
return false;
return isSymmetrical(pRoot1->m_pLeft, pRoot2->m_pRight)
&& isSymmetrical(pRoot1->m_pRight, pRoot2->m_pLeft);
}
29.顺时针打印矩阵
题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
将整个问题分解开，打印整个矩阵，相当于一圈圈剥开矩阵，一圈一圈剥开又可以分解成4个不同方向留一个输出。
#include <cstdio>
void PrintMatrixInCircle(int** numbers, int columns, int rows, int start);
void printNumber(int number);
void PrintMatrixClockwisely(int** numbers, int columns, int rows)
{
if(numbers == nullptr || columns <= 0 || rows <= 0)
return;
int start = 0;
while(columns > start * 2 && rows > start * 2)
{
PrintMatrixInCircle(numbers, columns, rows, start);
++start;
}
}
void PrintMatrixInCircle(int** numbers, int columns, int rows, int start)
{
int endX = columns - 1 - start;
int endY = rows - 1 - start;
// 从左到右打印一行
for(int i = start; i <= endX; ++i)
{
int number = numbers[start][i];
printNumber(number);
}
// 从上到下打印一列
if(start < endY)
{
for(int i = start + 1; i <= endY; ++i)
{
int number = numbers[i][endX];
printNumber(number);
}
}
// 从右到左打印一行
if(start < endX && start < endY)
{
for(int i = endX - 1; i >= start; --i)
{
int number = numbers[endY][i];
printNumber(number);
}
}
// 从下到上打印一行
if(start < endX && start < endY - 1)
{
for(int i = endY - 1; i >= start + 1; --i)
{
int number = numbers[i][start];
printNumber(number);
}
}
}
void printNumber(int number)
{
printf("%d\t", number);
}
30.包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。
使用两个栈，一个Data栈，一个min栈。初始时两个为空，data压入一个数字，该数字同时压入min。data再进一个数字，该数字与min的栈顶比较，如果该数字更小，压入该数字。如果min栈栈顶更小，则重复压入栈顶。
#include <stack>
#include <assert.h>
template <typename T> class StackWithMin
{
public:
StackWithMin() {}
virtual ~StackWithMin() {}
T& top();
const T& top() const;
void push(const T& value);
void pop();
const T& min() const;
bool empty() const;
size_t size() const;
private:
std::stack<T> m_data; // 数据栈，存放栈的所有元素
std::stack<T> m_min; // 辅助栈，存放栈的最小元素
};
template <typename T> void StackWithMin<T>::push(const T& value)
{
// 把新元素添加到辅助栈
m_data.push(value);
// 当新元素比之前的最小元素小时，把新元素插入辅助栈里；
// 否则把之前的最小元素重复插入辅助栈里
if(m_min.size() == 0 || value < m_min.top())
m_min.push(value);
else
m_min.push(m_min.top());
}
template <typename T> void StackWithMin<T>::pop()
{
assert(m_data.size() > 0 && m_min.size() > 0);
m_data.pop();
m_min.pop();
}
template <typename T> const T& StackWithMin<T>::min() const
{
assert(m_data.size() > 0 && m_min.size() > 0);
return m_min.top();
}
template <typename T> T& StackWithMin<T>::top()
{
return m_data.top();
}
template <typename T> const T& StackWithMin<T>::top() const
{
return m_data.top();
}
template <typename T> bool StackWithMin<T>::empty() const
{
return m_data.empty();
}
template <typename T> size_t StackWithMin<T>::size() const
{
return m_data.size();
}
32 不分行从上往下打印二叉树
实际就是二叉树的层序遍历，层序遍历是宽度优先，用队列模拟实现。根节点入队，访问队头，退队，同时把对头的子节点入队。之后仍然是访问队头，退队，入子节点。直到队空。
#include <cstdio>
#include "..\Utilities\BinaryTree.h"
#include <deque>
void PrintFromTopToBottom(BinaryTreeNode* pRoot)
{
if(pRoot == nullptr)
return;
std::deque<BinaryTreeNode *> dequeTreeNode;
dequeTreeNode.push_back(pRoot);
while(dequeTreeNode.size())
{
BinaryTreeNode *pNode = dequeTreeNode.front();
dequeTreeNode.pop_front();
printf("%d ", pNode->m_nValue);
if(pNode->m_pLeft)
dequeTreeNode.push_back(pNode->m_pLeft);
if(pNode->m_pRight)
dequeTreeNode.push_back(pNode->m_pRight);
}
}
33.二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
后序遍历，最后一个值就是根节点。然后前面部分一半是左子树，一半是右子树。由于是搜索树，所以左子树应该所有节点小于根，右子树所有节点大于根。然后再递归的再这两颗子树上判断。
#include <cstdio>
// BST：Binary Search Tree，二叉搜索树
bool VerifySquenceOfBST(int sequence[], int length)
{
if(sequence == nullptr || length <= 0)
return false;
int root = sequence[length - 1];
// 在二叉搜索树中左子树的结点小于根结点
int i = 0;
for(; i < length - 1; ++ i)
{
if(sequence[i] > root)
break;
}
// 在二叉搜索树中右子树的结点大于根结点
int j = i;
for(; j < length - 1; ++ j)
{
if(sequence[j] < root)
return false;
}
// 判断左子树是不是二叉搜索树
bool left = true;
if(i > 0)
left = VerifySquenceOfBST(sequence, i);
// 判断右子树是不是二叉搜索树
bool right = true;
if(i < length - 1)
right = VerifySquenceOfBST(sequence + i, length - i - 1);
return (left && right);
}
34 二叉树中和为某一值的路径
题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
用前序遍历的方式访问节点，并以此建立二叉树的路径。当我们访问到一个节点时，我们把这个节点加入到路径里。并累加该节点的值。如果当前节点是叶子节点，并且路径值正好是输入整数，则打印。如果不是叶子节点，则遍历子节点。
#include <cstdio>
#include "..\Utilities\BinaryTree.h"
#include <vector>
void FindPath(BinaryTreeNode* pRoot, int expectedSum, std::vector<int>& path, int& currentSum);
void FindPath(BinaryTreeNode* pRoot, int expectedSum)
{
if(pRoot == nullptr)
return;
std::vector<int> path;
int currentSum = 0;
FindPath(pRoot, expectedSum, path, currentSum);
}
void FindPath
(
BinaryTreeNode* pRoot,
int expectedSum,
std::vector<int>& path,
int& currentSum
)
{
currentSum += pRoot->m_nValue;
path.push_back(pRoot->m_nValue);
// 如果是叶结点，并且路径上结点的和等于输入的值
// 打印出这条路径
bool isLeaf = pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr;
if(currentSum == expectedSum && isLeaf)
{
printf("A path is found: ");
std::vector<int>::iterator iter = path.begin();
for(; iter != path.end(); ++ iter)
printf("%d\t", *iter);
printf("\n");
}
// 如果不是叶结点，则遍历它的子结点
if(pRoot->m_pLeft != nullptr)
FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
if(pRoot->m_pRight != nullptr)
FindPath(pRoot->m_pRight, expectedSum, path, currentSum);
// 在返回到父结点之前，在路径上删除当前结点，
// 并在currentSum中减去当前结点的值
currentSum -= pRoot->m_nValue;
path.pop_back();
}
36.二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
二叉搜索树的中序遍历方式其实就是有序的。最主要的是根节点需要最后与左子树最左边的节点，右子树最左边的节点相连。
#include <cstdio>
#include "..\Utilities\BinaryTree.h"
void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList);
BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
BinaryTreeNode *pLastNodeInList = nullptr;
ConvertNode(pRootOfTree, &pLastNodeInList);
// pLastNodeInList指向双向链表的尾结点，
// 我们需要返回头结点
BinaryTreeNode *pHeadOfList = pLastNodeInList;
while(pHeadOfList != nullptr && pHeadOfList->m_pLeft != nullptr)
pHeadOfList = pHeadOfList->m_pLeft;
return pHeadOfList;
}
void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
{
if(pNode == nullptr)
return;
BinaryTreeNode *pCurrent = pNode;
if (pCurrent->m_pLeft != nullptr)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
pCurrent->m_pLeft = *pLastNodeInList;
if(*pLastNodeInList != nullptr)
(*pLastNodeInList)->m_pRight = pCurrent;
*pLastNodeInList = pCurrent;
if (pCurrent->m_pRight != nullptr)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
38 字符串的全排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
这题思路是这样的，给定的字符串是abc，那么第一步首先圈出a是第一个字符，把a与后面的所有字符换位置，那么一共有3个：abc,bac,cba,
之后，再对剩下的位置采用一样的方法，确定第一个位置，把第一个位置与剩下的互换。abc，剩下bc，确定第一个字符b，依次与剩余的互换，得到acb。 所以基本方式就是把字符串分割成两部分，一部分是第一个字符，一部分是剩余的字符。然后把第一个字符与剩下的互换。之后对剩下的采用同样的方法。很显然可以采用递归。
#include <cstdio>
void Permutation(char* pStr, char* pBegin);
void Permutation(char* pStr)
{
if(pStr == nullptr)
return;
Permutation(pStr, pStr);
}
void Permutation(char* pStr, char* pBegin)
{
if(*pBegin == '\0')
{
printf("%s\n", pStr);
}
else
{
for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
{
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
39.数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
次数超过一半，那么如果这个数组是有序的，那么中位数就是那个数。可是这里没有序。我们可以借助快排的思想。随机找一个数，找到其有序点。如果左右长度相等，那么这个数就是我们要找的。如果不是，则在较长的一端继续这样。直到有一次两边是相等的。
#include <cstdio>
#include "..\Utilities\Array.h"
bool g_bInputInvalid = false;
bool CheckInvalidArray(int* numbers, int length)
{
g_bInputInvalid = false;
if(numbers == nullptr && length <= 0)
g_bInputInvalid = true;
return g_bInputInvalid;
}
bool CheckMoreThanHalf(int* numbers, int length, int number)
{
int times = 0;
for(int i = 0; i < length; ++i)
{
if(numbers[i] == number)
times++;
}
bool isMoreThanHalf = true;
if(times * 2 <= length)
{
g_bInputInvalid = true;
isMoreThanHalf = false;
}
return isMoreThanHalf;
}
40.最小的k个数
题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
第一种思路，和前面找超过一半的一样，基于partition，只要我们找到一个partition为k-1的位置，那么该位置前面就是最小的k个，只是没有顺序。所以我们可以递归的找partition。如果当前找的partion大于k-1，则把end设为该partion，在这一段继续找。如果小于，则把start设为该位置。在后面继续找，直到找到partition。但是这种方法需要改变输入数组。并且需要把整个数组内存读入。
第二种思路，设一个大小为k的容器，先读入数组前k的数字。此时容器满，后面每读入一个数字，1.找到当前容器最大值 2.比较读入的数字与该最大值，若小于最大值，则把读入的值插入，删除之前的最大值。 该容器可以用堆实现。可以直接使用STL里的multiset（set本身有序且查找复杂度很低）。这种方法可以针对海量数据。
#include <cstdio>
#include "..\Utilities\Array.h"
#include <set>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;
// ====================方法1====================
void GetLeastNumbers_Solution1(int* input, int n, int* output, int k)
{
if(input == nullptr || output == nullptr || k > n || n <= 0 || k <= 0)
return;
int start = 0;
int end = n - 1;
int index = Partition(input, n, start, end);
while(index != k - 1)
{
if(index > k - 1)
{
end = index - 1;
index = Partition(input, n, start, end);
}
else
{
start = index + 1;
index = Partition(input, n, start, end);
}
}
for(int i = 0; i < k; ++i)
output[i] = input[i];
}
// ====================方法2====================
typedef multiset<int, std::greater<int> > intSet;
typedef multiset<int, std::greater<int> >::iterator setIterator;
void GetLeastNumbers_Solution2(const vector<int>& data, intSet& leastNumbers, int k)
{
leastNumbers.clear();
if(k < 1 || data.size() < k)
return;
vector<int>::const_iterator iter = data.begin();
for(; iter != data.end(); ++ iter)
{
if((leastNumbers.size()) < k)
leastNumbers.insert(*iter);
else
{
setIterator iterGreatest = leastNumbers.begin();
if(*iter < *(leastNumbers.begin()))
{
leastNumbers.erase(iterGreatest);
leastNumbers.insert(*iter);
}
}
}
}
42.连续子数组的最大和
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
如果列出所有排列，n(n-1)/2,复杂度高。基于动态规划的思想，计算f(i)如果前面f(i-1)是负数，看Data(i)时，不需要考虑f(i-1),直接从Data(i)开始。
#include <cstdio>
bool g_InvalidInput = false;
int FindGreatestSumOfSubArray(int *pData, int nLength)
{
if((pData == nullptr) || (nLength <= 0))
{
g_InvalidInput = true;
return 0;
}
g_InvalidInput = false;
int nCurSum = 0;
int nGreatestSum = 0x80000000;
for(int i = 0; i < nLength; ++i)
{
if(nCurSum <= 0)
nCurSum = pData[i];
else
nCurSum += pData[i];
if(nCurSum > nGreatestSum)
nGreatestSum = nCurSum;
}
return nGreatestSum;
}
50.字符串中第一个只出现一次的字符
题目：在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出'b'。
利用哈希表，第一个遍历时，key记录字符。value记录出现次数。第二次遍历时，遍历到第一个value为1的字符则输出。
#include <cstdio>
#include <string>
char FirstNotRepeatingChar(const char* pString)
{
if(pString == nullptr)
return '\0';
const int tableSize = 256;
unsigned int hashTable[tableSize];
for(unsigned int i = 0; i < tableSize; ++i)
hashTable[i] = 0;
const char* pHashKey = pString;
while(*(pHashKey) != '\0')
hashTable[*(pHashKey++)] ++;
pHashKey = pString;
while(*pHashKey != '\0')
{
if(hashTable[*pHashKey] == 1)
return *pHashKey;
pHashKey++;
}
return '\0';
}
52.两个链表的第一个公共结点
题目：输入两个链表，找出它们的第一个公共结点。
相交链表是什么样子的，他们的尾部肯定是相同的。但是单向链表无法从尾部访问。
第一种思路：利用两个辅助栈，把两个链表分别入栈，然后同时弹栈，谈一次比较一次。即可。但是需要辅助站。
第二种思路：首先遍历两个链表，得到两个链表的长度n和m，得到差值后，把长的链表先走差值步，之后两者同时走。依次比较
#include <cstdio>
#include "..\Utilities\List.h"
unsigned int GetListLength(ListNode* pHead);
ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2)
{
// 得到两个链表的长度
unsigned int nLength1 = GetListLength(pHead1);
unsigned int nLength2 = GetListLength(pHead2);
int nLengthDif = nLength1 - nLength2;
ListNode* pListHeadLong = pHead1;
ListNode* pListHeadShort = pHead2;
if(nLength2 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
}
// 先在长链表上走几步，再同时在两个链表上遍历
for(int i = 0; i < nLengthDif; ++i)
pListHeadLong = pListHeadLong->m_pNext;
while((pListHeadLong != nullptr) &&
(pListHeadShort != nullptr) &&
(pListHeadLong != pListHeadShort))
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort = pListHeadShort->m_pNext;
}
// 得到第一个公共结点
ListNode* pFisrtCommonNode = pListHeadLong;
return pFisrtCommonNode;
}
unsigned int GetListLength(ListNode* pHead)
{
unsigned int nLength = 0;
ListNode* pNode = pHead;
while(pNode != nullptr)
{
++nLength;
pNode = pNode->m_pNext;
}
return nLength;
}
53.在排序数组中查找数字
题目1：数字在排序数组中出现的次数:统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3, 3, 3, 4, 5}和数字3，由于3在这个数组中出现了4次，因此输出4。
在一个有序数组里，找某个数字出现的次数。直接遍历复杂度O(N)。有序数组查找问题，一定切记使用二分搜索法。有序数组找一个数字出现次数，由于有序，那么这些数字一定是连续在一起的。那么只要我们找到了最右边的一个3，和最左边的一个3.那么相应的长度就知道了。1.有序数组找最左边的一个3，二分，如果中间值大于3，那么就在左边继续找，如果中间值小于3那么在右边找。如果中间值等于3，那么看这个中间值左边是否是3，如果不是，那么找到了最左边的3，如果中间值左边也是3，那么还是在左边继续找。2.有序数组中找右边的3过程和上面一样。
#include <cstdio>
int GetFirstK(const int* data, int length, int k, int start, int end);
int GetLastK(const int* data, int length, int k, int start, int end);
int GetNumberOfK(const int* data, int length, int k)
{
int number = 0;
if(data != nullptr && length > 0)
{
int first = GetFirstK(data, length, k, 0, length - 1);
int last = GetLastK(data, length, k, 0, length - 1);
if(first > -1 && last > -1)
number = last - first + 1;
}
return number;
}
// 找到数组中第一个k的下标。如果数组中不存在k，返回-1
int GetFirstK(const int* data, int length, int k, int start, int end)
{
if(start > end)
return -1;
int middleIndex = (start + end) / 2;
int middleData = data[middleIndex];
if(middleData == k)
{
if((middleIndex > 0 && data[middleIndex - 1] != k)
|| middleIndex == 0)
return middleIndex;
else
end = middleIndex - 1;
}
else if(middleData > k)
end = middleIndex - 1;
else
start = middleIndex + 1;
return GetFirstK(data, length, k, start, end);
}
// 找到数组中最后一个k的下标。如果数组中不存在k，返回-1
int GetLastK(const int* data, int length, int k, int start, int end)
{
if(start > end)
return -1;
int middleIndex = (start + end) / 2;
int middleData = data[middleIndex];
if(middleData == k)
{
if((middleIndex < length - 1 && data[middleIndex + 1] != k)
|| middleIndex == length - 1)
return middleIndex;
else
start = middleIndex + 1;
}
else if(middleData < k)
start = middleIndex + 1;
else
end = middleIndex - 1;
return GetLastK(data, length, k, start, end);
}
题目2：0到n-1中缺失的数字：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
长度n-1，数字范围0-n-1，并且有序。说明在那个缺失值之前，数字和其下标是相同的，之后数字和缺失值差一；那么我们只要在有序数组中找到第一个数字和缺失值差1的位置即可。仍然采用二分，如果中间值等于小标，那么继续在右边查找。如果中间值和下标差一，那么看他前一个数字，如果签一个数字和下标相等，那么中间值就是那个值。如果前一个数还是和下标差一，那么继续在左边查找。
#include <cstdio>
int GetMissingNumber(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;
int left = 0;
int right = length - 1;
while(left <= right)
{
int middle = (right + left) >> 1;
if(numbers[middle] != middle)
{
if(middle == 0 || numbers[middle - 1] == middle - 1)
return middle;
right = middle - 1;
}
else
left = middle + 1;
}
if(left == length)
return length;
// 无效的输入，比如数组不是按要求排序的，
// 或者有数字不在0到n-1范围之内
return -1;
}
题目：假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等。
递增有序数组查找，二分。中间值恰好等于下标，输出。中间值大于下标，由于递增，那么右边的数字依然大于下标。所以在左边继续找。如果小与下标，那么说明左边都小于，则在右边继续找。
#include <cstdio>
int GetNumberSameAsIndex(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;
int left = 0;
int right = length - 1;
while(left <= right)
{
int middle = left + ((right - left) >> 1);
if(numbers[middle] == middle)
return middle;
if(numbers[middle] > middle)
right = middle - 1;
else
left = middle + 1;
}
return -1;
}
54.二叉搜索树的第k个结点
题目：给定一棵二叉搜索树，请找出其中的第k大的结点。
二叉搜索树的中序遍历其实就是一个有序数组，那么就很容易找到第k个节点。
#include <cstdio>
#include "../Utilities/BinaryTree.h"
const BinaryTreeNode* KthNodeCore(const BinaryTreeNode* pRoot, unsigned int& k);
const BinaryTreeNode* KthNode(const BinaryTreeNode* pRoot, unsigned int k)
{
if(pRoot == nullptr || k == 0)
return nullptr;
return KthNodeCore(pRoot, k);
}
const BinaryTreeNode* KthNodeCore(const BinaryTreeNode* pRoot, unsigned int& k)
{
const BinaryTreeNode* target = nullptr;
if(pRoot->m_pLeft != nullptr)
target = KthNodeCore(pRoot->m_pLeft, k);
if(target == nullptr)
{
if(k == 1)
target = pRoot;
k--;
}
if(target == nullptr && pRoot->m_pRight != nullptr)
target = KthNodeCore(pRoot->m_pRight, k);
return target;
}
55.二叉树的深度
题目：输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
我们可以用递归分解的思想，如果一棵树只有根节点，那么长度就是1.如果一个节点只有右子树，那么深度就是右子树深度加一。如果只有左子树，那么深度就是左子树深度加一。如果同时由左子树和右子树，那么深度就是左右子树深度较大值加1.
#include <cstdio>
#include "..\Utilities\BinaryTree.h"
int TreeDepth(const BinaryTreeNode* pRoot)
{
if(pRoot == nullptr)
return 0;
int nLeft = TreeDepth(pRoot->m_pLeft);
int nRight = TreeDepth(pRoot->m_pRight);
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
判断平衡二叉树：分解成计算左右子树的深度，看差值是否大于1.
57.和为s的两个数字
题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。
排序数组给一个target，找到一对相加等于target的。
- 依次遍历，对于第一个数x，在后面找target-x；
- 利用hashmap，对于数x，在map里找是否存在target-x；
- 双指针法：初始一个指针在第一个数字，第二个指针在末尾的数字。两个数字相加，如果和大于target，则高指针下移。如果和小于target。则低指针上移。直到两个指针相遇。
#include <cstdio>
bool FindNumbersWithSum(int data[], int length, int sum,
int* num1, int* num2)
{
bool found = false;
if(length < 1 || num1 == nullptr || num2 == nullptr)
return found;
int ahead = length - 1;
int behind = 0;
while(ahead > behind)
{
long long curSum = data[ahead] + data[behind];
if(curSum == sum)
{
*num1 = data[behind];
*num2 = data[ahead];
found = true;
break;
}
else if(curSum > sum)
ahead --;
else
behind ++;
}
return found;
}
如果要求打印出所有对，则低+高<=target时，低右移动，且跳过与之前一样的。
threesum：调用之前twosum的接口，把数组分为两部分，一个是第一个数字x，一个剩余部分，在剩余部分找target-x的twosum。之后右移动第一个数字，且跳过所有相同的，继续分割数组，在剩余数组内找twosum
题目2：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。
设置small和big两个值，那么small到big就可以表示一个连续数组。初始small=1，big=2，如果small+到big<target，则big+1；如果small+到big>target，则small+1.一直到small到target/2为止。
#include <cstdio>
void PrintContinuousSequence(int small, int big);
void FindContinuousSequence(int sum)
{
if(sum < 3)
return;
int small = 1;
int big = 2;
int middle = (1 + sum) / 2;
int curSum = small + big;
while(small < middle)
{
if(curSum == sum)
PrintContinuousSequence(small, big);
while(curSum > sum && small < middle)
{
curSum -= small;
small ++;
if(curSum == sum)
PrintContinuousSequence(small, big);
}
big ++;
curSum += big;
}
}
void PrintContinuousSequence(int small, int big)
{
for(int i = small; i <= big; ++ i)
printf("%d ", i);
printf("\n");
}
58.翻转单词顺序
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
分两步：第一步翻转所有字符，第二步翻转每个单词的字符。
#include <cstdio>
#include "..\Utilities\StringUtil.h"
#include <string>
char* ReverseSentence(char *pData)
{
if(pData == nullptr)
return nullptr;
char *pBegin = pData;
char *pEnd = pData;
while(*pEnd != '\0')
pEnd ++;
pEnd--;
// 翻转整个句子
Reverse(pBegin, pEnd);
// 翻转句子中的每个单词
pBegin = pEnd = pData;
while(*pBegin != '\0')
{
if(*pBegin == ' ')
{
pBegin ++;
pEnd ++;
}
else if(*pEnd == ' ' || *pEnd == '\0')
{
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
pEnd ++;
}
return pData;
}
题目：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串"abcdefg"和数字2，该函数将返回左旋转2位得到的结果"cdefgab"。
分两步：先翻转各自单词ab和cdefg，再翻转全部。
#include <cstdio>
#include "..\Utilities\StringUtil.h"
#include <string.h>
char* LeftRotateString(char* pStr, int n)
{
if(pStr != nullptr)
{
int nLength = static_cast<int>(strlen(pStr));
if(nLength > 0 && n > 0 && n < nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// 翻转字符串的前面n个字符
Reverse(pFirstStart, pFirstEnd);
// 翻转字符串的后面部分
Reverse(pSecondStart, pSecondEnd);
// 翻转整个字符串
Reverse(pFirstStart, pSecondEnd);
}
}
return pStr;
}
60.n个骰子的点数
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
n个骰子的点数，可以先把骰分成两堆，第一堆只有一个，第二堆n-1个，单独那一个有可能出现1-6的点数。我们需要计算1-6每一个点数和剩下的n-1个骰子计算点数和。接下来继续把剩下的n-1个骰子分成两部分，一堆只有一个，另一堆n-2个，把上一轮的点数和这一轮相加，再计算
n-2个的情况，直到还是最后一个。这就是一个递归的思路。
#include <cstdio>
#include <math.h>
int g_maxValue = 6;
// ====================方法一====================
void Probability(int number, int* pProbabilities);
void Probability(int original, int current, int sum, int* pProbabilities);
void PrintProbability_Solution1(int number)
{
if(number < 1)
return;
int maxSum = number * g_maxValue;
int* pProbabilities = new int[maxSum - number + 1];
for(int i = number; i <= maxSum; ++i)
pProbabilities[i - number] = 0;
Probability(number, pProbabilities);
int total = pow((double)g_maxValue, number);
for(int i = number; i <= maxSum; ++i)
{
double ratio = (double)pProbabilities[i - number] / total;
printf("%d: %e\n", i, ratio);
}
delete[] pProbabilities;
}
void Probability(int number, int* pProbabilities)
{
for(int i = 1; i <= g_maxValue; ++i)
Probability(number, number, i, pProbabilities);
}
void Probability(int original, int current, int sum,
int* pProbabilities)
{
if(current == 1)
{
pProbabilities[sum - original]++;
}
else
{
for(int i = 1; i <= g_maxValue; ++i)
{
Probability(original, current - 1, i + sum, pProbabilities);
}
}
}
62.圆圈中最后剩下的数字
题目：0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
著名的约瑟夫环问题，其实就是一个环形链表，我们可以使用list来模拟实现，但是每当我们遍历到末尾数字时，就要自动回到链表开头。
#include <cstdio>
#include <list>
using namespace std;
// ====================方法1====================
int LastRemaining_Solution1(unsigned int n, unsigned int m)
{
if(n < 1 || m < 1)
return -1;
unsigned int i = 0;
list<int> numbers;
for(i = 0; i < n; ++ i)
numbers.push_back(i);
list<int>::iterator current = numbers.begin();
while(numbers.size() > 1)
{
for(int i = 1; i < m; ++ i)
{
current ++;
if(current == numbers.end())
current = numbers.begin();
}
list<int>::iterator next = ++ current;
if(next == numbers.end())
next = numbers.begin();
-- current;
numbers.erase(current);
current = next;
}
return *(current);
}
63.股票的最大利润
题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖交易该股票可能获得的利润是多少？例如一只股票在某些时间节点的价格为{9, 11, 8, 5, 7, 12, 16, 14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。
我们可以定义一个数组和输入数组一样大小，每个位置i表示，以当前价个卖出时获得的最大利润。这个数组计算玩后，最大值就是我们要的最大利润。计算位置i卖出的最大利润，只需要记得前i-1个值得最小值即可。所以再定义一个记录前i-1个数字最小值的参数。
#include <cstdio>
int MaxDiff(const int* numbers, unsigned length)
{
if(numbers == nullptr && length < 2)
return 0;
int min = numbers[0];
int maxDiff = numbers[1] - min;
for(int i = 2; i < length; ++i)
{
if(numbers[i - 1] < min)
min = numbers[i - 1];
int currentDiff = numbers[i] - min;
if(currentDiff > maxDiff)
maxDiff = currentDiff;
}
return maxDiff;
}
其它(from zuochengyun live)
1. 两个有序数组A和B，找到最长的公共部分。
思路1：双重循环，遍历A遍历B，时间复杂度O(N×M)
思路2：对于A中每一个数字，去B中二分找。O(N×logM)
思路3：同时设立两个开始指针，la，lb。谁小谁动。两个相等时一起动。O(N+M)
注意：不能说O(N+M)优于O(N×logM)，看数据量。
2.调换左右两部分 12345 67 ----- 67 12345
左右两部分依次单独逆序，12345-----54321 67----76，得到54321 76，再把整体逆序： 67 12345.
注意：逆序本身没有空间开销，高低两个指针互换即可。
3.关于sort()函数
sort(A), size(A)=N;
- 如果n<60，直接插入排序。O(N^2),N较小时，平方也不大。但是常数空间O(1) (基于比较交换的排序都是)。
- n>60;则选择快速排序和归并排序。当比较类型为基本类型时，选择快排。如果是类类型时，选择归并排序。
4.一个无序数组输出其排序后相邻差值最大的差值。O(N)
- 0(N)的复杂度就要求我们不能进行普通排序，我们可以进行桶排序。
2.遍历一次数组，得到最大值和最小值[x,y]，以及数组长度N，则设立N+1个桶(等分[x,y])，把N个数塞入N+1个桶，则至少有一个空桶。该空桶前一个桶的最大值和后一个桶的最小值差值大于一个桶的范围。所以我们找最大差值时不需要考虑桶内的情况。
5.用数组实现队列
1.用两个指针，end表示从那个位置入队，start表示从哪个位置出队。end和start初始都在数组开头，两者无关。但是设立size值，表示当前队列长度。当size为N时，end回到数组开头，不可以入队。size只要不为0，start就可以动。
6.之字型打印矩阵
最左上角位置l两个指针(r1,c1) (r2,c2)，前者往右走，走到不能走往下走。后者往下走，走到不能走往右走。两个指针每移动一次就会形成一条对角线。打印该对角线。
7. 输出N个有序数组整体最大的TOP K
建立大小为N的大顶堆，第一步，首先把N个数组最后最大的数插入堆。然后输出该堆顶，并且把堆顶元素所在的数组下一个位置的元素插入堆中，重新建堆。然后再输出堆顶。经过k次，就可以得到最大的k个数。
