剑桥offer(11~20)
class Solution { public: int NumberOf1(int n) { int count = 0; unsigned int num = n; while (num != 0) { if ((num & 1) == 1){ count++; } num = num >> 1; } return count; } };View Code
class Solution { public: double Power(double base, int exponent) { double result=0; if (exponent == 0){ return 1; } else{ if (abs(exponent) == 1){ return base; } result = base; for (int i = 2; i <= abs(exponent); i++){ result *= base; } } if (exponent > 0){ return result; } else{ return 1 / result; } } };View Code
class Solution { public: void reOrderArray(vector<int> &array) { for (int i = 0; i < array.size(); i++){ if(array[i]%2==0){ for(int j=i+1;j< array.size();j++){ if((array[j]%2==1)){ int tmp = array[j]; for(int k =j;k>i;k--){ array[k]= array[k-1]; } array[i]=tmp; break; } } } } } };View Code
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode*head = pListHead; ListNode*nodeK=pListHead; int len=0;//链表总长 int index=0;// if(k<=0){ return NULL; } while(head!=NULL){ len++; head=head->next; } if(k>len){ return NULL; } index = len-k; while(index--){ nodeK = nodeK->next; } return nodeK; } };View Code
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* h = NULL; ListNode* p = pHead; while(p){ ListNode* tmp = p -> next; p -> next = h; h = p; p = tmp; } return h; } };View Code
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) /* { ListNode *head = NULL, *node = NULL; while (pHead1 || pHead2){ if (((pHead1 == NULL) && (pHead2 != NULL)) || pHead1->val >= pHead2->val){ if (head){ node->next = pHead2; node = pHead2; } else{ node = pHead2; head = pHead2; } pHead2 = pHead2->next; } else if (((pHead2 == NULL) && (pHead1 != NULL)) || pHead1->val <= pHead2->val){ if (head){ node->next = pHead1; node = pHead1; } else{ node = pHead1; head = pHead1; } pHead1 = pHead1->next; } } node->next=NULL; return head; } */ { ListNode *head = NULL, *node = NULL; if (pHead1 == NULL) return pHead2; if (pHead2 == NULL) return pHead1; while (pHead1 && pHead2){ if ( pHead1->val >= pHead2->val){ if (head){ node->next = pHead2; node = pHead2; } else{ node = pHead2; head = pHead2; } pHead2 = pHead2->next; } else if ( pHead1->val <= pHead2->val){ if (head){ node->next = pHead1; node = pHead1; } else{ node = pHead1; head = pHead1; } pHead1 = pHead1->next; } } if (pHead1 == NULL){ node->next = pHead2; } if (pHead2 == NULL){ node->next = pHead1; } return head; } };View Code
class Solution { stack<int> data; stack<int> mindata; public: void push(int value) { data.push(value); if (mindata.size() <= 0){ mindata.push(value); } else if (value < mindata.top()){ mindata.push(value); } else if (value >= mindata.top()){ mindata.push(mindata.top()); } } void pop() { data.pop(); mindata.pop(); } int top() { return mindata.top(); } int min() { return mindata.top(); } };View Code
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int>tmp; int size = pushV.size(); if(size == 0) return false; for(int i=0,j=0;i<size;){ tmp.push(pushV[i++]); while(j<size && tmp.top() == popV[j]){ j++; tmp.pop(); } } return tmp.empty(); } };View Code
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<int> PrintFromTopToBottom(TreeNode *root) { queue<TreeNode*>q; vector<int>v; TreeNode *node = root; v.clear(); if(root == NULL){ return v; } q.push(node); while(!q.empty()){ node = q.front(); q.pop(); if(!node){ continue; } v.push_back(node->val); q.push(node->left); q.push(node->right); } return v; } };View Code
//非递归 //非递归也是一个基于递归的思想: //左子树一定比右子树小,因此去掉根后,数字分为left,right两部分,right部分的 //最后一个数字是右子树的根他也比左子树所有值大,因此我们可以每次只看有子树是否符合条件 //即可,即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理 //对于左子树回到了原问题,对于右子树,左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树 //只需看看右子树的右子树是否符合要求即可 class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { int size = sequence.size(); if(0==size)return false; int i = 0; while(--size) { while(sequence[i++]<sequence[size]); while(sequence[i++]>sequence[size]); if(i<size)return false; i=0; } return true; } }; BST的后序序列的合法序列是,对于一个序列S,最后一个元素是x (也就是根),如果去掉最后一个元素的序列为T,那么T满足:T可以分成两段,前一段(左子树)小于x,后一段(右子树)大于x,且这两段(子树)都是合法的后序序列。完美的递归定义 : ) 。 class Solution { bool judge(vector<int>& a, int l, int r){ if(l >= r) return true; int i = r; while(i > l && a[i - 1] > a[r]) --i; for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false; return judge(a, l, i - 1) && (judge(a, i, r - 1)); } public: bool VerifySquenceOfBST(vector<int> a) { if(!a.size()) return false; return judge(a, 0, a.size() - 1); } };View Code
class Solution { vector<vector<int> >allRes; vector<int> tmp; void dfsFind(TreeNode * node , int left){ tmp.push_back(node->val); if(left-node->val == 0 && !node->left && !node->right) allRes.push_back(tmp); else { if(node->left) dfsFind(node->left, left-node->val); if(node->right) dfsFind(node->right, left-node->val); } tmp.pop_back(); } public: vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { if(root) dfsFind(root, expectNumber); return allRes; } };View Code
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* searchNode(RandomListNode* pHead, int value){ RandomListNode* FHead = pHead; if(!FHead) return NULL; while (FHead&&FHead->label != value){ FHead = FHead->next; } if (FHead&&FHead->label == value) return FHead; else return NULL; } public: RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return NULL; RandomListNode* pHead1 = pHead; RandomListNode* newHead = NULL; RandomListNode* FHead = NULL; //首先构造一个正顺序的链表 while (pHead1 != NULL){ RandomListNode *node = new RandomListNode(pHead1->label); if (newHead == NULL){ newHead = node; FHead = node; } else{ FHead->next = node; FHead = FHead->next; } pHead1 = pHead1->next; } pHead1 = pHead; FHead = newHead; while (pHead1 != NULL){ if(pHead1->random){ FHead->random = searchNode(newHead, (int)pHead1->random->label); } FHead = FHead->next; pHead1 = pHead1->next; } return newHead; } };View Code
思路2:
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: //复制原始链表的任一节点N并创建新节点N',再把N'链接到N的后边 void CloneNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; while(pNode!=NULL) { RandomListNode* pCloned=new RandomListNode(0); pCloned->label=pNode->label; pCloned->next=pNode->next; pCloned->random=NULL; pNode->next=pCloned; pNode=pCloned->next; } } //如果原始链表上的节点N的random指向S,则对应的复制节点N'的random指向S的下一个节点S' void ConnectRandomNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; while(pNode!=NULL) { RandomListNode* pCloned=pNode->next; if(pNode->random!=NULL) pCloned->random=pNode->random->next; pNode=pCloned->next; } } //把得到的链表拆成两个链表,奇数位置上的结点组成原始链表,偶数位置上的结点组成复制出来的链表 RandomListNode* ReConnectNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; RandomListNode* pClonedHead=NULL; RandomListNode* pClonedNode=NULL; //初始化 if(pNode!=NULL) { pClonedHead=pClonedNode=pNode->next; pNode->next=pClonedNode->next; pNode=pNode->next; } //循环 while(pNode!=NULL) { pClonedNode->next=pNode->next; pClonedNode=pClonedNode->next; pNode->next=pClonedNode->next; pNode=pNode->next; } return pClonedHead; } //三步合一 RandomListNode* Clone(RandomListNode* pHead) { CloneNodes(pHead); ConnectRandomNodes(pHead); return ReConnectNodes(pHead); } };View Code
class Solution { public: /* 1、复制每个节点,如:复制节点A得到A1,将A1插入节点A后面 2、遍历链表,A1->random = A->random->next; 3、将链表拆分成原链表和复制后的链表 */ RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return NULL; RandomListNode *currNode = pHead; while(currNode){ RandomListNode *node = new RandomListNode(currNode->label); node->next = currNode->next; currNode->next = node; currNode = node->next; } currNode = pHead; while(currNode){ RandomListNode *node = currNode->next; if(currNode->random){ node->random = currNode->random->next; } currNode = node->next; } //拆分 RandomListNode *pCloneHead = pHead->next; RandomListNode *tmp; currNode = pHead; while(currNode->next){ tmp = currNode->next; currNode->next =tmp->next; currNode = tmp; } return pCloneHead; } };View Code
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { stack<TreeNode*> stack; TreeNode*root=NULL; TreeNode *p = pRootOfTree; TreeNode *pre=NULL; bool isFirst=true; //栈不空或者p不空时循环 while (p || !stack.empty()){ while (p != NULL){ //存入栈中 stack.push(p); //遍历左子树 p = p->left; } p = stack.top(); stack.pop(); if(isFirst){ root=p; pre = root; isFirst=false; }else { pre->right = p; p->left = pre; pre = p; } p = p->right; }//while return root; } };View Code
递归
//直接用中序遍历 public class Solution { TreeNode head = null; TreeNode realHead = null; public TreeNode Convert(TreeNode pRootOfTree) { ConvertSub(pRootOfTree); return realHead; } private void ConvertSub(TreeNode pRootOfTree) { if(pRootOfTree==null) return; ConvertSub(pRootOfTree.left); if (head == null) { head = pRootOfTree; realHead = pRootOfTree; } else { head.right = pRootOfTree; pRootOfTree.left = head; head = pRootOfTree; } ConvertSub(pRootOfTree.right); } }View Code