在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution { public: bool Find(vector<vector<int> > array,int target) { //获取迭代器的取值 vector<vector<int> >::iterator ite1 = array.begin(); vector<int>::iterator ite2 = ite1->begin(); //循环寻找所需要的值 for(ite1 = array.begin(); ite1 != array.end(); ite1++) { for(ite2 = ite1->begin(); ite2 != ite1->end(); ite2++) { //cout<<*ite2<<endl; if(*ite2 == target) return true; } } return false; } };
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution { public: //length为牛客系统规定字符串输出的最大长度，固定为一个常数 void replaceSpace(char *str,int length) { char *ptemp = (char *)malloc(sizeof(char)*length); char *source = str; int i = 0; while(*source != '\0' && i < length) { if(*source == ' ') { ptemp[i] = '%%'; i++; if(i > length) break; ptemp[i] = '2'; i++; if(i > length) break; ptemp[i] = '0'; i++; if(i > length) break; source++; } else { ptemp[i] = *source; source++; i++; if(i > length) break; } } if(i > length) ptemp[length] = '\0'; else ptemp[i] = '\0'; strcpy(str,ptemp); free(ptemp); ptemp = NULL; } };
3.题目描述
输入一个链表，从尾到头打印链表每个节点的值。
输入描述:
输入为链表的表头
输出描述:
输出为需要打印的“新链表”的表头
class Solution { public: vector<int> printListFromTailToHead(struct ListNode* head) { //计算链表的长度 struct ListNode* temp = head; int nListLen = 0; while(temp != NULL) { nListLen++; temp = temp->next; } vector<int> array(nListLen); int i = nListLen-1; temp = head; while(temp != NULL) { array[i]=temp->val; temp = temp->next; i--; } return array; } };
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
#include <iostream> #include <vector> using namespace std; //二叉树节点的定义 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) { if(pre.size() == 0 || in.size() == 0) return NULL; struct TreeNode* root = new TreeNode(pre[0]); int left_child_len = 0; while(pre[0] != in[left_child_len]) { left_child_len++; } int right_child_len = pre.size() - left_child_len - 1; if(left_child_len > 0) { vector<int> a = vector<int>(pre.begin()+1, pre.begin()+left_child_len+1); vector<int> b = vector<int>(in.begin(), in.begin()+left_child_len); root->left = reConstructBinaryTree(a, b); } if(right_child_len>0) { vector<int> c = vector<int>(pre.begin()+left_child_len+1, pre.end()); vector<int> d = vector<int>(in.begin()+left_child_len+1, in.end()); root->right = reConstructBinaryTree(c, d); } return root; } }; //前序遍历 void preoder(struct TreeNode *tree) { if(tree == NULL) return; cout<<tree->val<<endl; preoder(tree->left); preoder(tree->right); } //中序遍历 void midorder(struct TreeNode *tree) { if(tree == NULL) return; midorder(tree->left); cout<<tree->val<<endl; midorder(tree->right); } //后续遍历 void postorder(struct TreeNode *tree) { if(tree == NULL) return; postorder(tree->left); postorder(tree->right); cout<<tree->val<<endl; } int main() { vector<int> pre(8); vector<int>::iterator ite = pre.begin(); for(; ite != pre.end(); ite++) { cout<<"Please input pre:"; cin>>*ite; } vector<int> in(8); for(ite = in.begin(); ite != in.end(); ite++) { cout<<"Please input in:"; cin>>*ite; } Solution s; struct TreeNode *tree = s.reConstructBinaryTree(pre, in); //前序遍历 cout<<"--------------------------------------"<<endl; preoder(tree); //中序遍历 cout<<"--------------------------------------"<<endl; midorder(tree); //后续遍历 cout<<"--------------------------------------"<<endl; postorder(tree); return 0; }
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class Solution { public: void push(int node) { stack1.push(node); } int pop() { if(stack2.empty()) { while(!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } } int p=stack2.top(); stack2.pop(); return p; } private: stack<int> stack1; stack<int> stack2; };
