pre delet 不能 ins find com 最大和 odi
26. 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向
- class Solution {
- public:
- //0:left 1: rightTreeNode* doConvert(TreeNode* pRootOfTree,int leftOrRight) {
- if(pRootOfTree == nullptr)return nullptr;
- TreeNode* pleft = doConvert(pRootOfTree->left,0);
- TreeNode* pright = doConvert(pRootOfTree->right,1);
- if(pleft) pleft->right = pRootOfTree;
- if(pright) pright->left = pRootOfTree;
- pRootOfTree->left = pleft;
- pRootOfTree->right = pright;
- //left,返回最右边的节点
- if(leftOrRight ==0) {
- while(pRootOfTree->right) {
- pRootOfTree = pRootOfTree->right;
- }
- }
- //right,返回最左边的节点
- if(leftOrRight ==1) {
- while(pRootOfTree->left) {
- pRootOfTree = pRootOfTree->left;
- }
- }
- return pRootOfTree;
- }
- public:
- TreeNode* Convert(TreeNode* pRootOfTree) {
- if(pRootOfTree == nullptr)
- return nullptr;
- TreeNode* pleft = doConvert(pRootOfTree->left,0);
- TreeNode* pright = doConvert(pRootOfTree->right,1);
- if(pleft) pleft->right = pRootOfTree;
- if(pright) pright->left = pRootOfTree;
- pRootOfTree->left = pleft;
- pRootOfTree->right = pright;
- //right,返回最左边的节点
- while(pRootOfTree->left) {
- pRootOfTree = pRootOfTree->left;
- }
- return pRootOfTree;
- }
- };
27. 输入一个字符串, 按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc, 则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba
- class Solution {
- private:
- voiddfs(stringstr,intk, vector<string>& res) {
- if(k == str.size() -1) {
- res.push_back(str);
- return;
- }
- unordered_set<int> visited;
- sort(str.begin()+k,str.end());
- for(size_t i = k; i < str.size(); i++) {
- if(visited.find(str[i]) == visited.end()) {
- visited.insert(str[i]);
- swap(str[k], str[i]);
- dfs(str, k +1, res);
- swap(str[k], str[i]);
- }
- }
- }
- public:
- vector<string> Permutation(string str) {
- vector<string> res;
- dfs(str, 0, res);
- return res;
- }
- };
28. 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次,超过数组长度的一半,因此输出 2。如果不存在则输出 0。
- class Solution {
- public:
- intMoreThanHalfNum_Solution(vector<int> numbers) {
- intn = numbers.size();
- if(n ==0)return 0;
- intnum = numbers[0],count =1;
- for(inti=1;i){
- if(numbers[i] == num) count++;
- elsecount--;
- if(count ==0){
- num = numbers[i];
- count =1;
- }
- }
- //verifycount =0;
- for(inti=0;i){
- if(numbers[i] == num) count++;
- }
- if(count*2> n )return num;
- else return 0;// not exist
- }
- };
29. 输入 n 个整数,找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字,则最小的 4 个数字是 1,2,3,4,。solution1 在牛客网上超时,solution2 能正常通过。
- 1 class Solution1 {
- 2 private: 3 int partition(vector < int > &input, int left, int right) {
- 4
- if (left >= right) 5
- return left;
- 6 int pivotVal = input[left];
- 7
- while (left < right) {
- 8
- while (left < right && input[right] >= pivotVal) {
- 9 right--;
- 10
- }
- 11 input[left] = input[right];
- 12
- while (left < right && input[left] <= pivotVal) {
- 13 left++;
- 14
- }
- 15 input[right] = input[left];
- 16
- }
- 17 input[left] = pivotVal;
- 18
- return left;
- 19
- }
- 20 public: 21 vector < int > GetLeastNumbers_Solution(vector < int > &input, int k) {
- 22 vector < int > res;
- 23 int n = input.size();
- 24 25 int index = partition(input, 0, n - 1);
- 26
- while (index != k - 1) {
- 27
- if (index > k - 1) {
- 28 index = partition(input, 0, index - 1);
- 29
- } else {
- 30 index = partition(input, index + 1, n - 1);
- 31
- }
- 32
- }
- 33
- for (int i = 0; i < k; i++) {
- 34 res.push_back(input[i]);
- 35
- }
- 36
- return res;
- 37
- }
- 38
- };
- 39 40 class Solution2 {
- 41 public: 42 vector < int > GetLeastNumbers_Solution(vector < int > &input, int k) {
- 43 int n = input.size();
- 44
- if (n == 0 || n < k) 45
- return vector < int > ();
- 46 multiset < int,
- greater < int >> leastNums(input.begin(), input.begin() + k);
- 47 48
- for (int i = k; i < n; i++) {
- 49
- if (input[i] < *leastNums.begin()) {
- 50 leastNums.erase(leastNums.begin());
- 51 leastNums.insert(input[i]);
- 52
- }
- 53
- }
- 54
- return vector < int > (leastNums.begin(), leastNums.end());
- 55
- }
- 56
- };
30HZ 偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后, 他又发话了: 在古老的一维模式识别中, 常常需要计算连续子向量的最大和, 当向量全为正数的时候, 问题很好解决。但是, 如果向量中包含负数, 是否应该包含某个负数, 并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为 8(从第 0 个开始, 到第 3 个为止)。你会不会被他忽悠住?(子向量的长度至少是 1)
- class Solution {
- public:
- intFindGreatestSumOfSubArray(vector<int>& array) {
- intn = array.size();
- if(n ==0)return 0;
- int* dp =new int[n];
- dp[0] = array[0];
- intmaxSum = dp[0];
- for(inti =1; i < n; i++) {
- dp[i] = max(dp[i -1] + array[i], array[i]);
- if(dp[i] > maxSum) {
- maxSum = dp[i];
- }
- }
- delete [] dp;
- return maxSum;
- }
- };
剑指 offer(26-30) 编程题
来源: http://www.bubuko.com/infodetail-2002378.html