剑指offer刷题记录
为了能从书中学一些代码规范之类的东西,有一些代码是跟着书上写的,有的是自己写的
数组
数组中重复的数字
题目描述:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
//做法一:哈希表
//时间复杂度:O(n) ,空间复杂度O(n)
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
int a[1<<11]={1};
for(int i=0;i<length;++i)
{
if(a[numbers[i]]==-1)
{
*duplication=numbers[i];
return true;
break;
}
a[numbers[i]]=-1;
}
return false;
}
};
//做法二:
//时间复杂度:O(n) ,空间复杂度O(1)
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
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){
int temp = numbers[i];
if(numbers[i] == numbers[temp]){
*duplication = numbers[i];
return true;
}
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
};
二维数组中的查找
题目描述:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
bool found = false;
int rows = array.size();
int cols = array[0].size();
int i = 0; //行
int j = cols -1; //列
while(i<rows && j>=0){
if(array[i][j] > target){
j--;
}else if(array[i][j] < target){
i++;
}else {
return true;
}
}
return false;
}
};
字符串
替换空格
题目描述:
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution {
public:
void replaceSpace(char *str,int length) {
if(str == nullptr || length<= 0){
return ;
}
int originalLength = 0; //字符串实际长度
int numberOfBlank = 0; //空格长度
for(int i=0;str[i]!='\0';++i){
++originalLength;
if(str[i]==' '){
++numberOfBlank;
}
}
int newLength = originalLength + numberOfBlank * 2;
if(newLength>length){
return ;
}
int p1 = originalLength;
int p2 = newLength;
while(p1 >= 0 && p2>p1){
if(str[p1]==' '){
str[p2--] = '0';
str[p2--] = '2';
str[p2--] = '%';
p1--;
}else {
str[p2--] = str[p1--];
}
}
return ;
}
};
链表
从尾到头打印链表
题目描述:
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> a;
std:: stack<ListNode*> nodes;
ListNode* pNode = head;
while(pNode != nullptr){
nodes.push(pNode);
pNode = pNode->next;
}
while(!nodes.empty()){
pNode = nodes.top();
a.push_back(pNode->val);
nodes.pop();
}
return a;
}
};
树
重建二叉树
题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* R(vector<int> pre,int abegin,int aend, vector<int> vin,int bbegin,int bend){
if(abegin>=aend || bbegin>=bend){
return NULL;
}
TreeNode* root = new TreeNode(pre[abegin]);
int pivot;
for(pivot=bbegin;pivot<bend;pivot++){
if(vin[pivot] == pre[abegin]){
break;
}
}
root->left = R(pre,abegin+1,abegin+(pivot-bbegin)+1,vin,bbegin,pivot);
root->right = R(pre,abegin+(pivot-bbegin)+1,aend,vin,pivot+1,bend);
return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
return R(pre,0,pre.size(),vin,0,vin.size());
}
};
栈和队列:
用两个栈实现一个队列:
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int num = stack2.top();
stack2.pop();
return num;
}
private:
stack<int> stack1;
stack<int> stack2;
};
递归和循环
斐波那契数列
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
class Solution {
public:
int Fibonacci(int n) {
int maxn = 40;
int dp[maxn];
dp[1] =1;
dp[2] =1;
for(int i=3;i<=n;++i){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
};
跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
class Solution {
public:
int jumpFloor(int number) {
int maxn = 100;
int dp[maxn];
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<=number;++i)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[number];
}
};
变态跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
class Solution {
public:
int jumpFloorII(int number) {
int maxn = 100;
long long int dp[maxn];
dp[1] =1;
dp[2] =2;
for(int i=3;i<=number;++i){
dp[i] = 1;
for(int j= 1;j<i;++j){
dp[i]+=dp[j];
}
}
return dp[number];
}
};
矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
class Solution {
public:
int rectCover(int number) {
int maxn = 100;
int dp[maxn] ;
dp[1] =1;
dp[2] =2;
for(int i = 3;i <= number ; ++i){
dp[i] = dp[i-1]+ dp[i-2];
}
return dp[number];
}
};
位运算
二进制中1的个数
class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
int t = 32;
while(t--){
if(n&1)
{
cnt++;
}
n = n>>1;
}
return cnt;
}
};
查找和排序
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int low = 0;
int high = rotateArray.size()-1;
int mid;
if (rotateArray.empty()) return 0;
while(low<high){
mid = low + (high-low)/2;
if (rotateArray[low] < rotateArray[high]) return rotateArray[low];
if( rotateArray[low] < rotateArray[mid]){
low = mid+1;
}else if(rotateArray[mid] < rotateArray[high])
{
high = mid;
}else {
low++;
}
}
return rotateArray[low];
}
};
回溯法
矩阵中的路径
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。
例如
a b c e
s f c s
a d e e
矩阵中包含一条字符串"bccced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
class Solution {
public:
bool hashPathCore(const char* matrix,int rows,int cols,int row,int col,char* str,int& pathLen,bool* visited){
if( str[pathLen] =='\0'){
return true;
}
bool hasPath = false;
if(row>=0 && row<rows && col>=0 && col<cols && str[pathLen] == matrix[row*cols+col] && !visited[row*cols+col] ){
++pathLen;
visited[row*cols+col]=true;
hasPath = hashPathCore(matrix,rows,cols,row-1,col,str,pathLen,visited)
|| hashPathCore(matrix,rows,cols,row,col-1,str,pathLen,visited)
|| hashPathCore(matrix,rows,cols,row+1,col,str,pathLen,visited)
|| hashPathCore(matrix,rows,cols,row,col+1,str,pathLen,visited);
if(!hasPath){
--pathLen;
visited[row*cols+col]=false;
}
}
return hasPath;
}
bool hasPath(char* matrix, int rows, int cols, 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 pathLen = 0;
for(int row = 0;row<rows;++row){
for(int col = 0;col<cols;++col){
if(hashPathCore(matrix,rows,cols,row,col,str,pathLen,visited)){
return true;
}
}
}
return false;
}
};
机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 =
19。请问该机器人能够达到多少个格子?
class Solution {
public:
int cnt = 0;
int map[1005][1005];
void init(){
for(int i=0;i<1005;++i){
for(int j=0;j<1005;++j){
map[i][j]=0;
}
}
}
int cul(int num){
int ans = 0;
while(num){
ans+=num%10;
num/=10;
}
return ans;
}
void dfs(int k,int x,int y,int rows,int cols){
int t = cul(x)+cul(y);
if( map[x][y] == 1 ){
return ;
}
if(x<0 || x>=cols || y<0 || y>=rows)
{
return ;
}
if(t>k){
return ;
}
cnt++;
map[x][y] =1;
dfs(k,x+1,y,rows,cols);
dfs(k,x-1,y,rows,cols);
dfs(k,x,y+1,rows,cols);
dfs(k,x,y-1,rows,cols);
}
int movingCount(int threshold, int rows, int cols)
{
init();
dfs(threshold,0,0,rows,cols);
return cnt;
}
};