复习C++

今天复习了一下C++。很久很久不碰这门语言，早上看到一段代码竟然感觉十分陌生。this，const pointer，引用之类的，有点忘了。其实也不是忘，就是感觉很陌生。比如this别的语言里面也有，只是不是指针，比较容易混淆。所以就大概查了一下C++ Primer，然后做了几道题目。放在这里。

题目一

给CMyString类写一个方法，使它能够支持赋值=操作。CMyString类已经给出。

#include <bits/stdc++.h>

// implement a operator `=` on class CMyString

using namespace std;

class CMyString {
public:
  CMyString(char * pData = NULL);
  CMyString(const CMyString & str);
  CMyString & operator =(const CMyString &);
  void print();
  ~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;

  if (this != &str) {
    CMyString strTemp(str);

    char * pTemp = strTemp.m_pData; // I wrote str.m_pData before. Stupid!
    strTemp.m_pData = m_pData;
    m_pData = pTemp;
  }
  return *this;
}

CMyString::CMyString(char * pData)
{
  m_pData = NULL;
  m_pData = new char[strlen(pData) + 1];
  strcpy(m_pData, pData);
}

CMyString::CMyString(const CMyString & str)
{
  cout << "copying " << str.m_pData << "\n";
  m_pData = NULL;
  m_pData = new char[strlen(str.m_pData) + 1];
  strcpy(m_pData, str.m_pData);
  cout << "end of copying: " << m_pData << "\n";
  if (m_pData != str.m_pData) cout << "not equal" << "\n";
}

CMyString::~CMyString()
{
  cout << "delete: " << m_pData << "\n";
  delete [] m_pData;
}

void CMyString::print()
{
  cout << m_pData << "\n";
}

int main(int argc, char *argv[])
{
  CMyString str((char*)"Rabbit"), str4((char*)"Hola!"), str1((char*)"Slackware");
  str4 = str;

  str.print();
  str4.print();

  str = str4 = str1;
  str1.print();

  cout << "end of program" << "\n";

  return 0;
}

题目二

给一个二维数组，这个二维数组从左到右、从上到下依次按照从小到大的顺序排列。给一个数字，在这个数组里面找这个数字，如果找到，返回true。否则返回false

解法

当然你可以把整个二维数组扫描一遍。然而有更好的方法：起点从右上角或者左下角开始，如果num比当前位置的数字小，说明num不在这一列，j--，这样就可以找到num所在的列。如果num比当前数字大，说明num不在这一行，i++，这样就可以确定num所在的行。

// 2017/03/06 16:22:14

#include <bits/stdc++.h>

using namespace std;

// find a number in a sorted two-dimension array.
// the array is from left to right, top to bottom sorted.
bool findNumber(int *a, int row, int col, int num)
{
  if (NULL == a) return false;

  int j = col - 1, i = 0;
  if (col > 0 && row > 0) {
    // find the max column
    while (j >= 0 && a[i * col + j] > num) {
      j--;
    }
    if (j < 0) {
      return false;
    }

    // find the max row
    while (i < row && a[i * col + j] < num) {
      i++;
    }
    if (i == row) {
      return false;
    }

    return a[i * col + j] == num;
  }

  return false;
}

int main(int argc, char *argv[])
{
  int a[4][4] = {
    {1, 2, 8, 9},
    {2, 4, 9, 12},
    {4, 7, 10, 13},
    {6, 8, 11, 15}
  };

  cout << findNumber(&a[0][0], 4, 4, 7) << "\n"; // found
  cout << findNumber(&a[0][0], 4, 4, 1) << "\n"; // found
  cout << findNumber(&a[0][0], 4, 4, 15) << "\n"; // found

  cout << findNumber(&a[0][0], 4, 4, 3) << "\n"; // no
  cout << findNumber(&a[0][0], 4, 4, 16) << "\n";
  cout << findNumber(&a[0][0], 4, 4, -1) << "\n";

  cout << findNumber(NULL, 4, 4, 7) << "\n"; // no

  return 0;
}

题目三

给定一个字符串，把字符串里面的所有空格替换成%20。题目要求对字符串进行本地修改，保证字符串指向的连续内存有足够的空间。

解法

当然可以从前往后找空格，找到一个就把后面内容向后移动，然后把空格替换成%20。然而有更好的方法。从后往前替换。首先扫描一遍字符串，找到有cnt个空格。说明替换后的字符串长度是len + cnt * 2。所以从后往前一个一个替换就好了。需要注意的一个细节是：倒数第一个空格之后的内容需要向后移动cnt * 2个单位长度，倒数第二个空格之后的内容需要往后移动(cnt - 1) * 2个单位长度。

// 2017/03/06 16:23:21

#include <bits/stdc++.h>

using namespace std;

