代码鲁棒性 (输入参数检查等) 贯穿所有代码当中，不会特别强调.

1赋值运算符函数

注意：

1. 返回值类型为该类型引用（链式赋值），返回*this

2. 传入参数常量引用

3. 释放自身已有空间

4. 判断是不是自身赋值

例：

[cpp] view plain copy
MyString& MyString::operator=( const MyString& 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;  
}

不足：若内存不足，new 申请内存时抛出异常，则 m_pData 已经被 delete，此时其为一个空指针，非常容易导致程序奔溃。在赋值运算符函数内部抛异常，CMyString 实例不再保持有效的状态，违背异常安全性原则.

改进:1. 先 new 再 delete 2. 创建临时实例，交换临时实例和原来的实例：

[cpp] view plain copy
MyString& MyString::operator=( const MyString& str ){  
    if ( &str != this ){  
        MyString strTemp( str );  
  
        char* pTemp = strTemp.m_pData;  
        strTemp.m_pData = m_pData;  
        m_pData = pTemp;  
    }  
  
    return *this;  
}

3. 二维数组中的查找：二维数组，每一行，从左到右递增。每一列，从上到下递增。输入一个二维数组和一个整数，判断数组中是否含有该整数

思路：选取数组右上角数字，等于->结束。大于->剔除这一列。小于->剔除这一行。这样每比较一次剔除一列或一行，缩小范围，直到找到要查找的数字 or 查找范围为空

例：

[cpp] view plain copy
bool Find( int* matrix, int rows, int cols, int number ){  
    bool found = false;  
  
    if ( NULL != matrix && rows > 0 && cols > 0 ){  
        int row = 0;  
        int col = cols - 1;  
  
        while ( row = 0 ){  
            if ( number == matrix[row * cols + col] ){  
                found = true;  
                return found;  
            }  
            else if ( matrix[row * cols + col] > number )  
                --col;  
            else  
                ++row;  
        }  
    }  
  
    return found;  
}

二维数组在内存中占据连续的空间。在内存中从上到下存储各行元素，每行从左到右顺序存储

4. 替换空格

1. 在原串上操作 --> 保证原串后面有足够的空间 --> 从后往前替换

2.开辟新空间 --> 直接替换

两种思路都需遍历原串一次获取空格个数 --> O(N)

相关题目:两个排序数组 A1，A2。A1 后有足够空间容纳 A2，将 A2 中数字插入 A1 中使所有数字依旧有序

思路：遍历两个数组各一次得到两数组长度，三个指针，一个指针指向 lengthA1+lengthA2-1，其余两个分别指向 A1 与 A2 末尾。依次比较，将合适数字放到第一个指针所指位置

合并两个数组 (字符串) 时，如果从前往后赋值每个数字 or 字符需要重复移动数字 or 字符多次 --> 从后往前复制，减少移动次数，提高效率

5. 从尾到头打印链表

1. 栈

2. 递归

7. 用两个栈实现队列

思路：栈 S1 和 S2，入「队列」入栈 S1。出「队列」，若 S2 有元素 S2.pop( )，否则，将 S1 中元素压入栈 S2

相关题目：

1. 求链表中间结点

思路：两个指针，p1，p2。p1 一次走一步，p2 一次走两步。当 p2 指向链表最后一个结点时，p1 正好指向链表中间节点

2. 判断链表是否带环

思路：快慢指针，相遇->带环。快指针到链表尾->不带环

当我们用一个指针遍历链表不能解决问题时，可以尝试两个指针来遍历链表。可以让其中一个指针走的快些 (如一次走两步)，或者让它先在链表上走若干步

16. 反转链表

:

[cpp] view plain copy
ListNode* ReverseList( ListNode* pHead )     
{    
    // 链表为空和链表只有一个结点在这个语句进行处理  
    if (NULL == pHead || NULL == pHead->next)    
        return pHead;    
        
    ListNode* pPrev = NULL;    
    ListNode* pCur = pHead;    
    ListNode* pReverseHead = NULL;    
            
    while (NULL != pCur){    
        ListNode* pNext = pCur->next;    
  
        if (NULL == pNext)  
            pReverseHead = pCur;  
  
        pCur->next = pPrev;  
  
        pPrev = pCur;    
        pCur = pNext;    
    }    
        
    return pReverseHead;    
}

