算法 - CSDN
算法 订阅
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中的指令描述的是一个计算,当其运行时能从一个初始状态和(可能为空的)初始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。 展开全文
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中的指令描述的是一个计算,当其运行时能从一个初始状态和(可能为空的)初始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。
信息
特    征
有穷性 确切性 输入 输出 可行
常    用
计算、数据处理和自动推理
外文名
Algorithm
中文名
算法
学    科
数学 计算机
算法特征
一个算法应该具有以下五个重要的特征:(Finiteness)算法的有穷性是指算法必须能在执行有限个步骤之后终止;(Definiteness)算法的每一步骤必须有确切的定义;(Input)一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;(Output)一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)。
收起全文
  • 本门课程作为算法面试系列的第一季,会从“知己知彼”的角度,聊聊关于算法面试的那些事~ 【哪些人适合学习这门课程?】 求职中的开发者,对于面试算法阶段缺少经验 ...
  • 数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。
  • Java经典算法讲解

    2019-06-24 11:57:47
    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法...
  • 《经典算法大全》是一款IOS平台的应用。里面收录了51种常用算法,都是一些基础问题。博主觊觎了好久,可悲哀的是博主没有苹果,所以从网上下了老奔的整理版并且每个都手敲了一遍。 虽然网上也有博客贴了出来,但是...

    《经典算法大全》是一款IOS平台的应用。里面收录了51种常用算法,都是一些基础问题。博主觊觎了好久,可悲哀的是博主没有苹果,所以从网上下了老奔的整理版并且每个都手敲了一遍。

    虽然网上也有博客贴了出来,但是自己写写感觉总是好的。现在分享个大家。

    代码和运行结果难免有出错的地方,请大家多多包涵。

     

    1.河内之塔(汉诺塔

    2.费式数列

    3.巴斯卡三角形

    4.三色棋

    5.老鼠走迷宫(1)

    6.老鼠走迷宫(2)

    7.骑士走棋盘

    8.八皇后

    9.八枚银币

    10.生命游戏

    11.字串核对

    12.双色河内塔三色河内塔

    13.背包问题 

    14.蒙地卡罗法求PI

    15.Eratosthenes筛选求质数

    16.超长整数运算(大数运算)  同时建议参考这篇文章:大数的四则运算-海子的博客园

    17.长PI

    18.最大公因数,最小公倍数,因式分解

    19.完美数

    20.阿姆斯壮数

    21.最大访客数

    22.中序转后序式(前序式  相关文章:中缀表达式值问题

    23.后序式运算 

    24.洗扑克牌(乱数排列)

    25.Craps赌博游戏

    26.约瑟夫问题

    27.排列组合   相关文章:母函数与排列组合

    28.格雷码(Gray Code)

    29.产生可能的集合  相关文章:集合划分问题

    30.m元素集合的n个元素子集

    31.数字拆解

    32.得分排行

    33.选择,插入,冒泡排序

    34.shell 排序法-改良的插入排序

    35.shaker排序法-改良的冒泡排序

    36.改良的选择排序

    37.快速排序法一

    38.快速排序法二

    39.快速排序法三

    40.合并排序法

    41.基数排序法

    42.循环搜寻法(使用卫兵)

    43.二分搜寻法(二分查找法,折半查找法)  相关文章:二分查找

    44.插补搜寻法

    45.费式搜寻法

    46.稀疏矩阵

    47.多维矩阵转一维矩阵

    48.上三角,下三角,对称矩阵

    49.奇数魔方阵

    50.4N魔方阵

    51.2(2N+1)魔方阵

     

    展开全文
  • 10大计算机经典算法

    2017-06-01 17:00:39
    算法一:快速排序法    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常...
    算法一:快速排序法                            

          快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

    快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

    算法步骤:                  

    1 .从数列中挑出一个元素,称为 “基准”(pivot),

    2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

       

    算法二:堆排序算法                            

     堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    堆排序的平均时间复杂度为Ο(nlogn) 。

    算法步骤:

    1.创建一个堆H[0..n-1] 

    2.把堆首(最大值)和堆尾互换

    3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

    4. 重复步骤2,直到堆的尺寸为1

                               

    算法三:归并排序                            

     归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    算法步骤:

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

    4. 重复步骤3直到某一指针达到序列尾

    5. 将另一序列剩下的所有元素直接复制到合并序列尾

                              

    算法四:二分查找算法                            

       二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为Ο(logn) 。                            

    算法五:BFPRT(线性查找算法)                            

     BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂度,五位算法作者做了精妙的处理。

    算法步骤:

    1. 将n个元素每5个一组,分成n/5(上界)组。

    2. 取出每一组的中位数,任意排序方法,比如**排序。

    3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

    4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

    5. 若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。

    终止条件:n=1时,返回的即是i小元素。                          

    算法六:DFS(深度优先搜索)                            

     深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

    深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。


    深度优先遍历图算法步骤:

    1. 访问顶点v;

    2. 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

    3. 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

    上述描述可能比较抽象,举个实例:

    DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,… 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。

    接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。                            

    算法七:BFS(广度优先搜索)                            

      广度优先搜索算法(Breadth-First-Search),是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

    算法步骤:

    1. 首先将根节点放入队列中。

    2. 从队列中取出第一个节点,并检验它是否为目标。

    • 如果找到目标,则结束搜寻并回传结果。

    • 否则将它所有尚未检验过的直接子节点加入队列中。

    3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

    4. 重复步骤2。

                               

    算法八:Dijkstra算法                            

     戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

    该算法的输入包含了一个有权重的有向图 G,以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。(uv) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合,而边的权重则由权重函数 wE → [0, ∞] 定义。因此,w(uv) 就是从顶点 u 到顶点 v 的非负权重(weight)。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重,就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t,Dijkstra 算法可以找到 s 到 t的最低权重路径(例如,最短路径)。这个算法也可以在一个图中,找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。

    算法步骤:

    1. 初始时令 S={V0},T={其余顶点},T中顶点对应的距离值

    若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值

    若不存在<V0,Vi>,d(V0,Vi)为∞

    2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S

    3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值

    重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止

                           

    算法九:动态规划算法                            

     动态规划(Dynamic programming)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

    动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

    关于动态规划最经典的问题当属背包问题。

    算法步骤:

    1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

    2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。                            

    算法十:朴素贝叶斯分类算法                            

    朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下,如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。

    朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学**的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。


    尽管是带着这些朴素思想和过于简单化的假设,但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

    展开全文
  • 面试题20. 表示数值的字符串 本题的题目描述比较简单,例子比较少,解法也有多种,比如DFA确定有限状态机(然鹅我不会,回头再去了解了解),那咋办呢,有个投机取巧的方法就是正则表达式匹配直接调用库函数,那就...

    面试题20. 表示数值的字符串

    在这里插入图片描述
    本题的题目描述比较简单,例子比较少,解法也有多种,比如DFA确定有限状态机(然鹅我不会,回头再去了解了解),那咋办呢,有个投机取巧的方法就是正则表达式匹配直接调用库函数,那就不说了。正常的解法那就按照题目的意思和规则办,有啥情况就分析啥情况,走一步看一步就完事。
    代码如下(思路在注释):

    class Solution {
    public:
        bool isNumber(string s) {
            if(s.empty() || s==" ") return false;
            int l =s.find_first_not_of(' ');//去掉前边的空格
            int start = l;
            int r =s.find_last_not_of(' ');//去掉后边的空格
            bool numflag = false;//数值标记
            bool eflag = false;//指数标记
            bool dotflag = false;//点标记
            for(;l<=r; ++l)
            {
                if(isdigit(s[l]))
                    numflag = true;
                else if(s[l]=='.')
                {
                    //.之前不能出现e或者.
                    if(dotflag || eflag)
                        return false;
                    dotflag = true;
                }else if(s[l]=='e' || s[l]=='E')
                {
                    //E之前不能出现E,且必须有数字
                    if(eflag || !numflag)
                        return false;
                    eflag = true;
                    numflag = false;//重置数字标志
                }else if(s[l]=='+' || s[l]=='-')
                {
                    //+-号必须在第一个位置或者在E之后的第一个位置
                    if(l!=start && s[l-1]!='e' && s[l-1]!='E')
                        return false;
                }else
                    //其余不合法字符
                    return false;
            }
            return numflag;
        }
    };
    

    面试题21. 调整数组顺序使奇数位于偶数前面

    在这里插入图片描述
    解法1:双指针

    class Solution {
    public:
        vector<int> exchange(vector<int>& nums) {
            //双指针法
            int lo = 0, hi = nums.size()-1;
            while(lo<hi)
            {
                while(lo<hi && (nums[lo]&1))
                    ++lo;
                while(lo<hi && (nums[hi]&1)==0)
                    --hi;
                swap(nums[lo],nums[hi]);
            }
            return nums;
        }
    };
    

    解法2:快慢指针

    class Solution {
    public:
        vector<int> exchange(vector<int>& nums) {
            //快慢指针
            int slow = 0, fast = 0;
            while(fast<nums.size())
            {
                if(nums[fast]&1)
                    swap(nums[slow++],nums[fast]);
                ++fast;
            }
            return nums;
        }
    };
    

    面试题22. 链表中倒数第k个节点

    在这里插入图片描述
    思路:1、最直接的想法肯定是遍历一遍链表,然后统计节点个数n,然后从头节点开始顺序遍历,向前进n-k个节点,即到达倒数第k个节点,这样的情况下需要顺序遍历两次链表,因此时间复杂度有O(n^2),效率是较低的;2、链表的遍历思想中很容易想到一种思路,即双指针或者是快慢指针,本题可以引用双指针,初始化两个指针起始都指向头指针,然后指针p2先走k步,然后p1,p2在同时前进直到p2到达链表尾端,此时p1即倒数第k个节点,这样实际上只需要遍历一遍链表,即p2从头走到了尾,因此时间复杂度降低到O(n)。

    class Solution {
    public:
        ListNode* getKthFromEnd(ListNode* head, int k) {
            auto p1 = head;
            auto p2 = head;
            while(k--)
            {
                p2 = p2->next;
            }
            while(p2)
            {
                p2=p2->next;
                p1=p1->next;
            }
            return p1;
        }
    };
    

    面试题24. 反转链表在这里插入图片描述

    解法1:递归

    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            //递归法
            if(!head || !head->next) return head;
            ListNode* newhead = reverseList(head->next);
            head->next->next = head;
            head->next = nullptr;
            return newhead;
        }
    };
    

    解法2:双指针

    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            //双指针
            ListNode* pre = nullptr, *cur = head;
            while(cur)
            {
                auto post = cur->next;
                cur->next = pre;
                pre = cur;
                cur = post;
            }
            return pre;
        }
    };
    

    面试题25. 合并两个排序的链表在这里插入图片描述

    思路:整体思想和归并排序一样,定义一个伪头部dummy_head与一定前驱节点pre,然后对l1和l2两个链表进行遍历归并,直至某一链表值为空,最后再将非空的链表接上即可。

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            //伪头结点法
            ListNode* dummy_head = new ListNode(-1);
            auto pre = dummy_head;
            while(l1 && l2)
            {
                if(l1->val<=l2->val)
                {
                    pre->next = l1;
                    pre = l1;
                    l1 = l1->next;
                }else
                {
                    pre->next = l2;
                    pre = l2;
                    l2 = l2->next;
                }
            }
            if(!l1) pre->next = l2;
            else pre->next = l1;
            return dummy_head->next;
        }
    };
    

    面试题26. 树的子结构

    在这里插入图片描述
    解题思路:递归求解,1、定义一个辅助函数helper(),去判断两棵树是否相等;2、对树A进行遍历 ,以每一个节点为根节点的树与树B是否相等,如果存在相等,即B为A的子树。
    代码如下:

    class Solution {
    public:
        bool isSubStructure(TreeNode* A, TreeNode* B) {
            //递归
            if(!B || !A) return false;
            if(A->val==B->val)
                if(helper(A,B)) return true;
            return isSubStructure(A->left,B) || isSubStructure(A->right,B);
        }
    private:
        bool helper(TreeNode* A, TreeNode* B)
        {
            if(!B) return true;
            if(!A && B) return false;
            if(A->val!=B->val) return false;
            return helper(A->left,B->left) && helper(A->right,B->right);
        }
    };
    

    面试题27. 二叉树的镜像(翻转二叉树)

    在这里插入图片描述
    解法1:递归

    class Solution {
    public:
        TreeNode* mirrorTree(TreeNode* root) {
            //递归法
            if(!root) return root;
            auto left = mirrorTree(root->left);
            auto right = mirrorTree(root->right);
            root->left = right;
            root->right = left;
            return root;
        }
    };
    

    解法2:辅助队列

    class Solution {
    public:
        TreeNode* mirrorTree(TreeNode* root) {
            //队列
            if(!root) return root;
            queue<TreeNode*> q;
            q.push(root);
            while(!q.empty())
            {
                auto cur = q.front();
                q.pop();
                auto tmp = cur->left;
                cur->left = cur->right;
                cur->right = tmp;
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            return root;
        }
    };
    

    今日刷题笔记顺利完成,今日更多的题目是关于链表与树的内容,因此有许多的递归应用。同时也能感觉到链表中常用的方法:双指针可以优化链表的遍历或操作。明日继续!!!

    展开全文
  • 新的一天,新的开始!!! 面试题15.... 思路:本题主要考察的是一个位运算。主要解题思路有两种:1、位与&运算,对于n&1如果为1,即末位是1,否则为0,借助这个思路,可以对n的没一位,按位与1进行判断,为1则...

    新的一天,新的开始!!!

    面试题15. 二进制中1的个数

    在这里插入图片描述
    思路:本题主要考察的是一个位运算。主要解题思路有两种:1、位与&运算,对于n&1如果为1,即末位是1,否则为0,借助这个思路,可以对n的没一位,按位与1进行判断,为1则cnt++,然后将n右移一位,直至n为零;2、方法二需要一些技巧:即n&(n-1)这个操作,这个操作会将n的最右侧的1置零,这样逐位将n的最右侧的1置零并统计个数,直至n为0即可。
    代码如下:

    class Solution {
    public:
        int hammingWeight(uint32_t n) {
            //法2:巧用n&(n-1)
            int cnt = 0;
            while(n)
            {
                ++cnt;
                n &=n-1;
            }
            return cnt;
       
            /*/法1:逐位统计
            int cnt = 0;
            while(n)
            {
                if(n&1) cnt++;
                n >>=1;
            }
            return cnt;*/
        }
    };
    

    面试题16. 数值的整数次方

    在这里插入图片描述
    思路:本题比较好的方法为快速幂。详见百科:快速幂
    代码如下:

    class Solution {
    public:
        double myPow(double x, int n) {
            //思路:快速幂
            if(n==0) return 1;
            long long k = n;//极端情况INT_MIN求相反数时会溢出,所以需要用long long
            double res = 1.0;
            if(k<0)//处理指数为负的情况
            {
                k = -k;
                x = 1/x;
            }
            while(k)
            {
                if(k&1) res *= x;//如果指数为奇数,即需要额外乘以一个x
                x *= x;
                k >>= 1;
            }
            return res;
        }
    };
    

    面试题17. 打印从1到最大的n位数

    在这里插入图片描述
    此处是leetcode上的题目解法,与《剑指offer》书中愿意差别较大,原书中考查的是大数打印的问题,而leetcode上的题目却没体现,因此后序会贴出大数打印的思路及代码。

    class Solution {
    public:
        vector<int> printNumbers(int n) {
            //leetcode题意
            vector<int> res;
            if(!n) return res;
            for(int i=1, max=pow(10,n); i<max; ++i)
                res.push_back(i);
            return res;
        }
    };
    

    大数打印代码如下:

    class Solution{
    
    public:
    	vector<int> printNumbers(int n){
    		if(n<=0) return res;
    		string number(n,'0');
    		while(!Increment(number))
    			saveNumber(number);
    		return res;
    	}
    private:
    	vector<int> res;
    	bool Increment(string& number)
    	{
    		bool isoverflow = false;//越界标记
    		int carrybit = 0;//存储进位
    		int len = number.size();
    		for(int i=len-1; i>=0; --i)
    		{
    			int tmp = number[i] - '0' + carrybit;
    			if(i==len-1)//如果是末位数,则+1
    				++tmp;
    			if(tmp>=10)//存在进位情况
    			{
    				if(i==0)//最大位存在进位,即超过最大值了
    					isoverflow = true;
    				else//处理进位,同时更新该位置的值
    				{
    					carrybit = 1;
    					number[i] = tmp - 10 + '0';
    				}
    			}else//没有进位发生
    			{
    				number[i] = tmp+'0';
    				break;//没有进位可以直接跳出循环
    			}
    		}
    		return isoverflow;
    	}
    	void saveNumber(const string& number)
    	{
    		auto index = number.find_first_not_of('0');
    		if(index!=string::npos)
    			res.push_back(stoi(number.substr(index)));
    	}
    };
    

    面试题18. 删除链表的节点

    在这里插入图片描述
    本题也可只用单指针即可。此外,此题在《剑指offer》书中的原题是给定一个已知的单链表节点,要求在O(1)时间内删除该节点。大致思想是:由于删除链表的节点最先想到一定是找到删除节点的前驱节点,然后将待删除节点的后继成为前驱节点的后继即可。但是单向链表往往需要顺序遍历才能找到前驱节点,因此需要消耗O(n)时间,那如何实现O(1)找到前驱节点呢?换个思路,如果我们把待删除节点的后继的值复制给待删除节点,则相当于把后继节点成为了前驱节点的后继,随后只需要删除后继节点值即可。

    class Solution {
    public:
        ListNode* deleteNode(ListNode* head, int val) {
            //双指针法
            if(!head) return nullptr;
            if(head->val==val) return head->next;
            auto pre = head;
            auto cur = head->next;
            while(cur)
            {
                if(cur->val==val)
                {
                    pre->next = cur->next;
                    break;
                }else
                {
                    pre = cur;
                    cur = cur->next;
                }
            }
            return head;
        }
    };
    

    面试题19. 正则表达式匹配

    在这里插入图片描述
    递归解法(思路都在注释):

    class Solution {
    public:
        bool isMatch(string s, string p) {
            return isMatch(s.c_str(),p.c_str());
        }
        //为了方便判断串尾,将string转换成C风格字符串更好处理
        bool isMatch(const char*s, const char* p)
        {
            //递归出口,如果串p到达了尾部,则判断串s是否也到达尾部,不是则不能匹配,是说明可以完全匹配
            if(*p==0) return *s==0;
            //判断文本串s的是否到串尾或能否和模式串匹配
            auto fisrt_match = *s && (*s==*p || *p=='.');
            //如果*(p+1)=='*',则分两种情况
            if(*(p+1) == '*')
                return isMatch(s,p+2)//情况1:当前s和p不匹配,递归尝试s和p+2是否匹配,即*代表零个*p 
                || (fisrt_match && isMatch(++s,p));//情况2:如果当前已经匹配过了,即fisrs_match为真,则尝试++s和p是否匹配,即*号尝试更多的匹配
            else
                return fisrt_match && isMatch(++s,++p);//如果当前已经匹配了,且后续不是*号,则两个串都前移再继续尝试匹配
        }
    };
    

    动态规划解法:

    class Solution {
    public:
        bool isMatch(string s, string p) {
           //动态规划
           int slen = s.size(),plen = p.size();
           if(slen==0 && plen==0) return true;
           //dp[i][j]表示文本串s的前i个字符和模式串p的前j个字符能否匹配
           vector<vector<bool>> dp(slen+1,vector<bool>(plen+1,false));
           dp[0][0] = true;//空串一定匹配
           //处理文本串为空的情形
           for(int j=1; j<=plen; ++j)
           {
               //j==1,首字符一定是字母,所以肯定不能与空串匹配
               if(j==1) dp[0][j] = false;
               //如果p[j-1]=='*',则可以判断,j-1和j-2处两个字符是不影响匹配的
               //因此,dp[0][j]能否匹配取决于[0,j-2]能否匹配,即dp[0][j] = dp[0][j-2]
               if(p[j-1]=='*' && dp[0][j-2]) dp[0][j] = true;
           }
            //当文本串s不为空
            for(int i=1; i<=slen; ++i)
                for(int j=1; j<=plen; ++j)
                {
                    //第一种匹配情况:两个字符相等或者p[j-1]=='.'
                    if(s[i-1]==p[j-1] || p[j-1]=='.')
                        //当前两个可以匹配,则其匹配结果与dp[i-1][j-1]一样
                        dp[i][j]=dp[i-1][j-1];
                    //如果模式串p的字符是*,则需要回到*的前一个字符看能否匹配
                    else if(p[j-1]=='*')
                    {
                        if(j<2) dp[i][j]=false;
                        //如果j-2的字符能和i-1的字符匹配
                        if(p[j-2]==s[i-1] || p[j-2]=='.')
                            // 此时存在两种情况,即所谓的*号能匹配的第j-2个字符的个数:可能匹配0个,也可能匹配多个
                            //情况1:如aab aabb*此时i=3,j=5,此时j-1是*,j-2是b,J-1和i-1都是b可以匹配,但是在此之前
                            //      即i=3,j=3时,也就是aab aab时他们已经完成了匹配即dp[3][3]为true,因此这个*号不需要任何匹配
                            //      即dp[i][j] = dp[i][j-2]即可。
                            //情况2:如果需要匹配多个,则存在这种情形aabb aab*
                            //      此时i=4,j=4,我们需要匹配dp[i][j],由于p[j-2]==s[i-1]
                            //      那由于i,j是内外循环,因此到i=4,j=4的时候一定进行过i=3,j=4的匹配判断,所以我们可以忽略第4个b
                            //      转而继续往前寻求更多的b和当前的串匹配,即dp[4][4] = dp[3][4]即aab与aab*匹配情况
                            //      又因为p[j-2]==s[i-2],即第3个b仍然匹配,因此我们继续相同的操作,忽略第3个b,继续往前
                            //      即dp[4][4] = dp[3][4] = dp[2][4],即aa与aab*的匹配而这种情形当然依然遍历过了
                            dp[i][j] = dp[i-1][j] || dp[i][j-2];
                        //如果j-2与i-1字符不能匹配,则丢弃j-1,j-2两个字符
                        //此时能否匹配则取决于前j-2个字符,即dp[i][j]=dp[i][j-2]
                        else
                            dp[i][j] = dp[i][j-2];
                    }
                    //其他情况下都是不可能匹配
                    else
                        dp[i][j]=false;               
                }
            return dp[slen][plen];
        }
    };
    

    今日的刷题笔记顺利完成,正则表达式匹配确实值得多看几遍,这算是遇到的第三遍,写起来还是有一些小的bug没能顺利通过,还需要看答案,还需要继续提高!!!

    展开全文
  • 思路1:在许多的算法与数据结构的书籍中,讲到递归的时候免不了肯定讲斐波那契数列,这是一个很典型的递归过程,写法很简单,但是很明显的缺点是递归中重复计算的部分很多,可以采用记忆化递归改进,如果没有优化,...
  • 面试题38. 字符串的排列 方法1;交换回溯法(时间消耗比较爆炸) class Solution { public: vector<string> permutation(string s) { //交换回溯法 backtrack(s,0);... void backtrack(string s,int idx)
  • 大神的算法学习之路

    2018-10-29 18:30:58
    严格来说,本文题目应该是我的数据结构和算法学习之路,但这个写法实在太绕口——况且CS中的算法往往暗指数据结构和算法(例如算法导论指的实际上是数据结构和算法导论),所以我认为本文题目是合理的。 原文链接:...
  • 什么是算法

    2016-12-14 10:56:36
    什么是算法 1、什么是算法 算法(algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。 mark:我们...
  • A*算法

    2018-08-21 10:10:22
    一、算法介绍 A*算法常用于二维地图路径规划,算法所采用的启发式搜索可以利用实际问题所具备的启发式信息来指导搜索,从而减少搜索范围,控制搜索规模,降低实际问题的复杂度 。 二、算法原理 A*算法的原理是设计一...
  • 十大基本算法介绍

    2019-05-23 17:55:20
    一、算法概述: 1.算法分类: 十种常见算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能超过Q(nlogn),因此也称为非线性时间比较类排序。 非比较类排序:不通过比较来...
  • 算法设计之五大常用算法设计方法总结 一、【分治法】  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的...
  • 由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,...
  • 算法

    2018-11-21 00:29:20
    1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出...
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • 算法的时间复杂度和空间复杂度 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的...
  • 主要介绍MP(Matching Pursuits)算法和OMP(Orthogonal Matching Pursuit)算法[1],这两个算法虽然在90年代初就提出来了,但作为经典的算法,国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用,并未对其...
  • 10分钟搞懂遗传算法

    2018-01-24 20:57:27
    大自然有种神奇的力量,它能够将优良的基因保留下来,从而...本文先跟大家介绍遗传算法的基本思想,然后用遗传算法来解决一个实际问题,最后给出遗传算法的代码实现和解析。废话不多说,现在就开始吧~ 遗传算法
1 2 3 4 5 ... 20
收藏数 3,243,670
精华内容 1,297,468
热门标签
关键字:

算法