// replace all of the white spaces in a string to `%20`
// O(n)
void replaceSpace(char str[], int length)
{
  // IMPORTANT!!!
  if (NULL == str || length <= 0) {
    return;
  }

  // count the number of white spaces
  int cnt = 0;
  int strLen = 0;
  for (int i = 0; str[i] != '\0'; i++) {
    if (str[i] == ' ') {
      cnt++;
    }
    strLen++;
  }

  if (length <= strLen + cnt * 2) {
    return;
  }

  // replace from the tail of the string
  int pos = strLen;
  while (cnt > 0 && pos >= 0) {
    while (pos >= 0 && ' ' != str[pos]) {
      str[pos + cnt * 2] = str[pos];
      pos--;
    }
    if (pos >= 0 && ' ' == str[pos]) {
      str[pos + (cnt - 1) * 2] = '%';
      str[pos + (cnt - 1) * 2 + 1] = '2';
      str[pos + (cnt - 1) * 2 + 2] = '0';
    }
    cnt--;
    pos--;
  }
}

int main(int argc, char *argv[])
{
  char str[100] = "we are happy."; // simple case
  replaceSpace(str, 100);
  cout << str << "\n";

  char str1[100] = "we are happy. "; // one tail space
  replaceSpace(str1, 100);
  cout << str1 << "\n";

  char str2[100] = " we are happy. "; // head and tail space
  replaceSpace(str2, 100);
  cout << str2 << "\n";

  char str3[100] = "  we are happy. "; // two head spaces
  replaceSpace(str3, 100);
  cout << str3 << "\n";

  char str4[100] = "we are happy.  "; // two tail spaces
  replaceSpace(str4, 100);
  cout << str4 << "\n";

  char str5[100] = "wearehappy."; // no space
  replaceSpace(str5, 100);
  cout << str5 << "\n";

  char str6[100] = "   "; // only some spaces
  replaceSpace(str6, 100);
  cout << str6 << "\n";

  char str7[100] = " "; // only one space
  replaceSpace(str7, 100);
  cout << str7 << "\n";

  char str8[100] = ""; // empty string
  replaceSpace(str8, 100);
  cout << str8 << "\n";

  char *str9 = NULL; // NULL pointer
  replaceSpace(str9, 100);
  cout << str9 << "\n";

  return 0;
}

题目四

给一个单向链表，要求倒序打印出链表的内容。

解法

比较简单。可以递归打印，也可以把每个节点的值放到栈里面。最好打印栈里面的内容。需要注意的是，第二个方法比较好。原因是递归容易造成Stackoverflow，当链表非常长的时候。

// 2017/03/06 19:31:00

#include <bits/stdc++.h>

// print all of the nodes in the list in reverse order

using namespace std;

struct ListNode
{
  int m_nKey;
  ListNode *m_pNext;
};

// add a node to the tail
void AddToTail(ListNode **pHead, int value)
{
  ListNode *pNew = new ListNode();
  pNew->m_nKey = value;
  pNew->m_pNext = NULL;

  if (NULL == *pHead) {
    *pHead = pNew;
  }
  else {
    ListNode *next = *pHead;
    while (NULL != next->m_pNext) {
      next = next->m_pNext;
    }
    next->m_pNext = pNew;
  }
}

// print list nodes in reverse order
// NOTE: very long list will cause stack overflow!
void PrintReverse(ListNode *pHead)
{
  if (NULL == pHead) return;

  // print cdr, then print the current node
  if (NULL != pHead->m_pNext) {
    PrintReverse(pHead->m_pNext);
  }
  cout << pHead->m_nKey << " ";
}

void PrintReverse_Iterate(ListNode *pHead)
{
  if (NULL == pHead) return;
  stack<int> values;
  while (NULL != pHead) {
    values.push(pHead->m_nKey);
    pHead = pHead->m_pNext;
  }

  while (!values.empty()) {
    cout << values.top() << " ";
    values.pop();
  }
  cout << "\n";
}

int main(int argc, char *argv[])
{
  ListNode *head = NULL;
  AddToTail(&head, 3);
  AddToTail(&head, 1);
  AddToTail(&head, 10);
  AddToTail(&head, 9);
  AddToTail(&head, -1);

  PrintReverse(head);
  cout << "\n";

  PrintReverse_Iterate(head);

  ListNode *head1 = NULL;
  AddToTail(&head1, 10000);
  PrintReverse_Iterate(head1);
  PrintReverse(head1);
  cout << "\n";

  PrintReverse_Iterate(NULL);
  PrintReverse(NULL);

  return 0;
}

题目五

给定一个二叉树的前序遍历序列和中序遍历序列，构造出这个二叉树。

解法

这题早就见过，不过还是第一次写。其实也挺简单，就是首先在preorder里面找到根，然后在inorder序列里找到这个根的位置。那么在inorder里的根之前的都是左子树，右边的都是右子树。这样我们就有了左右子树的inorder序列。我们也在inorder里面得到了左子树的长度，那么在preorder里面根后面截取相同的长度，就是左子树的preorder序列，剩下的就是右子树的preorder序列。这样，我们就根据当前树的preorder序列和inorder序列得到了左右子树的preorder和inorder序列。所以这是一个递归的做法。

另外，实现的时候，不要傻傻的复制preorder和inorder这两个数组（我一开始就这么想的T_T）。可以用指针，传对应位置的指针当作子数组就可以了。

