方法 EasyCVR 观察者模式 perl razor tcp constructor datepicker ios7 后台管理模板下载 网盘源码 mysql数据库名称 webform开发教程 当前时间减一天 python怎么下载安装 python程序实例 python代码 java环境搭建 java中的对象 java课程 java获取本机ip java截取 linuxtar命令 shell编程学习 修改mac地址软件 xp画图工具 microkms 销售单软件 r语言和python 混沌世界隐藏英雄密码 js跳出for循环 ip切换软件 淘宝图片下载 流程图制作工具 mp4剪切合并大师 相册制作工具 网络电子书 黑客攻防技术宝典 dnf卡邮件 保留两位小数的函数
当前位置: 首页 > 学习教程  > 编程语言

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

2021/2/13 17:19:11 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

剑指 Offer 03. 数组中重复的数字 &#xff1a;hash解决简单粗暴。 class Solution { public://思路&#xff1a; n < 100000 没有爆数组的可能&#xff0c;且所有数字都在 0&#xff5e;n-1 的范围内&#xff0c;可以用以下数组标记来写int findRepeatNumber(vector<i…

剑指 Offer

03. 数组中重复的数字 :hash解决简单粗暴。
class Solution {
public:
    //思路: n <= 100000 没有爆数组的可能,且所有数字都在 0~n-1 的范围内,可以用以下数组标记来写
    int findRepeatNumber(vector<int>& nums) {
     unordered_map<int,int> mp;
     for(int i=0;i<nums.size();i++){
         if(++mp[nums[i]]>1)  return nums[i];
     }
     return -1;
    }
};
04. 二维数组中的查找:暴力能解决就是差了点感觉
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
       for(int i = 0 ; i < matrix.size() ; i ++){
            for(int j = 0 ; j < matrix[0].size() ; j ++){
                if(matrix[i][j] == target) return true;
            }
        }
        return false;
    }
};
05. 替换空格:替换就完事了
class Solution {
public:
    string replaceSpace(string s) {
    string res;
    for(auto &c:s){
        if(c==' ') res=res+"%20";
        else res+=c; 
    }
    return res;
    }
};
06. 从尾到头打印链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //反转链表,,。
    vector<int> reversePrint(ListNode* head) {
        ListNode *pre =NULL;
        ListNode *cur =head;
        vector<int> res;
        while(cur!=NULL){
            ListNode* next=cur->next;
             cur->next = pre;
             pre=cur;
             cur=next;
        }
        while(pre){
          res.push_back(pre->val);
          pre = pre->next;
        }
        return res;
    }
};
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 left,int right){
       if(left > right) return NULL;   //当左大于右的时候结束。
       TreeNode* tree = new TreeNode(preorder[root]);  //建立一颗树。
       int i= left;
       while(i<right && preorder[root]!= inorder[i]) i++;
       tree->left=build(preorder,inorder,root+1,left,i-1);
       tree->right=build(preorder,inorder,root+1+i-left,i+1,right);
       return tree;
    }
};
09. 用两个栈实现队列
class CQueue {
    // CQUEUE是创建队列
    //appendTail是队尾添加数
    //delete是队队头删数
    //两个栈模拟队列,栈是先进后出,队列是先进先出,两个栈模拟队列就是,两个栈的顺序为反。
    //ex:A:1 2 3 4
    //    B:4 3 2 1
public:
    stack<int> stack1;
    stack<int> stack2;
    CQueue() {
 
    }
    
    void appendTail(int value) {
         stack1.push(value);
    }
    
    int deleteHead() {
       if(stack2.empty()){
           while(!stack1.empty())  {stack2.push(stack1.top()); stack1.pop();}
       }
       if(stack1.empty() && stack2.empty())  return -1;
       int temp = stack2.top();
       stack2.pop();
       return temp;
    }
};
10- I. 斐波那契数列
int temp[]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,134903163,836311896,971215059,807526948,778742000,586268941,365010934,951279875,316290802,267570670,583861472,851432142,435293607,286725742,722019349,8745084,730764433,739509517,470273943,209783453,680057396,889840849,569898238,459739080,29637311,489376391,519013702,8390086,527403788,535793874,63197655,598991529,662189184,261180706,923369890,184550589,107920472,292471061,400391533,692862594,93254120,786116714,879370834,665487541,544858368,210345902,755204270,965550172,720754435,686304600,407059028,93363621,500422649,593786270,94208912,687995182};
int fib(int n){
   return temp[n];
}
10- II. 青蛙跳台阶问题
int temp[]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,134903163,836311896,971215059,807526948,778742000,586268941,365010934,951279875,316290802,267570670,583861472,851432142,435293607,286725742,722019349,8745084,730764433,739509517,470273943,209783453,680057396,889840849,569898238,459739080,29637311,489376391,519013702,8390086,527403788,535793874,63197655,598991529,662189184,261180706,923369890,184550589,107920472,292471061,400391533,692862594,93254120,786116714,879370834,665487541,544858368,210345902,755204270,965550172,720754435,686304600,407059028,93363621,500422649,593786270,94208912,687995182,782204094};
int numWays(int n){
    return temp[n+1];
}
11. 旋转数组的最小数字
class Solution {
public:
    int minArray(vector<int>& numbers) {
     sort(numbers.begin(),numbers.end());
     return numbers[0];
    }
};
12. 矩阵中的路径
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(dfs(board,word,i,j,0))
                    return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board,string word,int i,int j,int k){
        if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]!=word[k])
            return false;
        if(k==word.size()-1)
            return true;
        char temp = board[i][j];
        board[i][j]='*';
        bool ans = dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1)||
                    dfs(board,word,i,j+1,k+1)||dfs(board,word,i,j-1,k+1);
        board[i][j] = temp;
        return ans;
    }
};
13. 机器人的运动范围
class Solution {
public:
    int flag[101][101]={0};  //标记自己已经走过;

    int movingCount(int m, int n, int k) {
     return dfs(m,n,0,0,k);
    }

    int dfs(int m,int n,int x,int y,int k){
        if(x>=m || x<0 || y>=n ||y<0||(x/10+x%10+y/10+y%10)>k||flag[x][y])  return 0;
        flag[x][y] = 1;
        return dfs(m,n,x+1,y,k)+dfs(m,n,x-1,y,k)+dfs(m,n,x,y+1,k)+dfs(m,n,x,y-1,k)+1;
    }
};
14- I. 剪绳子
class Solution {
public:
    //当n=1,max=0; n=2,max=1; n=3,max=2;n=4, max=4;n=5,max= 6;n=6,max=9;
    //                                  n=7,max=12;n=8,max=18;n=9,max=27;
    //这就有一个规律了,试一下就好了。
    int cuttingRope(int n) {
     if(n==1) return 0;
     if(n==2) return 1;
     if(n==3) return 2;
     if(n==4) return 4;
     if(n==5) return 6;
     if(n==6) return 9;
     return 3*cuttingRope(n-3);
    }
};
14- II. 剪绳子 II
class Solution {
public:
    int cuttingRope(int n) {
     if(n==1) return 0;
     if(n==2) return 1;
     if(n==3) return 2;
     if(n==4) return 4;
     long long res=1;
     while(n>4){
         res %=1000000007;
         res = res*3;
         n=n-3; 
     }
     if(n==4) res = (res*4)%1000000007;
     if(n==3) res = (res*3)%1000000007;
     if(n==2) res = (res*2)%1000000007;
     return int(res);
    }
};
15. 二进制中1的个数
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int num=0;
        while(n){
            num++;
            n = (n-1)&n;
        }
        return num;
    }
};

本文链接: http://www.dtmao.cc/news_show_700116.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?