JZ16数值的整数次方 描述 实现函数doublePower(doublebase,intexponent)，求base的exponent次方。 注意： 1.保证base和exponent不同时为0。 2.不得使用库函数，同时不需要考虑大数问题 3.有特殊判题，不用考虑小数点后面0的位数。 方法1 思路 既然是求次方，那我们做不断累乘就可以了，重点是处理负的次方数 具体做法： step1：先处理次方数为负数的情况，将底数化为分数解决。 step2：遍历次方数的次数，不断累乘底数。 代码 publicdoublePower(doublebase,intexponent){ if(expo...

JZ21调整数组顺序使奇数位于偶数前面(一) 描述 输入一个长度为n整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 思路： 既然要把所有的奇数放在数组前面，所有的偶数放在数组后面，那可以统计奇数在原数组中出现了多少次，这样就可以找到二者的分界线。 有了分界线以后，前面就是奇数，后面就是偶数，可以利用两个指针分别指向二者的开头，遇到一个元素就添加到相应位置，然后指针移动。 具体做法： step1：遍历数组，统计奇数出现的次数，即找到了偶数开始的位置。 step2：准备一个和原数组...

JZ23链表中环的入口结点 描述 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。 解析 环很大 在前面我们提到过快慢指针，判断是否有环。如果有环，在来找环的入口。如果没环直接返回null即可，我们假设是有环的，那么会有两种情况，一种是O型，一种是6型，其实原理都一样，这里主要看一下6字型的环，他会有两种情况， 如果有环，那么快指针走过的路径就是图中a+b+c+b，慢指针走过的路径就是图中a+b，因为在相同的时间内，快指针走过的路径是慢指针的2倍，所以这里有a+b+c+b=2(a+b)，整理得到a=c 在相遇的时候再使用两个指针，一个从链表起始点开始，一个从...

JZ26树的子结构 描述 输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构） 假如给定A为{8,8,7,9,2,,,,,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构 题解1深度遍历 思路 既然是要找到A树中是否有B树这样子树，如果是有子树肯定是要遍历这个子树和B树，将两个的节点一一比较，但是这样的子树不一定就是A树根节点开始的，所以我们还要先找到子树可能出现的位置。 既然是可能的位置，那我们可以对A树的每个节点前序递归遍历，寻找是否有这样的子树，而寻找是否有子树的时候，我们就将A树与B树同步前序遍历，依次比较节点值。 具体做法： ...

JZ31栈的压入、弹出序列 描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。 1.0<=pushV.lengthpopV.length<=1000 2.-1000<=pushV[i]<=1000 3.pushV的所有数字均不相同 方法1辅助栈（推荐使用） 思路： 题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列...

JZ33二叉搜索树的后序遍历序列 描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。 提示： 1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。 2.该题我们约定空树不是二叉搜索树 3.后序遍历是指按照“左子树-右子树-根节点”的顺序遍历 思路 BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x（也就是根），如果去掉最后一个元素的序列为T， 那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x， 且这两段（子树）都是合法的后序...

JZ34二叉树中和为某一值的路径(二) 描述 输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n 思路 当前的路径path要更新 当前的目标值expectNumber要迭代，减去当前节点的值 若当前节点是叶子节点，考虑是否满足路径的期待值，并考虑是否将路径添加到返回列表中 具体做法： step1：维护两个向量ret和path step2：编写递归...

JZ36二叉搜索树与双向链表 描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表 注意: 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出双向链表，程序会根据你的返回值自动打印输出 思路： 二叉树中序遍历除了递归方法，我们还可以尝试非递归解法，与常规的非递归中序遍历几乎相同，还是借助栈来辅助，只是增加了连接节点。 具体做法： step1：创建两个指针，一个指向题目...

JZ38字符串的排列 描述 输入一个长度为n字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。 题目主要信息 给定一个长度为n的字符串，求其中所有字符的全排列 字符串中可能有重复字符，打印顺序任意 字符串中只包含大小写字母 思路 都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列。为了便于去掉重复情况，还是参照数组全排列，优先考虑字典序排序，因为排序后重复的字符就会相邻，后序递归找起来也很方便 使用临时变量去组装一个全排列...

JZ43整数中1出现的次数（从1到n整数中1出现的次数） 描述 输入一个整数n，求1～n这n个整数的十进制表示中1出现的次数例如，113中包含1的数字有1、10、11、12、13因此共出现6次 思路：暴力统计法 遍历1到n的每个数字，然后对每个数字单独遍历它的每一位，检查是否是1，如果是1则计数。具体做法：step1：从1遍历到n，查看每一个数字。step2：对于每个数字，用连除法每次判断最后一位数字是否为1，并进行计数。 代码 packagemid.JZ43整数中1出现的次数; publicclassSolution{ publicintNumberOf1Between1AndN_Solu...

JZ45把数组排成最小的数 描述 输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。1.输出结果可能非常大，所以你需要返回一个字符串而不是整数2.拼接起来的数字可能会有前导0，最后结果不需要去掉前导0 具体做法 step1：优先判断空数组的特殊情况。step2：将数组中的数字元素转换成字符串类型。step3：重载排序比较为字符串类型的x+y<y+x，然后进行排序。step4：将排序结果再按照字符串拼接成一个整体。 代码 packagemid.JZ4...

JZ46把数字翻译成字符串 描述 有一种将字母编码成数字的方式：'a'->1,'b->2',...,'z->26'。 现在给一串数字，返回有多少种可能的译码结果 示例1 输入："12" 返回值：2 说明：2种可能的译码结果（”ab”或”l”） 思路 思路： 对于普通数组1-9，译码方式只有一种，但是对于11-19，21-26，译码方式有可选择的两种方案，因此我们使用动态规划将两种方案累计。 具体做法： step1：用辅助数组dp表示前i个数的译码方法有多少种。 step2：对于一个数，我们可以直接译码它，也可以将其与前面的1或者2组合起来译码：如果直接译码，则dp[...

JZ47礼物的最大价值 描述 描述 在一个m\timesnm×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 如输入这样的一个二维数组， [ [1,3,1], [1,5,1], [4,2,1] ] 那么路径1→3→5→2→1可以拿到最多价值的礼物，价值为12 具体做法： step1：初始化第一列，每个元素只能累加自上方。step2：初始化第一行，每个元素只能累加自左方。step3：然后遍历数组，对于每个元素添加来...

JZ48最长不含重复字符的子字符串 描述 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 示例1 输入："abcabcbb" 返回值：3 说明：因为无重复字符的最长子串是"abc"，所以其长度为3。 方法1 思路 维护一个数组，想里面添加元素，直至出现第一个重复元素位置，计算数组长度作为一次结果 将每一个元素都作为开始元素，利用两次for，将全部不重复子字符串全部计算出来，取出最大数 代码 intmax=Integer.MIN_VALUE; List<Character>tmp=newArrayList<>(); if(snull&...

JZ49丑数 题目 我们先看到题目，把只包含质因子2、3和5的数称作丑数（UglyNumber）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。 方法1：质因数分解（暴力） 思路 算法实现 一个很朴素的做法 从1n每次+1，一直枚举，直到找到地N个丑数为止 那么还有一个待解决的问题，如何判断当前数字是不是丑数呢？ 我们总结一下丑数的性质：只能分解为2,3,5的如干次幂相乘的数，即设第个丑数为，则res=2x+3y+5z 那么我们只需要通过质因数分解，判断他分解2,3,5后，是否为1，如果为1，则说明没有其他的因数，否则则有其他因数，那么他就不是一个丑数 ...

JZ51数组中的逆序对 题目 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出Pmod1000000007 方法1：暴力 思路 算法实现两个for循环，如果前面的数大于后面的计数加1即可 问题当输入数过大时，需要的时间会很长，所以此方法不行 代码 packagemid.JZ51数组中的逆序对; importjava.util.ArrayList; publicclassSolution{ publicintInversePairs1(int[]array){ in...

JZ54二叉搜索树的第k个节点 题目 给定一棵结点数为n二叉搜索树，请找出其中的第k小的TreeNode结点值。 返回第k小的节点值即可 不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 保证n个节点的值不一样 思路 算法实现 根据二叉搜索树的性质，左子树的元素都小于根节点，右子树的元素都大于根节点。因此它的中序遍历（左中右）序列正好是由小到大的次序，因此我们可以尝试递归中序遍历，也就是从最小的一个节点开始，找到k个就是我们要找的目标。 具体做法：step1：设置全局变量count记录遍历了多少个节点，res记录第k个节点。step2：另写一函数进行递归中序遍历，当节...

JZ56数组中只出现一次的两个数字 题目 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字 思路 算法实现 既然有两个数字只出现了一次，我们就统计每个数字的出现次数，利用哈希表的快速根据key值访问其频率值。 具体做法： step1：遍历数组，用哈希表统计每个数字出现的频率。step2：然后再遍历一次数组，对比哈希表，找到出现频率为1的两个数字。step3：最后整理次序输出。 代码 packagemid.JZ56数组中只出现一次的两个数字; importjava.util.; publicclassSolution{ / 代码中的类名、方法...

JZ57和为S的两个数字 题目 输入一个升序数组array和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。 方法1暴力解题 思路 算法实现 两次循环，两个值相加与sum进行比较，为true直接break即可 代码 packagemid.JZ57和为S的两个数字; importjava.util.ArrayList; publicclassSolution{ / 暴力计算 @paramarray @paramsum @return 运行时间1084ms 占用内存28348KB / privateAr...

JZ58左旋转字符串 题目 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。 对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。 例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc” 思路 算法实现 先判断字符串是否不会空，然后对参数n进行取余，截取前后两节字符串，拼接即可 代码 packagemid.JZ58左旋转字符串; publicclassSolution{ / @paramstr @paramn @return 运行时间19ms 占用内存9976KB / publicSt...