剑指offer，靠谱分析及牛客网可AC代码，c++（31~40）

31、连续子数组的最大和 https://blog.csdn.net/malele4th/article/details/79326370

class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if (array.empty()) return 0; int max = array[0]; int temp = array[0]; for (int i = 1; i < array.size(); i++) { if (temp > 0) temp += array[i]; else temp = array[i]; if (temp > max) max = temp; } return max; } };

32、整数中1出现的次数 https://blog.csdn.net/malele4th/article/details/79326525

class Solution { public: int NumberOf1Between1AndN_Solution(int n) { int num = 0; long long m; for (m = 1; m < n; m *= 10) num += (n / m + 8) / 10 * m + (n / m % 10 == 1) * (n % m + 1); return num; } };

33、把数组排成最小的数 https://blog.csdn.net/malele4th/article/details/79326814 三参数sort函数的运用

34、丑数 https://blog.csdn.net/malele4th/article/details/79328046 不是除法，从乘法切入。

class Solution { public: int GetUglyNumber_Solution(int index) { if(index<=0) return 0; if(index==1) return 1; vector<int> k(index); k[0]=1; int t2=0,t3=0,t5=0; for(int i=1;i<index;i++) { k[i]=min(k[t2]*2,min(k[t3]*3,k[t5]*5)); if(k[i]==k[t2]*2) t2++; if(k[i]==k[t3]*3) t3++; if(k[i]==k[t5]*5) t5++; } return k[index-1]; } };

35、第一个只出现一次的字符位置 https://blog.csdn.net/malele4th/article/details/79328105 STL中map的应用

class Solution { public: int FirstNotRepeatingChar(string str) { map<char, int>s; for (int i = 0; i < str.size(); i++) s[str[i]]++; for (int i = 0; i < str.size(); i++) if (s[str[i]] == 1) return i; return -1; } };

36、数组中的逆序对 https://blog.csdn.net/malele4th/article/details/79328107 https://blog.csdn.net/derrantcm/article/details/46761051

class Solution { public: int InversePairs(vector<int> data) { int length=data.size(); if (length <= 0) return 0; vector<int>copy; for (int i = 0; i < length; i++) copy.push_back(data[i]); long long count = core(data, copy, 0, length - 1); return count % 1000000007; //题目要求对1000000007取模。 } long long core(vector<int> &data,vector<int> ©,int start,int end) { if (start == end) { copy[start] = data[start]; return 0; } int length = (end - start) / 2; long long left = core(copy, data, start, start + length);//data与copy位置不能改变 long long right = core(copy, data, start + length + 1, end); int i = start + length; int j = end; int index = end; long long count = 0; while (i >= start && j >= start + length + 1) { if (data[i] > data[j]) { count = count + j - length - start; copy[index--] = data[i--]; } else copy[index--] = data[j--]; } for (; i >= start; i--) //这两个循环前后顺序不影响，其实只有其中一个运行了。 copy[index--] = data[i]; for (; j >= start + length + 1; j--) copy[index--] = data[j]; return left + right + count; } };

37、两个链表的第一个公共节点 https://blog.csdn.net/malele4th/article/details/79328165 https://blog.csdn.net/derrantcm/article/details/46761093

class Solution { public: ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) { ListNode* p1 = pHead1; ListNode* p2 = pHead2; while (p1 != p2) { if (p1 != nullptr) p1 = p1->next; if (p2 != nullptr)p2 = p2->next; if (p1 != p2) { /*不加这个判断语句会一直循环*/ if (p1 == nullptr) p1 = pHead2; if (p2 == nullptr) p2 = pHead1; } } return p1; } };

38、数字在排序数组中出现的次数 https://blog.csdn.net/malele4th/article/details/79328299 https://blog.csdn.net/derrantcm/article/details/46771317

class Solution { public: int GetNumberOfK(vector<int> data, int k) { if (data.empty()) return 0; int length = data.size() - 1; int left = first(data, k, 0, length); int right = last(data, k, 0, length); if(left>-1&&right>-1) return right - left+1; return 0; } int first(vector<int>data,int k,int start,int end ) { if (start > end) return -1; int mid = start + (end - start) / 2; if (data[mid] == k) { if (data[mid - 1] != k || mid == start) return mid; else end = mid - 1; } else if (data[mid] > k) end = mid-1; else start = mid+1; return first(data, k, start, end); } int last(vector<int>data,int k,int start,int end) { if (start > end) return -1; int mid = start + (end - start) / 2; if (data[mid] == k) { if (data[mid + 1] != k || mid == end) return mid; else start = mid + 1; } else if (data[mid] > k) end = mid - 1; else start = mid + 1; return last(data, k, start, end); } };

39、二叉树的深度（判断是否为平衡二叉树） https://blog.csdn.net/malele4th/article/details/79328442 https://blog.csdn.net/derrantcm/article/details/46771529

// 递归遍历，仅仅一行 class Solution { public: int TreeDepth(TreeNode* pRoot){ return pRoot ? max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1 :0; } };

40、数组中只出现一次的数字 https://blog.csdn.net/malele4th/article/details/79329079 https://blog.csdn.net/derrantcm/article/details/46771717

class Solution { public: void FindNumsAppearOnce(vector<int> data, int* num1, int* num2) { if (data.size() < 2) return; int size = data.size(); int index = 0; int temp = data[0]; *num1 = *num2 = 0; for (int i = 1; i < size; i++) temp ^= data[i]; //(temp&1)括号不可少 while ((temp & 1) == 0) { temp = temp >> 1; index++; } for(int i=0;i<size;i++) { if (bit(data[i], index))* num1 ^= data[i]; else *num2 ^= data[i]; } } bool bit(int num, int index) { num = num >> index; return(num & 1); } };