代码

剑指offer

//1. 拷贝构造函数
#include <iostream>
using namespace std;
class CMyString{
public:
    CMyString(char* pData = NULL);
    CMyString(const CMyString& str);
    CMyString& operator = (const CMyString& str);
    ~CMyString(void);
private:
    char* m_pData;
};
CMyString& CMyString::operator = (const CMyString& str) {
    if (this == & str) 
        return *this;
    delete [] m_pData;
    m_pData = NULL;
    m_pData = new char[strlen(str.m_pData) + 1];
    strcpy(m_pData, str.m_pData);
    return *this;
}
int main(){
    return 0;
}
//2. 单例模式
//考虑线程安全的话需要加同步锁等机制，加锁前后需要两步判断是否为null
class CSingleton
{
private:
    CSingleton()   //构造函数是私有的
    {
    }
    static CSingleton *m_pInstance;
public:
    static CSingleton * GetInstance()
    {
        if(m_pInstance == NULL)  //判断是否第一次调用
            m_pInstance = new CSingleton();
        return m_pInstance;
    }
};
//3.在二维数组中查找某个数字，每一行按照从左到右递增，每一列按照从上到下递增复杂度降为了o(n)
#include <iostream>
using namespace std;
bool Find(int* matrix, int rows, int columns, int number) {
    bool found = false;
    if (matrix != NULL && 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，很明显替换后的字符串会边长，涉及字符的移动问题
//能否开辟新的内存？还是保证原字符串后边的空间足够
//O(n^2)解法直接暴力，每次发现空格，替换然后后边的字符串整天向后移动2位
//O(n)
//首先统计空格数目，这样可以得到替换后的字符串的长度，本质在于减少同一段字符的多次重复移动，提前计算出总的移动次数
//然后从后往前替换，准备两个指针p1,p2 p1指向原串末尾，p2指向替换后的字符串末尾,不能从前向后，不然会覆盖后边的字符串
易错问题:
#include <iostream>
using namespace std;
int main(){
    char str1[] = "hello world";
    char str2[] = "hello world";
    char* str3 = "hello world";
    char* str4 = "hello world";
    cout << (str1 == str2) << endl; // 0
    cout << (str3 == str4) << endl; // 1
    //c++为了节省内存，会把常量字符串放到一个单独的区域
    return 0;
}
void ReplaceBlank(char string[], int length) {
    if (string == NULL && length <= 0) 
        return;
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0; 
    while (string[i] != '\0') {
        ++ originalLength;
        if (string[i] == ' ') 
            ++ numberOfBlank;
        ++ i;
    } 
    int newLength  = originalLength + numberOfBlank * 2;
    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) {
        if (string[indexOfOriginal] == ' ') {
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '%';
        } else {
            string[indexOfNew --] = string[indexOfOriginal];
        }
        -- indexOfOriginal;
    }
}
//5.从尾到头打印链表
struct ListNode{
    int key;
    ListNode* next;
};
//使用栈
void PrintListReversingly_Iteratively(ListNode* phead) {
    stack<ListNode*> nodes;
    ListNode* pNode = phead;
    while (pNode != NULL) {
        nodes.push(pNode);
        pNode = pNode -> next;
    }
    while (!node.empty()) {
        pNode = nodes.top();
        cout << pNode -> value << " ";
        nodes.pop();
    }
}
//系统栈
void PrintListReversingly_Iteratively(ListNode* phead) {
    if (phead != NULL) {
        PrintListReversingly_Iteratively(phead -> next);
        cout << phead -> value << " ";
    }
}
//6. 由前序遍历和中序遍历重建二叉树
struct BinaryTreeNode{
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};
BinaryTreeNode* Construct(int* preorder, int* inorder, int length) {
    if (preorder == NULL || inorder == NULL || length <= 0) return NULL;
    return ConstructCore(preorder, preorder+length-1,inorder, inorder+length-1);
}
BinaryTreeNode* ConstructCore(int* spre, int* epre, int* sin, int* ein) {
    int rootvalue = spre[0];
    BinaryTreeNode* root = new BinaryTreeNode();
    root -> value = rootvalue;
    root -> left = root -> right = NULL;
    if (spre == epre && sin == ein && *spre == *sin) return root;
    else throw exception("Invalid Input");
    int * rootInorder = sin;
    while (rootInorder <= ein && *rootInorder != rootvalue) 
        ++ rootInorder;
    if (rootInorder == ein && *rootInorder != rootvalue)
        throw exception("Invalid Input");
    int leftlength = rootInorder - sin;
    int * leftPreorderEnd = spre + leftlength;
    if (leftlength > 0)//左子树还有值存在
        root -> left = ConstructCore(spre+1, leftPreorderEnd, sin, rootInorder-1);
    if (leftlength < epre - spre) //右子树还有值存在
        root -> right = ConstructCore(leftPreorderEnd+1, epre, rootInorder+1, esin);
    return root;
}
//7.用两个栈实现队列操作
//添加元素总是添加到stack1中，每次都是从stack2的栈顶删除元素，当stack2为空时再将stack1中的元素转移到stack2中。
相关题目:用两个队列实现一个栈
//添加时先添加到有元素存在的队列中，当需要删除时将所有元素依次转移到空队列中，然后删除头部元素即可。
//8.旋转数组的最小数字
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
常见的方法是o(n)直接扫描一遍数组即可。
可以将之分解为两个有序数组的分界线的查找，可以借助二分查找实现o(logn)的时间复杂度。
int Min(int* numbers, int length) {
    if (number == NULL || length <= 0)
        throw new std:: exception("Invaild parameters");
    int index1 = 0;
    int index2 = length - 1;
    int indexMid;
    while (numbers[index1] >= numbers[index2]) {
        if (index2 - index1 == 1) { //临界条件 跳出二分查找
            indexMid = index2;
            break;
        }
        indexMid = (index1+index2)/2;
        if(numbers[indexMid] == numbers[index1] && numbers[index1] == numbers[index2])
            //特例情况，此时要执行顺序查找，无法确定中间的元素是属于哪段的序列
        if (numbers[indexMid] >= numbers[index1])
            index1 = indexMid;
        else if (numbers[indexMid] <= numbers[index2])
            index2 = indexMid;
    }
    return numbers[indexMid];
}
//.斐波那契数列
递推o(n) or 快速幂o(logn)
//斐波那契数列的应用~
一只青蛙一次可以跳上一级台阶，也可以跳上2级。求该青蛙跳上一个n级台阶移动有多少种跳法？f(n) = f(n-1) + f(n-2)
相关题目:
1. 可以跳1阶，可以跳2阶，可以跳n阶，此时跳上n阶台阶共有多少种跳法？可以用数学归纳法证明f(n) = 2^(n-1)
2. 用2*1的句型去覆盖2*8的矩形 f(8) = f(7) + f(6)
//10. 二进制中1的数目
int numberof1(int n) {
    int count = 0;
    while (n) {
        ++ count;
        n = (n-1) & n;
    }
    return count;
}将一个数字右移时要小心其是否为负数。
//11. 数值的整数次方
//注意指数为<=0的情况，并且0^(负数)的情况错误处理要有，通常通过设置全局变量g_InvaildInput来标识函数出错了。最后计算时o(logn)的时间复杂度来快速幂。
//12.打印1到最大的n位数
最大陷阱是这里n没有限制范围，可能超过Int
//模拟字符串加法
void print(int n) {
    if (n <= 0)
        return;
    char * number  = new char[n+1];
    memset(number, '0', n);
    number[n] = '\0';
    while(!increment(number)) { //加1并判断是否溢出
        printnumber(number);//忽略前导0的输出
    }
    delete [] number;
}
//递归版本
void print(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';
        printrecursively(number, n, 0);
    }
}
void printcursively(char * number, int length, int index) {
    if (index == length - 1){
        printnumber(number);//忽略前导0
        return;
    }
    for(int i = 0;i < 10; ++i) {
        number[index+1] = i + '0';
        printcursively(number, length, index+1);
    }
}
//13.O(1)时间删除链表节点
//14. 调整数组顺序使得奇数位于偶数之前
疑问?需不需要保持原有数组的顺序? 插入排序？ 快速排序的思路
判断时定义一个func()来判断是否排在前边还是后边，提高泛化能力
//15.链表中的倒数第k个结点
//16.反转链表
//17.合并两个有序链表
//18.树的子结构
bool HasSubTree(BinaryNode* root1, Binary* root2) {
    bool result = false;
    if (root1 != NULL && root2 != NULL) {
        if (root1 -> value == root2 -> value)
            result = DoesTree1HaveTree2(roo1, root2);
        if (!result)
            result = HasSubTree(root1 -> left, root2);
        if (!result)
            result = HasSubTree(root1 -> right, root2);
    }
}
bool DoesTree1HaveTree2(BinaryNode* root1, BinaryNode* root2) {
    if (root2 == NULL)
        return true;
    if (root1 == NULL)
        return false;
    if (root1 -> value != root2 -> value)
        return false;
    return DoesTree1HaveTree2(root1->left, root2->left) &&  DoesTree1HaveTree2(root1 -> right, root2 -> right);
}
//19. 二叉树的镜像
//20. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
void print(int ** numbers, int columns, int rows) {
    if (number == NULL || columns <= 0 || rows <= 0)
        return;
    int start = 0; //到时候看初始值是1还是0
    while (columns > start*2 && rows > start*2) {
        printMatrix(numbers, columns, rows, start);
        start ++;
    }
}
void printMatrix(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) { //至少有3行两列
        for (int i = endY -1; i >= start +1; --i) {
            int number = numbers[i][start];
            printNumber(number);
        }
    }
}
//21.包含min函数的栈
定义一个能到的栈的最小的元素的min函数，调用min、push以及pop的时间复杂度都是o(1)
仅仅保留当前最小的元素是不够的，因为当最小元素pop出去之后，我们还要能够得到次小的元素。维护一个最小元素栈，每个push数据时都将当前栈的最小元素push进最小栈，可能出现push多次的情况~
//22.栈的压入、弹出序列 -> 用一个辅助栈模拟运行过程
bool IsPopOrder(int * push, int * pop, int length) {
    bool is_possible = false;
    if (push != NULL && pop != NULL && length > 0) {
        int * nextpush = push;
        int * nextpop = pop;
        stack<int>stackdata;
        while (nextpop - pop < length) {
            while (stackdata.empty() || stackdata.top() != *nextpop) {
                if (nextpush - push == length) break;
                stackdata.push(*nextpush);
                nextpush++;
            }
            if (stackdata.top() != *nextpop)
                break;
            stackdata.pop();
            nextpop++;
        }
        if (stackdata.empty() && nextpop - pop == length)
            is_possible = true;
    }
    return is_possible;
}
//23.二叉树的层次遍历
//24. 二叉搜索树的后序遍历数列
bool Verify(int * sequence, int length) {
    if (sequence == NULL || 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 (sequcen[j] < root)
            return false;
    }
    bool left = true;
    if (i > 0) {
        left = Verify(sequence, i);
    }
    bool right = true;
    if (i < length - 1) {
        right = Verify(sequence + i, length - i - 1);
    }
    return left && right;
}
//25.二叉树中和为某一值的路径，(路径指的是到叶节点的才算~)
//26.复杂链表的复制
复杂链表，每个节点除了指向自身之外，还指向另外一个其他的节点。
一种思路利用哈希表~
首先复制一遍next指针，然后结合哈希表构造映射<N,N'>映射即可。
第二种思路直接把新的节点N'链接到N之后。然后再将N'的sibling指针进行复制~最后将两个链表拆开~
//27. 二叉搜索树转双向链表
//28. 字符串的排列
输出某些字符的全排列
void Permutation(char* pstr) {
    if (pstr == NULL)
        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;
            Permutaion(pstr, pbegin+1);
            char temp = *pch;
            *pch = *pbegin;
            *pbegin = temp;
        }
    }
}
相关问题:求所有字符的组合
把求n个字符串中长度为m的组合问题分解为两个子问题:分别求n-1个字符串中长度为m-1的组合，以及求n-1个字符的长度为m的组合。然后利用递归解决。(针对放不放这个字符)，递归边界是m==0
可以参考下刘汝佳算法设计中的实现方式。
\\29. 数组中出现次数超过一半的数字
一是基于partition函数的o(n)算法，目的在于找到第k大的数字，在这个问题中k=n/2
二是利用数组特点，超过数组一半的数字为a，其他为b，然后统计次数，相减~非常巧妙。
\\30. 最小的k个数
一是o(n)的算法，只有当我们可以修改输入的数组时可以使用
还是利用partition函数~ 找到第k大的数。
二是o(nlogk)的算法，特别适合海量数据的处理
利用最大堆(O(logk)完成删除及插入、o(1)得到最大值)，每次过来一个元素都删除一个最大的值，最后剩下的就是最小的k个数了。当然也可以利用红黑树(插入删除查找操作均为o(logk))。输出的集合中的元素是按字母大小顺序排列的。
#include <iostream>
using namespace std;
//调整以index为根的子树
//n：堆中元素个数
void MaxHeap(int a[],int index,int n){
    if(n < 2){
        return;
    }
    int largestIndex = index;
    // 左子节点下标
    int leftIndex = 2 * index;
    // 右子节点下标
    int rightIndex = 2 * index + 1;
    // 左子节点最大
    if(leftIndex <= n && a[leftIndex] > a[largestIndex]){
        largestIndex = leftIndex;
    }//if
    // 右子节点最大
    if(rightIndex <= n && a[rightIndex] > a[largestIndex]){
        largestIndex = rightIndex;
    }//if
    //如果a[index]是最大的，则以index为根的子树已是最大堆否则index的子节点有最大元素
    //则交换a[index],a[LargetIndex],从而使index及子女满足堆性质
    int temp;
    if(largestIndex != index){
        // 交换
        temp = a[largestIndex];
        a[largestIndex] = a[index];
        a[index] = temp;
        //重新调整以LargestIndex为根的子树
        MaxHeap(a,largestIndex,n);
    }//if
}
//建堆：将一个数组a[1-n]变成一个最大堆
void BuildMaxHeap(int a[],int n){
    //子数组a[(n/2+1,n/2+2......n)]中的元素都是树中的叶子不用调整
    for(int i = n/2;i >= 1;i--){
        // 调整以i为根节点的树使之成为最大堆
        MaxHeap(a,i,n);
    }
}
//堆排序
void HeapSort(int*& a,int n){
    int tmp;
    //数组中最大元素在根a[1]，则可以通过它与a[i]交换来达到最终的正确位置
    for(int i = n;i > 1;i--){
        // 交换
        tmp = a[i];
        a[i] = a[1];
        a[1] = tmp;
        //a[i]已达到正确位置，从堆中去掉
        n--;
        //重新调整
        MaxHeap(a,1,n);
    }
}
// 最小K个数
void MinK(int a[],int k,int n){
    for(int i = k+1;i <= n;i++){
        //如果X比堆顶元素Y大，则不需要改变原来的堆
        //如果X比堆顶元素Y小，那么用X替换堆顶元素Y，
        //在替换之后，X可能破坏了最大堆的结构，需要调整堆来维持堆的性质
        int temp;
        if(a[i] < a[1]){
            temp = a[i];
            a[i] = a[1];
            a[1] = temp;
            // 重新调整最大堆
            MaxHeap(a,1,k);
        }
    }
    // 堆排序
    HeapSort(a,k);
    // 输出
    for(int i = 1;i <= k;i++){
        cout<<a[i]<<endl;
    }
}
int main(){
    int k = 5;
    //a[0]不用，堆的根结点是从1开始的
    int a[] = {0,3,17,8,27,7,20,5,35,6};
    //BulidMaxHeap将输入数组构造一个最大堆
    BuildMaxHeap(a,k);
    // 最小k个元素
    MinK(a,k,9);
    return 0;
}
\\31. 最大连续子段和
\\32. 从1到n整数中1的出现次数
输入数字n，n有o(logn)位!
以21345为例，分成两段1~1345和1346~21345.其中1~1345采用递归求解，而对于1346~21345,首先最高位1可能出现在10000~19999中共10^4个，而对于其他位来说，将这20000个数切成两半，每一部分都有4*10^3个1出现(其中1位选择1，其他3位随便选)
\\33. 把数组排成最小的数
实际上是个排序问题，排序规则为a+b > b+a?
\\34. 丑数
和素数筛表法类似，但是这里在往后筛选之前需要先排序选出最小的。
#include<iostream>
#include<stdlib.h>
#include<cassert>
#include<time.h>
using namespace std;
//求M2，M3，M5的最小值
int Min(int number1,int number2,int number3)
{
    int min=(number1<number2)?number1:number2;
    return (min<number3)?min:number3;
}
//获取第k个丑数，假定1为第一个丑数
int getUglyNumber2(int index)
{
    //如果index<=0表明输入有误，直接返回0
    if(index<=0)
        return 0;
    //定义丑数数组，用于记录排序的丑数
    int *pUglyNumbers=new int[index];
    //第一个丑数为1
    pUglyNumbers[0]=1;
    //第一个丑数的坐标是0，下一个丑数的坐标从1开始
    int nextUglyIndex=1;
    //定义三个指向丑数数组的指针，用它们来标识从数组中的哪一个数开始计算M2，M3和M5，开始都是丑数数组的首地址。
    int *T2=pUglyNumbers;
    int *T3=pUglyNumbers;
    int *T5=pUglyNumbers;
    while(nextUglyIndex<index)//
    {
        int min=Min(*T2 * 2,*T3 * 3,*T5 * 5);//M2=*T2 * 2, M3=*T3 * 3, M5=*T5 * 5
        pUglyNumbers[nextUglyIndex]=min;//求M2，M3，M5的最小值作为新的丑数放入丑数数组
        //每次生成新的丑数的时候，去更新T2，T3和T5.
        while(*T2 * 2<=pUglyNumbers[nextUglyIndex])
            ++T2;
        while(*T3 * 3<=pUglyNumbers[nextUglyIndex])
            ++T3;
        while(*T5 * 5<=pUglyNumbers[nextUglyIndex])
            ++T5;
        nextUglyIndex++;
    }
    int ugly=pUglyNumbers[index-1];//因为丑数有序排列，所以丑数数组中的最后一个丑数就是我们所求的第index个丑数。
    delete[] pUglyNumbers;
    return ugly;
}
\\35. 第一次只出现一次的字符
利用哈希表实现~ 记得加空字符串的判断
\\36. 数组中的逆序对
利用归并排序~ 统计在最后归并的过程中发生，在两个子数组的末尾设置两个指针并进行统计即可。
\\37. 两个链表的第一个公共结点
\\38. 数字在有序数组中出现的次数
思路就是利用二分查找算法在排序数组中首先找到这个元素的第一个位置，然后再利用二分查找算法找到这个元素的末尾元素，然后位置相减即可。
\\39. 二叉树的深度
相关问题:判断是否为平衡二叉树,见数据结构二叉树节
\\40. 数组中只出现一次的数字
利用异或的性质，任何一个数字异或它自己都等于0.当问题扩展为数组中有2个只出现一次的元素时，得先想办法将这两个元素分到不同的子数组中去，再进行分别计算。如何进行？ 首先还是依次异或之后得到结果，将结果的某位为1的值作为判断标准将数组分为2组即可。
\\41. 寻找在有序数组中和为s的两个数字
设置首位指针根据与s大小比较的结果进行移动~
相关问题:输入一个s，打印出和为s的连续正数序列。解决思路也是设置两个指针，不过现在代表序列的首和末尾。
\\42. 翻转单词顺序
第一次翻转句子中的所有字符，第二次再逐个翻转每个单词中字符的顺序。这个不用翻转，直接从后往前读也是可以的。
相关题目:左旋转字符串
根据n的大小将字符串分为两个部分，先分别翻转这两个部分，然后再整体翻转字符串即可。先整体或者先部分翻转都是可以的。
\\43.n个骰子的点数
借助滚动数组，第n个骰子加入时和为n的次数等于第n-1个骰子和为n-1
\n-2\....\n-6的次数之和、类似于DP的思路
\\44. 扑克牌的顺子
判断是否为连续的数组，sort之后计算差距的总和=？大小王的个数，还要特殊处理重复扑克牌的出现情况
\\45. 圆圈中最后剩下的数字
约瑟夫环问题。
模拟的时候需要利用std::list模拟一个循环列表出来。
记一个结论:f(n,m) = (f(n-1,m) + m)%n ,n > 1 当n =1时 f(n, m) = 0
\\46. 求1+2+...n
利用模板或者构造函数完成递归或者迭代的过程
\\47. 不用加减乘除做加法
int Add(int num1, int num2) {
    int sum, carry;
    do {
        sum = num1 ^ sum2; //二进制加法
        carry = (num1 & num2) << 1;
        num1 = sum;
        num2 = carry;
    } while (num2 !=0);
    return num1;
}
\\48. 不能被继承的类
把构造函数设置为私有函数或者借助私有继承
\\49. 把字符串转化为整数 实现atoi函数
注意特殊情况的处理，如溢出、负数、空字符串、错误处理、非法字符处理、杂乱类型的字符串~ 见leetcode
\\50. 树中两个结点的最低公共祖先
主要是两种思路, 见数据结构二叉树节~