17. 合并两个排序的链表

：

[cpp] view plain copy
ListNode* Merge( ListNode* pHead1, ListNoe* pHead2 )  {    
    if (NULL == pHead1)    
        return pHead2;    
    else if (NULL == pHead2)    
        return pHead1;    
    
    ListNode* pMergedHead = NULL;    
    
    if (pHead1->val val){    
        pMergeHead = pHead1;    
        pMergeHead->next = Merge( pHead1->next, pHead2 );    
    }    
    else{    
        pMergeHead = pHead2;    
        pMergeHead->next = Merge( pHead1, pHead2->next );    
    }    
    
    return pMergedHead;    
}

21. 包含 min 函数的栈定义一个可以使 min, push, pop 都为 O(1) 的栈

思路：借用辅助栈，每次数据栈元素入栈时，将所有入栈元素中最小值入辅助栈 (保证辅助栈和数据栈->同入同出)

：

[cpp] view plain copy
void Push( const int& data ){    
      dataS.push( data );    
  
if (0 == minS.size( ) || data     minS.push( data );  
else  
    minS.push( minS.top( ) );  
  }    
  
  void Pop( ){  
assert( dataS.size( ) > 0 && minS.size( ) > 0 );  
  
dataS.pop( );  
minS.pop( );  
  }    
  
  const T& Min( ) const {  
assert( dataS.size( ) > 0 && minS.size( ) > 0 );  
  
return minS.top( );  
  }

23. 从上往下打印二叉树 (层序遍历二叉树)

借助队列

：

[cpp] view plain copy
void LevelPrint( Node* pRoot ){    
    if (NULL == pRtoot)    
        return;  
    
    queue queueNode;    
    queueNode.push( pRoot );    
    
    while (0 != queueNode.size( ))  {    
        Node* pNode = queueNode.front( );    
        queueNode.pop( );  
    
        Visit( pNode );    
    
        if (NULL != pNode->pLeft)    
            queueNode.push(pNode->pLeft);    
    
        if (NULL != pNode->pRight)    
            queueNode.push(pNode->pRight);    
    }    
}

29. 数组中出现次数超过一半的数字

思路：如果有一个数字出现次数超过数组元素总个数的一半，则它出现次数比其他数字出现的次数总和还要多。

:

[cpp] view plain copy
bool g_inputInvalid = false;  
  
  
bool CheckInvalidArr( int* arr, int len ){  
    g_inputInvalid = false;  
  
    if (NULL == arr || len         g_inputInvalid = true;  
  
    return g_inputInvalid;  
}  
  
  
bool CheckMoreThanHalf( int* arr, int len, int number ){  
    int times = 0;  
  
    for (int i = 0; i         if (number == arr[i])  
            ++times;  
  
    bool isMoreThanHalf = true;  
    if (times * 2         g_inputInvalid = true;  
        isMoreThanHalf = false;  
    }  
  
    return isMoreThanHalf;  
}  
  
  
int MoreThanHalfNum( int* arr, int len ){  
    // 如果只返回0存在二义性，是无效参数返回0还是0出现次数超过一半呢？  
    // 定义一个函数 和 一个全局变量，即可区分这两种情况  
    if (CheckInvalidArray( arr, len ))  
        return 0;  
  
    int result = arr[0];  
    int times = 1;  
  
    for (int i = 1; i         if (0 == times){  
            result = arr[i];  
            times = 1;  
        }  
        else if (result == arr[i])  
            ++times;  
        else  
            --times;  
    }  
      
    // 此时result中保存的数字并不一定是数组中出现次数超过数组长度一半的数字，需要验证  
    // 11234  
    if (!CheckMoreThanHalf( arr, len, result ))  
        result = 0;  
  
    return result;  
}

37. 两个链表的第一个公共结点

思路：

1. 借助栈，两个链表都从后往前遍历，直到找到最后一个相同结点

2. 遍历两个链表一次，得到链表长度，len1，len2。假设 len1 为 5，len2 为 4。则在链表 1 上先走 (len1 - len2) 步，接着同时开始走，第一个相同节点

38. 数字在排序数组中出现的次数

思路：

因为是排序数组，找到第一个 k 和最后一个 k 即可知道 k 出现的次数 O(log n) 二分

：

[cpp] view plain copy
int GetFirstK( int* arr, int len, int k, int start, int end ){  
    // 这段区间内没找到k， 返回-1  
    if (start > end)  
        return -1;  
  
    int midIndex = (start + end) / 2;  
    int midData = arr[midIndex];  
  
    if (k == midData){  
        if ((midIndex > 0 && k != arr[midIndex - 1])  
            || 0 == midIndex)  
            return midIndex;  
        else  
            end = midIndex - 1;  
    }  
    else if (midData > k)  
        end = midIndex - 1;  
    else  
        start = midIndex + 1;  
  
    return GetFirstK( arr, len, k, start, end );  
}  
  
  
int GetLastK( int* arr, int len, int k, int start, int end ){  
    if (start > end)  
        return -1;  
  
    int midIndex = (start + end) / 2;  
    int midData = arr[midIndex];  
  
    if (k == midData){  
        if ((midIndex             || len - 1 == midIndex)  
            return midIndex;  
        else  
            start = midIndex + 1;  
    }  
    else if (midData > k)  
        end = midIndex - 1;  
    else  
        start = midIndex + 1;  
  
    return GetLastK( arr, len, k, start, end );  
}  
  
  
int GetTimesOfK( int* arr, int len, int k ){  
    int times = 0;  
  
    if (NULL != arr && len > 0 ){  
        int first = GetFirstK( arr, len, k, 0, len - 1 );  
        int last = GetLastK( arr, len, k, 0, len - 1 );  
  
        if (first > -1 && last > -1)  
            times = last - first + 1;  
    }  
  
    return times;  
}

39. 二叉树的深度

:

[cpp] view plain copy
int TreeDepth( BinaryTreeNode* pRoot ){  
    if (NULL == pRoot)  
        return 0;  
       
    int depthLeft = TreeDepth( pRoot->left );  
    int depthRight = TreeDepth( pRoot->right );  
  
    return (depthleft > depthRight) ? (depthLeft + 1) : (depthRight + 1);  
}

相关题目：判断一棵树是不是平衡二叉树。左右子树的深度相差不超过 1.

1. 需要重复遍历多次的解法

：

[cpp] view plain copy
bool IsBalanced( BinaryTreeNode* pRoot ){  
    if (NULL == pRoot)  
        return true;  
       
    int depthLeft = TreeDepth( pRoot->left );  
    int depthRight = TreeDepth( pRoot->right );  
    int diff = left - right;  
  
    if (diff > 1 || diff         return false;  
  
    return IsBalanced( pRoot->left ) && IsBalanced( pRoot->right );  
}

后序遍历，每个节点只遍历一次

：

[cpp] view plain copy
bool IsBalanced( BinaryTreeNode* pRoot, int* pDepth ){  
    if (NULL == pRoot){  
        *pDepth = 0;  
        return true;  
    }  
  
    int left;  
    int right;  
  
    if (IsBalanced( pRoot->left, &left ) && IsBalanced( pRoot->tight, &right )){  
        int diff = left - right;  
        if (diff >= -1 && diff             *pDepth = left > right ? (left + 1) : (right + 1);  
            return true;  
        }  
    }  
  
    return false;  
}  
  
  
bool IsBlanced( BinaryTreeNode* pRoot ){  
    int depth = 0;  
      
    return IsBlanced( pRoot, &depth );  
}

42. 翻转单词顺序 vs 左旋转字符串

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。标点符号和普通字母一样处理。--> "I am a student." 变为 "student. a am I"

思路：

1. 翻转句子中所有的字符。此时不但翻转了句子中单词的顺序，连单词内的字符的顺序也翻转了

2. 翻转每个单词中字符的顺序

：

[cpp] view plain copy
void Reverse( char* pBegin, char* pEnd ){  
    if (NULL == pBegin || NULL == pEnd)  
        return;  
  
    while (pBegin         char temp = *pBegin;  
        *pBegin = *pEnd;  
        *pEnd = temp;  
  
        ++pBegin;  
        --pEnd;  
    }  
}  
  
  
char* ReverseSentence( char* pData ){  
    if (NULL == pData)  
        return NULL;  
  
    char* pBegin = pData;  
    char* pEnd = pData;  
  
    while ('

ITPub博客

面试->代码剑指offer（一）

最新文章

ITPub博客

面试->代码 剑指offer（一）

最新文章

面试->代码剑指offer（一）