// 2016/03/06 20:10:41

#include <bits/stdc++.h>

using namespace std;


struct BinaryTreeNode
{
  int m_nValue;
  BinaryTreeNode *m_pLeft;
  BinaryTreeNode *m_pRight;
};


BinaryTreeNode * ConstructCore(int * startPreorder, int * endPreorder,
                               int * startInorder, int * endInorder)
{
  if (startPreorder > endPreorder ||
      startInorder > endInorder) {
    return NULL;
  }

  int rootValue = startPreorder[0];
  int leftNodesLen = 0;
  int *current = startInorder;

  BinaryTreeNode * root = new BinaryTreeNode();
  root->m_nValue = rootValue;
  root->m_pLeft = root->m_pRight = NULL;

  // only one element in the array
  if (startPreorder == endPreorder) {
    if (startInorder == endInorder &&
        *startPreorder == *startInorder) {
      return root;
    }
    else {
      throw exception();
    }
  }

  while(current != endInorder && *current != rootValue) {
    current++;
    leftNodesLen++;
  }

  // didn't find root value in the inorder array
  if (current == endInorder &&
      *current != rootValue) {
    throw exception();
  }

  // left child
  root->m_pLeft = ConstructCore(startPreorder + 1, startPreorder + leftNodesLen,
                                startInorder, startInorder + leftNodesLen - 1);

  // right child
  root->m_pRight = ConstructCore(startPreorder + leftNodesLen + 1, endPreorder,
                                 startInorder + leftNodesLen + 1, endInorder);

  return root;
}


// construct a binary tree using preorder and inorder
BinaryTreeNode * Construct(int * preorder, int * inorder, int len)
{
  if (NULL == preorder || NULL == inorder || 0 >= len) return NULL;

  return ConstructCore(preorder, preorder + len - 1,
                       inorder, inorder + len - 1);
}


void PreorderPrintTree(BinaryTreeNode * root)
{
  if (NULL == root) {
    return;
  }
  cout << root->m_nValue << " ";
  PreorderPrintTree(root->m_pLeft);
  PreorderPrintTree(root->m_pRight);
}


int main(int argc, char *argv[])
{
  int preorder[8] = { 1, 2, 4, 7, 3, 5, 6, 8 };
  int inorder[8] = { 4, 7, 2, 1, 5, 3, 8, 6 };

  int T = 0;

  cout << "Case " << T++ << "\n";
  BinaryTreeNode *root = Construct(preorder, inorder, 8);
  PreorderPrintTree(root);
  cout << "\n";

  cout << "Case " << T++ << "\n";
  int preorder1[7] = {1, 2, 4, 5, 3, 6, 7}; // complete binary tree
  int inorder1[7] = {4, 2, 5, 1, 6, 3, 7};
  BinaryTreeNode *root1 = Construct(preorder1, inorder1, 7);
  PreorderPrintTree(root1);
  cout << "\n";

  cout << "Case " << T++ << "\n";
  int preorder2[5] = {1, 2, 4, 5, 3}; // incomplete binary tree
  int inorder2[5] = {4, 2, 5, 1, 3};
  BinaryTreeNode *root2 = Construct(preorder2, inorder2, 5);
  PreorderPrintTree(root2);
  cout << "\n";

  // only have left children
  cout << "Case " << T++ << "\n";
  int preorder3[3] = {1, 2, 4};
  int inorder3[3] = {4, 2, 1};
  BinaryTreeNode *root3 = Construct(preorder3, inorder3, 3);
  PreorderPrintTree(root3);
  cout << "\n";

  // only have right children
  cout << "Case " << T++ << "\n";
  int preorder4[3] = {1, 3, 7};
  int inorder4[3] = {1, 3, 7};
  BinaryTreeNode *root4 = Construct(preorder4, inorder4, 3);
  PreorderPrintTree(root4);
  cout << "\n";

  // only root node
  cout << "Case " << T++ << "\n";
  int preorder5[1] = {1};
  int inorder5[1] = {1};
  BinaryTreeNode *root5 = Construct(preorder5, inorder5, 1);
  PreorderPrintTree(root5);
  cout << "\n";

  // empty tree
  cout << "Case " << T++ << "\n";
  int preorder6[0] = {};
  int inorder6[0] = {};
  BinaryTreeNode *root6 = Construct(preorder6, inorder6, 0);
  PreorderPrintTree(root6);
  cout << "\n";

  // invalid input
  cout << "Case " << T++ << "\n";
  int preorder7[3] = {1, 2, 3};
  int inorder7[3] = {2, 1, 4};
  BinaryTreeNode *root7 = Construct(preorder7, inorder7, 3);
  PreorderPrintTree(root7);
  cout << "\n";

  return 0;
}

做了几道题目，大概又熟悉一些了吧。指针操作什么的。捡起来也挺容易。不过，有时间还是要研究一下C++的高级语法。

不太懂，同样的语法为什么短程序块就有代码高亮，长一点的就没有。不管了。就这样吧。