剑指offer相关代码

全是纯手工编写，方便自己查看

#include<iostream> #include<vector> #include<stack> #include<queue> using namespace std; //使用递归时，函数进去的第一步就是判断退出递归的边界条件，因为递归都是要返回值的，所以第二步就是定义返回值的变量，此变量的初始值与第一步边界条件返回值要相反或不同 //(因为只返回一个值，一般只定义一个变量，即使定义多个变量，最后这多个变量都要整合为一个变量进行返回)， //第三步就是根据要递归的各种可能性，依次调用函数本身，就针对一种可能性而言，调用时参数就变为其中的一种可能性，赋值给第二步定义的变量，然后根据变量值进行判断 //是否进行下一种可能性的递归或直接返回此变量值。若进行下一种可能性递归，在函数最后一句return之前，就要把各种可能性都整合成一个值 //,第四步返回这个值。 //重中之重：在递归时，就将此次递归为本层操作，不要想到递归进下一层，既然使用了递归函数，那么下一层自会处理。 //斐波那契数列第n项的值 long long Fibonacci(unsigned int n) { int result[2]={0,1}; if(n < 2) result[n]; long long first = 0; long long second = 1; long long fibN = 0; for(int i = 2;i <= n;++i) { fibN = first +second; first = second; second = fibN; } return fibN; } //求二进制中1的个数 int NumberOf1(int n) { int count = 0; while(n > 0) { ++count; n = n & (n-1);//将n最右边的1变为0 } return count; } double Power(double base,int exponent) { if(base == 0 && exponent <=0) throw exception("invalid input"); if( exponent == 0) return 1.0; double result = 1.0; unsigned int temp = exponent; if(exponent < 0) temp = static_cast<int> (-exponent); for(int i = 0;i < temp;++i) { result *= base; } if(exponent < 0) result = 1/result; return result; } //从1打印到n 1.累加函数2.打印函数，注意，是每累加一次就打印一次，而不是把数字全部存储好以后再打印 //利用字符串来模拟加法 bool Increment(string &number) { int length = number.size(); bool over_flow = false;//检查最高位是否达到999..99，只有number[0]产生进位，则表明达到了最大值 int take_over = 0;//进位信息，最多为1；因为一次进位只会向高位加1 for(int i = length-1;i >= 0;--i) { int sum = number[i] - '0' + take_over; if(i == length-1) ++sum; if(sum >= 10) { if(i == 0) { over_flow = true;//最高位进位了 } else { sum -= 10; take_over = 1; number[i] = '0' + sum; } } else { number[i] = '0' + sum;//如果sum没有>=10，那么其次高位就不会进位，所以次高位就不需要进行遍历了 break; } } return over_flow; } void PrintNumber(const string &number) { bool is_begin = false; int length = number.size(); for(int i = 0;i < length;++i) { if(!is_begin && number[i] != '0') { is_begin = true; } if(is_begin) { cout<<number[i]; } } cout<<endl; } void Print1toMax(int n) { if(n < 1) return; string number(n,'0'); while(!Increment(number)) { PrintNumber(number); } } //在O(1)时间删除链表节点 struct ListNode { int value; ListNode *next; }; //此处没有考虑结点不是链表的情况 void DeleteNode(ListNode **head,ListNode *pto_deleted) { if(head == NULL || pto_deleted == NULL) return; if(pto_deleted->next != NULL) { ListNode *temp = pto_deleted->next; pto_deleted->value = temp->value; pto_deleted->next = temp->next; delete temp; temp = NULL; } else if(*head == pto_deleted)//只有一个结点 { delete pto_deleted; pto_deleted = NULL; *head == NULL; } else//删除尾结点 { ListNode *pNode = *head; while(pNode->next != pto_deleted) { pNode = pNode->next; } pNode->next =NULL; delete pto_deleted; pto_deleted = NULL; } } //输出倒数第k个节点 ListNode *FindToTail(ListNode **head,unsigned int k) { if(head == NULL || k==0) return NULL; ListNode *first = *head; ListNode *second_kth = first->next; int count = 0; while(count < k-1 && second_kth->next != NULL)//这样能保证second_kth是最后一个节点 { second_kth = second_kth->next; ++count; } if(count + 1 == k) { while(second_kth->next != NULL)//若写成second_kth != NULL 则在尾结点时，还要执行此循环，此后second_kth为NULL了 { first = first->next; second_kth = second_kth->next; } return first; } else return NULL; } //翻转链表 ListNode *ReverseList(ListNode *head) { if(head == NULL) return head; ListNode *prev = NULL; ListNode *next = NULL; ListNode *node = head; while(node != NULL) { next = node->next; node->next = prev; prev = node; if(next == NULL) { return node; } else { node = next; } } } //合并两个已经排序好的链表 ListNode *Merge(ListNode *head1,ListNode *head2) { if(head1 == NULL) return head2; if(head2 == NULL) return head1; ListNode *head = NULL; if(head1->value < head2->value) { head = head1; head1 = head1->next; } else { head = head2; head2 = head2->next; } ListNode *node = head; while(head1 != NULL && head2 != NULL) { if(head1->value < head2->value) { node->next = head1; head1 = head1->next; } else { node->next = head2; head2 = head2->next; } node = node->next; } if(head1 == NULL) node->next = head2; if(head2 == NULL) node->next = head1; return head; } //把一个数组的奇数放在前面，偶数放在后面,一般：可以定义两个数组，%2来区分奇数和偶数，然后再用一个循环给传进来的数组进行赋值 //但空间复杂度为0(n) //技巧：奇数的二进制表示法的最低位必定为1，偶数的最低位必定为0，所以根据此来判断是奇数还是偶数，空间复杂度为O(1) void ReorderOddEven(vector<int> &data) { if(data.empty()) return; int size = data.size(); int begin = 0; int end = size-1; while(begin < end) { while(begin < end && (data[begin] & 0x01) != 0)//直到指向偶数才停止循环 ++begin; while(begin < end && (data[end] & 0x01) == 0)//直到指向奇数才停止循环 --end; if(begin < end)//只要begin < end，就要一直执行外层的while { int temp = data[begin]; data[begin] = data[end]; data[end] = temp; } } } //判断树B是否是数A的子树 struct BinaryTreeNode { int value; BinaryTreeNode *left; BinaryTreeNode *right; }; bool DoesSubtree(BinaryTreeNode *rootA,BinaryTreeNode *rootB) { if(rootB == NULL)//表明B子树已经比较完了 return true; if(rootA == NULL)//表明A树比较万了，但B树还有节点 return false; bool result_left = false,result_right=false,result = false; if(rootA->value == rootB->value) { result_left = DoesSubtree(rootA->left,rootB->left); result_right = DoesSubtree(rootA->right,rootB->right); } result = result_left && result_right; return result; } bool HasSubtree(BinaryTreeNode *rootA,BinaryTreeNode *rootB) { if(rootB == NULL) return true; bool result =false;// DoesSubtree(rootA,rootB); if(rootA != NULL && rootB != NULL) { result = DoesSubtree(rootA,rootB); if(!result) result = HasSubtree(rootA->left,rootB); if(!result) result = HasSubtree(rootA->right,rootB); } return result; } //二叉树镜像 void Mirror(BinaryTreeNode *pnode) { if(pnode == NULL) return; if(pnode->left == NULL && pnode->right == NULL) return; BinaryTreeNode *temp = pnode->left; pnode->left = pnode->right; pnode->right = temp; Mirror(pnode->left); Mirror(pnode->right); } //二叉树层序遍历,也叫广度优先遍历，遍历时，遇到根节点，打印其值，就把其左右子(6,8)节点加入到容器中，因为同层是从左到右遍历，所以先取出左子节点(6)， //重复此操作(8,5,7)，此时右子节点(8)在最前面,依次下去可以看出容器是一个先进先出的队列 //前序，中序，后序遍历都是二叉树的深度优先遍历的特例 void PrintTopToButtom(BinaryTreeNode *root) { if(root == NULL) return; queue<BinaryTreeNode *> temp; temp.push(root);//每访问一个节点时，都会把其左右节点压入队列中 while(temp.size())//终止条件是队列中不再含有节点 { BinaryTreeNode *pnode = temp.front(); temp.pop(); cout<<pnode->value<<' '; if(pnode->left != NULL) temp.push(pnode->left); if(pnode->right != NULL) temp.push(pnode->right); } } //普通的深度优先遍历,是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。 //在遍历了根结点后，就开始遍历左子树，最后才是右子树。因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序， //由此可以先将右子树压栈，然后再对左子树压栈，这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。 void depthFirstSearch(BinaryTreeNode *root){ stack<BinaryTreeNode *> nodeStack; //使用C++的STL标准模板库 nodeStack.push(root); BinaryTreeNode *node; while(!nodeStack.empty()){ node = nodeStack.top(); printf("%d ", node->value); //遍历根结点 nodeStack.pop(); if(node->right){ nodeStack.push(node->right); //先将右子树压栈 } if(node->left){ nodeStack.push(node->left); //再将左子树压栈 } } } //判断一个序列是否是二叉搜索树的后序遍历 bool VerifySequenceOfBST(int *sequence,int length) { if(sequence == NULL || length <= 0) return false; int root = sequence[length-1]; int i = 0; for(;i < length;++i)//左子树的所有节点 { if(sequence[i] > root) break; } for(int j = i;j < length -1;++j) { if(sequence[j] < root) return false; } bool left= true;//定义初始值为true if(i > 0)//如果递归到最后i = 0了，说明就没有左子节点了，也就是说全部遍历完左子树都满足后序遍历的条件，所以说初始值为true left = VerifySequenceOfBST(sequence,i); bool right = true; if(i < length-1)//如果递归到i=length-1即最后一个右子节点了，也说明右子树满足后序遍历的条件 right = VerifySequenceOfBST(sequence+i,length-i-1); return (left && right); } //二叉树中和为某一路径的值，必须要找至叶子节点才算是路径，并打印所有路径 //用栈来实现路径的保存，但是在打印节点值的时候，很不方便，所以用vector来替代 void FindPath(BinaryTreeNode *root,int number) { if(root == NULL) return; int cur = 0; vector<int> path; FindPath(root,path,cur,number); } void FindPath(BinaryTreeNode *root,vector<int> &path,int cur,int number) { if(root == NULL) return; cur += root->value; path.push_back(root->value); bool leaf = (root->left == NULL) && (root->right ==NULL); if(cur == number && leaf) { for(auto it = path.begin();it != path.end();++it) { cout<<*it<<' '; } } //如果不是叶子节点，继续访问，上面的if不会执行 if(root->left != NULL) FindPath(root->left,path,cur,number); if(root->right != NULL) FindPath(root->right,path,cur,number); path.pop_back();//退到上一个节点 } //将一个二叉搜索树转换成一个双向链表,利用中序遍历，当遍历到根节点时，其左子树已经转换成了一个排序的链表了 //此时处在链表最后一个节点的是当前链表的最大值，只需把此值和根节点连接起来即可 //根节点变成最后一个节点，此时遍历右子树，只需把根节点和右子树中最小节点连接起来即可 void ConvertNode(BinaryTreeNode *pNode,BinaryTreeNode **pLastNodeInList) { if(pNode == NULL) return; BinaryTreeNode *current = pNode; if(pNode->left != NULL) ConvertNode(pNode->left,pLastNodeInList); current->left = *pLastNodeInList; if(*pLastNodeInList != NULL) (*pLastNodeInList)->right = current; *pLastNodeInList = current; if(current->right != NULL) ConvertNode(pNode->right,pLastNodeInList); } BinaryTreeNode* Convert(BinaryTreeNode *proot) { BinaryTreeNode *pLastNodeInList = NULL; ConvertNode(proot,&pLastNodeInList); BinaryTreeNode *headoflist = pLastNodeInList; while(headoflist != NULL && headoflist->left != NULL) headoflist = headoflist->left; return headoflist; } //根据前序和中序重建二叉树 struct BinaryTreeNode { int value; BinaryTreeNode *left; BinaryTreeNode *right; BinaryTreeNode *parent; }; BinaryTreeNode *RestructTree(int *preorder,int *inorder,int length) { if(preorder ==NULL || inorder == NULL || length <= 0) return NULL; BinaryTreeNode *root = new BinaryTreeNode(); root->value = preorder[0]; root->left = NULL; root->right = NULL; int mid = 0; for(int i = 0 ;i < length;++i) { if(inorder[i] == preorder[0]) { mid = i; } } root->left = RestructTree(preorder+1,inorder,mid); root->right = RestructTree(preorder+mid+1,inorder+mid+1,length-1-mid); return root; } BinaryTreeNode *RestructTree1(int *afterorder,int *inorder,int length) { if(afterorder == NULL || inorder == NULL || length < 1) return NULL; BinaryTreeNode *root = new BinaryTreeNode(); root->value = afterorder[length-1]; root->left = NULL; root->right = NULL; int mid = 0; for(int i = 0;i < length;++i) { if(inorder[i] == root->value) { mid = i; break; } } root->left = RestructTree1(afterorder,inorder,mid); root->right = RestructTree1(afterorder+mid,inorder+mid,length-mid-2);//因为后序遍历中，最后一个节点已经遍历过了，要去掉 } //给定一个栈的压入序列，判断一个序列是否是栈的弹出序列 bool IsPopOrder(vector<int> &pPush,vector<int> &pPop,int length) { if(pPush.empty() || length < 0 || pPush.size() !=length ) return false; if(pPop.empty()) return true; stack<int> temp; int count = 0; for(int i = 0; i < length;++i)//针对弹出序列 { while(temp.empty() || temp.top() != pPop[i])//栈顶不等于要弹出的值得时候，就一直压入栈 { if(count < length) { temp.push(pPush[count]); count++; } else//已经没有值可以压入栈了 { return false; } } if(temp.top() == pPop[i])//while在 ==时跳出，这个if就在保证弹出栈的下一个i与top值相等 { temp.pop(); } } if(temp.empty()) return true; else return false; } //复制复杂链表 struct ComplexListNode { int value; ComplexListNode *next; ComplexListNode *sibling; }; //分为三步 //第一步,先把要复制的节点连接到原链表中，此时复制的节点并没有设置sibling void CloneNodes(ComplexListNode *head) { ComplexListNode *pnode = head; while(pnode != NULL) { ComplexListNode *pCloned = new ComplexListNode(); pCloned->value = pnode->value; pCloned->sibling = NULL; pCloned->next = pnode->next; pnode->next = pCloned; pnode = pCloned->next; } } //第二步，设置复制的节点的sibling,原节点N的sibling指向节点s， //那么复制的节点N'是N的next,所以同样s'的节点就应指向原节点s的next void ConnectSiblingNodes(ComplexListNode *head) { ComplexListNode *pnode = head; while(pnode != NULL) { ComplexListNode *pCloned = pnode->next; if(pnode->sibling != NULL)//==NULL的不用复制 { pCloned->sibling = pnode->sibling->next; } pnode = pCloned->next; } } // 第三步，拆分链表，奇数时为原链表，偶数为复制的链表 ComplexListNode *ReconnectNodes(ComplexListNode *head) { ComplexListNode *pNode =head; ComplexListNode *pClonedHead = NULL; ComplexListNode *pClonedNode = NULL; if(pNode != NULL) { pClonedNode = pClonedHead = pNode->next; pNode->next = pClonedHead->next; pNode = pNode->next; } while(pNode != NULL) { pClonedNode->next = pNode->next; pClonedNode = pClonedNode->next; pNode->next = pClonedNode->next; pNode = pNode->next; } return pClonedHead; } //第四步：综合前三步 ComplexListNode *Clone(ComplexListNode *head) { CloneNodes(head); ConnectSiblingNodes(head); return ReconnectNodes(head); } //字符串排列 void Permutation(char *pstr) { if(pstr == NULL) return; } void Permutation(char *pstr,char *begin) { if(*begin == '\0') { printf("%s",pstr); } else { for(char *pch = begin;*pch != '\0';++pch) { char temp = *pch; *pch = *begin; *begin = temp; Permutation(pstr,begin+1); } } } //字符串排列 void Permutation(char* pStr, char* pBegin) { if(*pBegin == '\0') { printf("%s\n", pStr); } else { for(char* pCh = pBegin; *pCh != '\0'; ++ pCh) { swap(*pCh,*pBegin); Permutation(pStr, pBegin + 1); swap(*pCh,*pBegin);//要保证下一次递归时原顺序不变 } } } void Permutation(char* pStr) { if(pStr == NULL) return; Permutation(pStr, pStr); } //输出数组中出现次数超过一半的数字 //输出数组中出现次数超过一半的数字,要考虑输入的数组最高频率出现的次数没有一半的情况 bool cmp(int a,int b) { return a < b; } int MoreHalfOfNumber(vector<int> data) { sort(data.begin(),data.end(),less<int>()); int length = data.size(); length--; return data[length/2]; } bool is_input_vaild = false; int MoreHalfOfNumber(vector<int>& data) { if(data.size() <= 0) { is_input_vaild = true; return 0; } sort(data.begin(),data.end(),cmp); int length = data.size(); length--; int number = data[length/2]; int count = 0; for(int i = 0;i < data.size();++i) { if(data[i] == number) count++; } if(count*2 < length) { is_input_vaild = true; return 0; } } //第一个只出现一次的字符 char FirstNotRepeating(char *pstring) { if(pstring == NULL) { return '\0'; } unsigned int hash[256]; for(int i = 0;i < 256;++i) { hash[i] = 0; } int size = strlen(pstring); for(int i = 0 ;i < size;++i) { hash[pstring[i]]++; } for(int i = 0;i < size;++i) { if(hash[pstring[i]] == 1) { return pstring[i]; } } return '\0'; } //两个链表中第一个公共结点,指的是地址相同，而不单单是结点值相同 //链表长的先走几步，当一样长度时，就一起走，找到同一个结点 ListNode *FindFirstCommomNode(ListNode *phead1,ListNode *phead2) { int phead1_len = 0,phead2_len = 0; ListNode *temp1 = phead1; ListNode *temp2 = phead2; while(temp1 != NULL) { phead1_len++; temp1 = temp1->next; } while(temp2 != NULL) { phead2_len++; temp2 = temp2->next; } temp1 = phead1; temp2 = phead2; int distance = phead1_len - phead2_len; if(distance > 0) { while(distance) { temp1 = temp1->next; distance--; } } else if(distance < 0) { while(distance) { temp2 = temp2->next; distance++; } } while(temp1 != NULL && temp2 != NULL && temp1 != temp2) { temp1 = temp1->next; temp2 = temp2->next; } return temp1; } //数字在排序数组中出现的次数，时间复杂度为O(lgn) int GetFirstK(int *data,int length,int k,int start,int end) { if(start > end) return -1; int middleIndex = (start+end)/2; int middledata = data[middleIndex]; if(middledata == k) { if(middleIndex > 0 && data[middleIndex-1] != k || middleIndex == 0) { return middleIndex; } else { end = middleIndex - 1; } } else if(middledata > k) { end = middleIndex -1; } else { start = middleIndex + 1; } return GetFirstK(data,length,k,start,end);//不像快速排序那样，这个只需要找其中一边，而快速排序，两边都要操作 } int GetLastK(int *data,int length,int k,int start,int end) { if(start > end) return -1; int middleIndex = (start+end)/2; int middledata = data[middleIndex]; if(middledata == k) { if(middleIndex < length-1 && data[middleIndex+1] != k || middleIndex == length-1) { return middleIndex; } else { start = middleIndex + 1; } } else if(middledata > k) { end = middleIndex -1; } else { start = middleIndex + 1; } return GetLastK(data,length, k,start, end); } int GetNumberOfK(int *data,int length,int k) { int count = 0; if(data == NULL) return -1; int first = GetFirstK(data,length,k,0,length-1); int last = GetLastK(data,length,k,0,length-1); if(first > -1 && last > -1) count = last - first + 1; return count; } 求一个二叉树的深度 int TreeDepth(BinaryTreeNode *proot) { if(proot == NULL) return 0; int left = TreeDepth(proot->left); int right = TreeDepth(proot->right); return (left > right) ? (left+1) : (right+1);//后序遍历左右子树以后，找到最深的深度，然后加上根节点1，就是最后的深度 } //判断一个二叉树是否是平衡二叉树,利用后序遍历，可以只遍历一次节点就能得出结果 bool IsBalanced(BinaryTreeNode *proot,int *depth) { if(proot == NULL) { *depth = 0; return true; } int left,right; if( IsBalanced(proot->left,&left) && IsBalanced(proot->right,&right)) { int diff = left - right; if(diff <= 1 && diff >= -1) { *depth = 1 + (left > right) ? left : right; return true; } } return false; } bool IsBalanced(BinaryTreeNode *proot) { int depth = 0; return IsBalanced(proot,&depth); } //找出数组中2个只出现一次的数，其他数字均出现两次。 //利用异或原理，分成两个子数组，每个子数组中只包含一个只出现1次的数. //在总的异或结果中找到第一位为1的位,num为数组的异或结果 unsigned int FindFirstBit1(int num) { int indexBit = 0; while((num & 1) == 0 && indexBit < 8 * sizeof(int)) { num = num>>1; ++indexBit; } return indexBit; } //判断该数是否属于其中一个子数组，若是为true,否则为另一个子数组中的值 //IsBit1两个值相同的肯定会被分到同一个组中,相与过后，要么同为1，要么同为0 bool IsBit1(int num,int indexBit) { num = num>>indexBit; return (num & 1); } void FindNumsAppearOnce(int data[],int length,int &num1,int &num2) { if(data == NULL || length < 0) return; int result_xor = 0; for(int i = 0;i < length;++i) result_xor ^= data[i]; int index_bit = FindFirstBit1(result_xor); for(int i = 0;i < length;++i) { if(IsBit1(data[i],index_bit)) num1 ^= data[i]; else num2 ^= data[i]; } } //在递增排序的数组中，找出和为S的两个数字，任意一组均可 //O(n)的解法 bool FindNumberWithSum(int data[],int sum) { bool found = false; if(data == NULL) return found; int length = sizeof(data)/sizeof(int); int end = length - 1; int start = 0; while(end > start) { int result = data[start] + data[end]; if(result == sum) { cout<<data[start]<<data[end]<<endl; found = true; } else if(result < sum) //因为已经是排好序的，所以如果小的话，就在增加一点点 start++; else//如果大的话，就再减小一点点 end--; } return found; } //翻转一句英文 string Reverse(string s) { if(s.size() == 0) return ""; reverse(s.begin(),s.end()); vector<string> data; int size = s.size(); int index = 0; for(int i = 0; i < size;++i) { if(s[i] == ' ') { data.push_back(s.substr(index,i-index)); index = i+1; } } data.push_back(s.substr(index)); size = data.size(); string result = ""; for(int i = 0; i< size-1;++i) { reverse(data[i].begin(),data[i].end()); result += data[i]+" "; } reverse(data[size-1].begin(),data[size-1].end()); result += data[size-1]; return result; } //字符串左旋操作,将左边的num个字符旋转到末尾 string LeftRoate(string s,int num) { if(s.size() < num) return ""; string s1 = s.substr(0,num); string s2 = s.substr(num); s = s2 + s1; return s; } //字符串转换成整数 int StrToInt(string s) { if(s.size() == 0) { cout<<"输入无效"; return 0; } unsigned int max = -1; long long result = 0; int flag = 1; if(s[0] == '+') { flag = 1; s = s.substr(1); } else if(s[0] == '-') { flag = -1; s = s.substr(1); } int size = s.size(); for(int i = 0;i < size; ++i) { if((s[i] < '9') && (s[i] >= '0') )//s[i]是字符串 { result = result * 10 + flag * (s[i] -'0');//所以若不减去'0'的字符对应的ACSII码的话，会出错'0' = 46 if((flag == 1 && result > 0x7FFFFFFF) || (flag == -1 && result < (signed int)0x80000000)) { cout<<"输入无效"; result = 0; break; } } else { cout<<"输入无效"; result = 0; break; } } return (int)result; } //替换空格 void PrintNewString(string orignal) { if(orignal.size() == 0) return; int count = 0; int length=0; string temp=""; for(int i = 0 ;i < orignal.size();++i) { if(orignal[i] ==' ') { temp += "%20"; } else temp += orignal[i]; } cout<<temp<<endl; } //打印从尾到头的节点 struct ListNode { int value; ListNode *next; }; void PrintNode(ListNode *root) { if(root == NULL) return; stack<int> temp; ListNode *node = root; while(node != NULL) { temp.push(node->value); node = node->next; } while(!temp.empty()) { cout<<temp.top()<<" "; temp.pop(); } } //求连续子数组的最大和 //思路：2、每次都记录当前累加和的最大值，若累加下一个整数后大于记录的值，就更新，否则，不更新 //1、若连续累加后和为负数，则总是从下一个整数开始重新计算,但是当前的最大值仍然保存着 bool g_Invaildinput = false; int GetGreastSum(vector<int> data) { if(data.empty()) { g_Invaildinput = true; return 0; } g_Invaildinput = false; int curr_sum = data[0]; int great_num = data[0]; int size = data.size(); for(int i = 1;i < size;++i) { if(curr_sum < 0) curr_sum = data[i]; else curr_sum += data[i]; if(curr_sum > great_num) great_num = curr_sum; } return great_num; } //把数组排成最小的数 bool cmp(string s1, string s2) { string t1 = s1 + s2; string t2 = s2 + s1; return t1 < t2; } void Print(vector<int> data) { vector<string>data_t; for (auto c : data) { data_t.push_back(to_string(c)); } sort(data_t.begin(), data_t.end(), cmp); for (auto c : data_t) { cout << c; } cout << endl; }