搜索

剑指offer等算法总结归类

gecimao 发表于 2019-07-01 13:20 | 查看: | 回复:

  两个指针,第一个先走k步,第二个不动,然后第一个和第二个一起走,知道第一个到尾节点。

  思路:两个链表先比较头,头比较小的做新链表的头,新链表的next递归调用本函数。

  思路:三步走。第一步:连接到后面。第二步:构建随机指针。第三部:拆除连接

  最后记得把pClonedNode赋值给一个pClonedHead保存头结点。用于最后的返回。

  思路:分别遍历两个链表,得到他们的长度差,然后长链表走这个差值的步数。然后长链表和短链表一起走,直到它们碰到,返回。

  思路:用两个指针,一个快指针一下走两步,一个慢指针,一下走一步。然后走着直到它们相遇。然后把慢指针从头走,快指针一步一步走,直到它们相遇就是环的入口节点。

  思路:特别要注意需要保存节点到一个ListNode中,以防后面修改移动后找不到指针。需要Pre节点一个。指向前一个节点,pNode指向当前节点。由于当前节点的前一个是没有的,所以创建一个头节点val为-1.然后把它指向node。

  思路:从最右边最上边开始比较,target比之大,row++;比之小,col--,否则返回true

  6. 题目描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

  思路:本题考查二分查找。两个下标,一头一尾,循环条件是while(array[index1]=array[index2])循环结束条件是index2-index1==1.循环的过程中要不停的创建数组的重点,不停的去二分查找,如果中点值大于等于前半部分(隐含的条件是大于第二部分),那么中点的值就位于第一部分,第一部分的下标就要变换为mid。同理,如果中点值小于第一部分并且小于等于第二部分,那中点值一定位于第二部分,对于特殊情况,如// 3 3 3 0 3, 3 0 0 0 3两种情况无法判断哪个属于旋转部分。就需要通过普通的办法来查找。

  思路1:借助一个辅助数组,遍历第一遍把奇数放进去,第二遍把偶数放进去,再传递给原来的数组。

  思路:遍历数组的时候保存两个值,一个是数组中的一个数字,另一个是次数。但我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,次数加一,不同次数减一:如果次数为0,那么我们需要保存下一个数字,并把次数设为1,有与我们要找的数字出现的次数比其他的数字次数之和还要多,MAME要找的数字肯定是最后一次吧次数设为1对应的数字。另外要验证该数字是否大于长度的一半。

  30.题目描述:HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?(子向量的长度至少是1)(连续子数组的最大和)

  思路:两个变量,一个存当前的和,另一个存最大值,然后遍历数组,如果curSum小于0,就等于当前数组的值,否则就curSum+=num【i】,如果curSum比max大的线.题目描述:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

  35.题目描述:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

  40.题目描述:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

  思路:所有数组元素的异或结果就是两个出现一次的数字的异或结果,所以把这两个数字分别划分到两个数组里,每个数组的异或结果就是这个数,划分规则是根据第一次出现1的位数那一位是0还是1。例如数组{2,4,3,6,3,2,5,5}异或的结果是0010,我们就根据倒数第二位是0还是1来划分。注意位数是从后往前的。

  41.题目描述:小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

  思路:有点类似二分查找或者partition过程,不同的是,两个指针一个是从头开始,另一个从第二个元素开始。记录small+big的和为cursum,如果这个值等于要求的sum和的话,那么就找到一个,small++;如果小于sum那么big++,cursum也要加上big处的数,大于的话small也要++,但是cursum要把small去掉,这个时候可能就到了边界,注意此处的边界是mid=()sum+1)/2,从1和2开始循环

  42.题目描述:输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

  50.题目描述:在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。

  从代码上看,第一个正序,第二个从后往前,注意第二次计算顺带把第一个的带进去了,result数组的最后一个值和C数组的最后一个值是相等的,看图就明白了。

  {2,3,4,2,6,2,5,1}分析,主要要用到双端队列,在java中就是linkedList,数组的第一个数字是2,存入队列。第二个数字是3,由于它比前一个数字2大,因此2不可能成为滑动窗口的最大值。先把2从队列里删除,再把3存入队列。什么时候结束呢,当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时,这个数字已经从窗口划出,可以从队列中删除了。

  45.题目描述:从扑克牌中随机抽5张牌,判断是不是一个顺子,即这五张牌是不是连续的。A为1,J为11,大小王可以看成是任意数字。

  2.题目描述:请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy

  27.题目描述:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

  34.题目描述:在一个字符串(1=字符串长度=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。如果字符串为空,返回-1

  一个哈希表,没有的线.题目描述:汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

  思路:主要是一个头尾互换函数不停的调用。先整体调用。然后分出的两块分别调用。

  44.题目描述:牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

  注意:思路是result=result*10+c-0;但是要注意第一个字符有正负号的情况,下标要移动,如果第一个是+或者-但是长度只有1也要返回0;遍历的过程中也要判断是否在0-9中间。

  表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串aaa与模式a.a和ab*ac*a匹配,但是与aa.a和ab*a均不匹配。

  思路:主要分为两种情况:模式的第二个字符(1)是*(2)第二个不是*,然后再分情况递归调用,移动下标。

  53.题目描述:请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串+100,5e2,-123,3.1416和-1E-16都表示数值。 但是12e,1a3.14,1.2.3,+-5和12e+4.3都不是。

  65.题目描述:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如[a b c e s f c s a d e e]是3*4矩阵,其包含字符串bcced的路径,但是矩阵中不包含“abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

  思路:回溯法,不停的往前走两层循环,里面用递归,回溯,分别取i-1,i+1,j-1,j+1,k取下一个字符,暴力遍历,即可,如果访问成功记得修改flag

  4.题目描述:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回(递归)思路:先把中序遍历的下标,健为中序中的数字,值为下标放入hashmap中。主要是下标变换.先建立根节点,root.left=递归调用。root.rigth=递归调用。

  17.题目描述:输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

  思路:先判断根是否相等,相等的话再比较左孩子和右孩子,左右的比较肯定是递归。当然不是的话,我们还要把左孩子和root2树做同样的对比。

  思路:把节点放一个队列里(linnkedList)有左子树就把左子树放入,有右子树就把右子树放入队列,然后再依次弹出,入队和出队是同在一个循环里面的。出队的时候放入ArrayList中。,要是有左右孩子就要把左右孩子依次放入队列。整体看就是出队的时候伴随着入队。出队的元素就是以前入队形成的。

  思路:总体是递归思路。首先要想清楚二叉搜索树的性质:所有的左子树的值小于根节点的值,所有的右子树的值大于根节点。后序遍历的特点是:根节点在最后。

  24.题目描述:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

  思路:总体递归思路。两个ArrayList一个放所有路径,一个放一条当前路径。需要用到递归,每当到叶子节点时候就要判断是否等于target,target递归的过程中不停的变换,findPath(root,target)target不不停的减去root值。开始的时候要把root.val放进去。最后到叶子节点记得把road(当前路径的list)的最后一个元素删掉(如果等于已经添加进roads里面了,如果没有找到就把最后一个值舍去,然后返回上一层节点)

  思路:要注意点一点是要把T初始的TreeNode赋值给一个变量Head。然后递归调用,左节点去找,有节点去找。然后找到左孩子的最右边节点和右孩子最左边节点。然后把根节点和左孩子最右节点相连,右孩子最左和根节点相连。最后返回Head。

  思路:递归。哪个孩子的深度大,就把这个深度加上自己本身的1,就是实际的深度。

  思路:与上题思路基本相同。但是要加上一句,if左右孩子深度差超过1,那么return false。

  思路:一个节点如果有右孩子,那么它的中序遍历的下一个节点就是它的右孩子的最左边的节点,如果没有右孩子,它的中序遍历的下一个节点就需要:通过next向上遍历直到它是它父节点的左孩子为止。

  思路:准备两棵一模一样的树,这个题来说就是第一颗树的左孩子和第二课树的左孩子对称并且,第一棵树的右孩子和第二棵树的左孩子对称。然后递归,注意跳出循环的条件。

  思路:准备两个栈(linkedList或者Stack),一个放正序TreeNode,另一个放逆序TreeNode,正序弹出来的时候,按从左到右的顺序压入,然后逆序栈弹出的就是逆序,然后按从右往左的顺序压栈,两个栈相互交替完成。然后每次循环需要一个list。用来添加一行的数字。(注意循环条件,当任意一个不为空就可以循环)

  思路:与上一题有点像,不同的是此处只需要一个数据结构,一个队列即可。需要准备一个num遍历存储队列的大小,当num0时候要不停的出队,当然出队的同时它的孩子也要分别入队。其他操作基本相同。另外,队列使用linkedList。(队列和栈都可以使用)

  思路:序列化是TreeNode到String字符串的过程,反序列化反之。注意用先序遍历。

  62.题目描述:给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

  思路:总体思路是中序遍历,左中右,然后递归,左边如果找到了那么return,右边找到了右边return。中间是index++;然后if(index==k)return pRoot;

  5.题目描述:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。思路:push直接进第一个栈,出栈的线不为空才出,为空的线.题目描述:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

  思路:准备两个栈,第一个放其他元素,第二个放最小元素,push过程中,如果minStack为空或者新元素比minStack的栈顶元素小,则把新元素push进去,然后把新元素push进第一个栈。pop过程中,如果第一个栈弹出的元素和minStack的栈顶元素相同,则需要把minStack元素和第一个栈的元素一并弹出。

  21.题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

  思路:准备一个辅助栈。先压入第一个要压入的元素。如果下一个要弹出的元素不等于栈顶,则要压栈,直到找到下一个要弹出的元素,如果下一个要弹出的元素等于栈顶元素,直接pop弹出。如果到最后都没找到就返回false。要注意两个下标:一个是pop数组的,这个是整个for循环的下标,另一个是push数组的下标,这个index是push数组有没有到头的一个标志。

  11.题目描述:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

  思路:start为起点,由于起点始终都是0,0或者1,1这种,相当于0,0的位置,注意循环条件是rowsstart*2&&colsstart*2,向下打印的时候,需要加入判断:endYstart,向左的时候:endYstart&&endxstart 向上的时候:endystart+1&&endxstart。另外需要注意的是,转一圈,也就是循环一次,start要加一。并且每次endx=cols-1-start,endy=rows-1-start;65.题目描述:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如[a b c e s f c s a d e e]是3*4矩阵,其包含字符串bcced的路径,但是矩阵中不包含“abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

  63.题目描述:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

  33.题目描述:把只包含素因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

  思路:2、3、5分别有自己的一个下标,每一个丑数都是另一个丑数乘以2/3、或者5。要用自己下标处的值乘以自己的2/3、或者是5,然后找他们中间的最小值放入list中,如果这个最小值和刚才得到的数字相等的话,那么下标就++。

  需要的辅助空间:三个num保存有可能进入到list中的丑数,三个index保存2/3/5的下标,一个Arraylist保存结果。

本文链接:http://windsorflowers.net/diguixiangliang/311.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部