Algorithm : 做一个 leetcode 的算法题
///////////////////////////////////////////////////////////////////
// 1. 与替换空格类似的题目
// 有两个排序数组A1, A2, A1的末尾有足够多的的空间容纳A2,实现一个函数,把A2中所有数字插入A1中且所有的数字的有序的!
//方法一:从前往后比较,需要额外的空间 //时间复杂度O(2n), 空间复杂度O(n) void MergeTwoArray1(int aiArrayA[], int iNumA, int aiArrayB[], int iNumB) { const int MAX_ARRAY_COUNT = iNumA + iNumB; vector<int> vect(MAX_ARRAY_COUNT, 0); int i = 0, j = 0, k = 0; // 1. 比较两个数组,把较小的加入新的数组 while (i < iNumA &&j < iNumB) { if (aiArrayA[i] < aiArrayB[j]) { vect[k++] = aiArrayA[i++]; } else { vect[k++] = aiArrayB[j++]; } } // 2.把剩余的元素加到新数组 while (i < iNumA) { vect[k++] = aiArrayA[i++]; } while (j < iNumB) { vect[k++] = aiArrayB[j++]; } // 3.把数据复制到数组A k = 0; for (auto it : vect) { aiArrayA[k++] = it; } }
// 方法二:从后往前比较,不需要额外的空间 //时间复杂度O(n), 空间复杂度O(1) void MergeTwoArray2(int aiArrayA[], int iNumA, int aiArrayB[], int iNumB) { int iNewNum = iNumA + iNumB - 1; int i = iNumA - 1; int j = iNumB - 1; // 从数组后往前比较,就不存在重叠的情况了!!! while (i >= 0 && j >= 0) { if (aiArrayA[i] > aiArrayB[j]) { aiArrayA[iNewNum--] = aiArrayA[i--]; } else { aiArrayA[iNewNum--] = aiArrayB[j--]; } } while (i >= 0) { aiArrayA[iNewNum--] = aiArrayA[i--]; } while (j >= 0) { aiArrayA[iNewNum--] = aiArrayB[j--]; } }
//////////////////////////////////////////////////////////////////////////////////////////////
// 2.题目五:从尾到头打印链表
// 方法一:时间复杂度O(n),空间复杂度O(n) template <typename TYPE> void ReversePrintList1(ListNode<TYPE>* pNode) { assert(NULL != pNode); stack<ListNode<TYPE>*> stStack; while (pNode) { stStack.push(pNode); pNode = pNode->m_pNextNode; } cout << "链表逆序打印: " << endl; while (!stStack.empty()) { ListNode<TYPE>* pTmpNode = stStack.top(); printf("%02d -> ", pTmpNode->m_stData); stStack.pop(); } putchar(10); }
// 方法二:递归实现(递归实现也是类似栈实现) // 时间复杂度O(n), 空间复杂度O(n) // 注意:如果链表非常长,会导致函数调用层级很深,从而导致函数调用栈溢出!!! template <typename TYPE> void ReversePrintLisHEAP_TYPE(ListNode<TYPE>* pNode) { if (!pNode) { return; } ReversePrintLisHEAP_TYPE(pNode->m_pNextNode); printf("%02d -> ", pNode->m_stData); }
///////////////////////////////////////////////////////////////////////////////////////
// // 3.题目六:重建二叉树
// 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出改二叉树
struct BinaryTreeNode { int m_iValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; BinaryTreeNode(int iValue = 0, BinaryTreeNode* pLeft = NULL, BinaryTreeNode* pRight = NULL) :m_iValue(iValue), m_pLeft(pLeft), m_pRight(pRight) { } }; BinaryTreeNode* RebuildTree(int* pPreStart, int* pPreEnd, int* pInStart, int* pInEnd) { if (pPreStart > pPreEnd || pInStart > pInEnd) { return NULL; } // 1.建立根节点(前序遍历第一个元素) BinaryTreeNode* pRoot = new BinaryTreeNode(*pPreStart); if (!pRoot) { return NULL; } // 2.找到中序根节点 int* p = pInStart; while (p <= pInEnd && *p != pRoot->m_iValue) { p++; } int iLeftLength = p - pInStart; int* pLeftPreEnd = pPreStart + iLeftLength; // 3.构建左子树 if (iLeftLength > 0) { pRoot->m_pLeft = RebuildTree(pPreStart + 1, pLeftPreEnd, pInStart, p - 1); } // 4.构建右子树 if (iLeftLength < (pPreEnd - pPreStart)) { pRoot->m_pRight = RebuildTree(pLeftPreEnd + 1, pPreEnd, p + 1, pInEnd); } return pRoot; } BinaryTreeNode* RebuildBinaryTree(int* piPreOrderArray, int* piInorderArray, int iLength) { if (NULL == piPreOrderArray || NULL == piInorderArray || iLength <= 0) { return NULL; } return RebuildTree(piPreOrderArray, piPreOrderArray + iLength - 1, piInorderArray, piInorderArray + iLength -1); } void DestroyTree(BinaryTreeNode* pTree) { if (pTree) { // 释放左子树 DestroyTree(pTree->m_pLeft); // 释放右子树 DestroyTree(pTree->m_pRight); delete pTree; pTree = NULL; } } // 后序遍历 void PostTraversal(BinaryTreeNode* pNode) { if (pNode) { PostTraversal(pNode->m_pLeft); PostTraversal(pNode->m_pRight); printf("%02d -> ", pNode->m_iValue); } } void RebuildBinaryTreeTestFunc() { cout << "\n\n --------------- RebuildBinaryTreeTestFunc Start -------------->" << endl; const int MAX_TREE_NODE_COUNT = 8; //前序遍历序列(中 -> 左 -> 右) int aiPreOrderArray[MAX_TREE_NODE_COUNT] = {1, 2, 4, 7, 3, 5, 6, 8}; //中序遍历序列(左 -> 中 -> 右) int aiInorderArray[MAX_TREE_NODE_COUNT] = {4, 7, 2, 1, 5, 3, 8, 6}; //后序遍历序列(左 -> 右 -> 中) int aiPostArray[MAX_TREE_NODE_COUNT] = {7, 4, 2, 5, 8, 6, 3, 1}; BinaryTreeNode* pTree1 = RebuildBinaryTree(aiPreOrderArray, aiInorderArray, MAX_TREE_NODE_COUNT); if (pTree1) { // 后序遍历 PostTraversal(pTree1); putchar(10); // 施法资源 DestroyTree(pTree1); } cout << "\n\n --------------- RebuildBinaryTreeTestFunc End -------------->" << endl; }
////////////////////////////////////////////////////////////////////////////////////
// 4.题目七:用两个栈实现队列
// 题目:用两个栈实现一个队列,队列的声明如下:
template <typename TYPE> class CQueue { public: CQueue(){} ~CQueue(){} void AppendTail(const TYPE& node); TYPE DeleteHead(); private: stack<TYPE> m_stPushStack; stack<TYPE> m_stPopStack; }; // 方法一: // 插入时 --> m_stPopStack不为空,将元素压入m_stPushStack; // 删除时 --> m_stPushStack不为空,将元素压入 m_stPopStack; // 方法二: // 插入时 --> 直接往 m_stPushStack 插入新元素 // 删除时 --> 如果m_stPopStack为空,插入m_stPushStack中元素,否则直接弹出元素 template <typename TYPE> TYPE CQueue<TYPE>::DeleteHead() { #if 0 while (!m_stPushStack.empty()) { m_stPopStack.push(m_stPushStack.top()); m_stPushStack.pop(); } #else if (m_stPopStack.empty()) { while (!m_stPushStack.empty()) { m_stPopStack.push(m_stPushStack.top()); m_stPushStack.pop(); } } #endif TYPE tmp = m_stPopStack.top(); m_stPopStack.pop(); return tmp; } template <typename TYPE> void CQueue<TYPE>::AppendTail(const TYPE& node) { #if 0 while (!m_stPopStack.empty()) { m_stPushStack.push(m_stPopStack.top()); m_stPopStack.pop(); } m_stPushStack.push(node); #else m_stPushStack.push(node); #endif } void QueueWithTwoStackTestFunc() { cout << "\n\n --------------- QueueWithTwoStackTestFunc Start -------------->" << endl; CQueue<int> stQueue; stQueue.AppendTail(1); stQueue.AppendTail(2); stQueue.AppendTail(3); cout << "Queue Pop Node: " << stQueue.DeleteHead() << endl; stQueue.AppendTail(4); stQueue.AppendTail(5); stQueue.AppendTail(6); cout << "Queue Pop Node: " << stQueue.DeleteHead() << endl; cout << "Queue Pop Node: " << stQueue.DeleteHead() << endl; cout << "Queue Pop Node: " << stQueue.DeleteHead() << endl; cout << "Queue Pop Node: " << stQueue.DeleteHead() << endl; cout << "Queue Pop Node: " << stQueue.DeleteHead() << endl; cout << "\n\n --------------- QueueWithTwoStackTestFunc End -------------->" << endl; }
/////////////////////////////////////////////////////////////////////////////////////////////
// 5.用两个队列实现一个栈
template <typename TYPE> class CStack { public: CStack(){} ~CStack(){} public: void AppendTail(const TYPE& value); TYPE DeleteHead(); private: queue<TYPE> m_stQueue1; queue<TYPE> m_stQueue2; }; template <typename TYPE> TYPE CStack<TYPE>::DeleteHead() { TYPE head; if (m_stQueue1.empty()) { while (m_stQueue2.size() > 1) { m_stQueue1.push(m_stQueue2.front()); m_stQueue2.pop(); } head = m_stQueue2.front(); m_stQueue2.pop(); } else { while (m_stQueue1.size() > 1) { m_stQueue2.push(m_stQueue1.front()); m_stQueue1.pop(); } head = m_stQueue1.front(); m_stQueue1.pop(); } return head; } template <typename TYPE> void CStack<TYPE>::AppendTail(const TYPE& value) { m_stQueue1.push(value); } void StackWithTwoQueueTestFunc() { cout << "\n\n --------------- StackWithTwoQueueTestFunc Start -------------->" << endl; CStack<int> stStack; stStack.AppendTail(1); stStack.AppendTail(2); stStack.AppendTail(3); cout << "Stack Pop Node: " << stStack.DeleteHead() << endl; stStack.AppendTail(4); stStack.AppendTail(5); stStack.AppendTail(6); cout << "Stack Pop Node: " << stStack.DeleteHead() << endl; cout << "Stack Pop Node: " << stStack.DeleteHead() << endl; cout << "Stack Pop Node: " << stStack.DeleteHead() << endl; cout << "Stack Pop Node: " << stStack.DeleteHead() << endl; cout << "Stack Pop Node: " << stStack.DeleteHead() << endl; cout << "\n\n --------------- StackWithTwoQueueTestFunc End -------------->" << endl; }
Review : 阅读并点评一篇英文技术文章
Tips : 学习一个技术技巧
排序算法学习:https://mp.weixin.qq.com/s/iiH2wSG-hVeUHxIsfuu9gw