剑指offer_2020_9_8

剑指 Offer 03. 数组中重复的数字

class Solution {
public:    
int findRepeatNumber(vector<int>& nums) {        
map<int, int>mym;        
for (int i = 0; i < nums.size(); i++)        {            mym[nums[i]]++;        }        map<int, int>::iterator it;        
for (it = mym.begin(); it != mym.end(); it++)        
{            
if (it->second > 1)            
{                
return it->first;            }        }        
return -1;
    }};

剑指 Offer 04. 二维数组中的查找

class Solution {
public:    
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {        
int n,m;        
if(matrix.size()==0||matrix[0].size()==0)        
return false;        
n=matrix.size();//行数        
m=matrix[0].size();//列数        
for(int i=n-1,j=0;i>=0&&j<m;)        {            
if(target==matrix[i][j])            {                return true;            }            if(target<matrix[i][j])            {                i--;                continue;            }            
if(target>matrix[i][j])            {                j++;                continue;            }                }        
return false;
    }};

剑指 Offer 05. 替换空格

class Solution {
public:    
string replaceSpace(string s) {        
string ans;    
for(int i=0;i<s.size();i++)    {        if(s[i]==' ')           ans+="%20";           else ans+=s[i];    }    
return ans;    }};

剑指 Offer 06. 从尾到头打印链表

class Solution {public:   
 vector<int> reversePrint(ListNode* head) {     
 vector<int>ans;     
 ListNode* p=head;     
 while(p!=NULL)     {         ans.push_back(p->val);         p=p->next;     }     std::reverse(ans.begin(),ans.end());     return ans;    }};

剑指 Offer 07. 重建二叉树

class Solution {
public:    
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {        
return build(preorder,inorder,0,0,inorder.size()-1);           }    TreeNode*build(vector<int>&preorder,vector<int>&inorder,int root,int start,int end)    {        if(start>end) return NULL;         
TreeNode*tree=new TreeNode(preorder[root]);         
int i=start;       
 while(i<end&&preorder[root]!=inorder[i]) i++;        
 tree->left=build(preorder,inorder,root+1,start,i-1);        
 tree->right=build(preorder,inorder,root+1+i-start,i+1,end);        
 return tree;    }};