- 博客(114)
- 收藏
- 关注
RSS订阅原创 剑指offer系列（47）：求1+2+3+...+n
题目描述求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 样例输入5输出15 思路分析方法一：利用Math类的api实现n(n+1)，即Math.pow(n,2) + n方法二：利用递归，达到循环1+2+...+n的效果，异常处理来结束递归方法三：同样是递归，利用短...
2018-10-07 10:32:05
150
原创 leetcode刷题之旅（47）全排列2
题目描述给定一个可包含重复数字的序列，返回所有不重复的全排列。 样例输入: [1,1,2]输出:[ [1,1,2], [1,2,1], [2,1,1]]思路分析依旧是回溯法，不过要注意重复元素，加入flag标志数组判断 代码及结果public List<List<Integer>> permuteUnique(int...
2018-10-01 11:36:41
191
原创 leetcode刷题之旅（46）全排列
题目描述给定一个没有重复数字的序列，返回其所有可能的全排列。 样例输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 思路分析典型的回溯法，注意剪枝 代码及结果public List<List<Integer>> ...
2018-10-01 11:19:13
177
原创 leetcode刷题之旅（40）组合总和2
题目描述给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 样例示例 1:输入: candidates = [10,1,2,7,6,1,5], tar...
2018-10-01 11:06:34
183
原创 leetcode刷题之旅（39）组合总和
题目描述给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 样例输入: candidates = [2,3,6,7], target = 7,...
2018-10-01 10:48:46
126
原创 剑指offer系列（36）：两个链表的第一个公共结点
题目描述输入两个链表，找出它们的第一个公共结点。 样例A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3输入A,B，输出c1 思路分析方法一：找到长链表，先行走数...
2018-09-25 17:01:41
108
原创 剑指offer系列（7）：斐波那契数列
题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 思路分析斐波那契数列f(n)= f(n-1) + f(n-2)，由于要避免栈溢出，不能采用直接递归的方法。方法一：变递归为循环方法二：尾递归，思路同方法一方法三：扩大范围，f(n)= f(n-1) + f(n-2) = f(n-2) + f(n-3) + f(...
2018-09-25 16:15:04
112
原创 剑指offer系列（4）：重建二叉树
题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 样例分析例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回{1,2,5,3,4,6,7} 思路分析前序遍历序列中，根节点总在最前。而中序遍历序列中，根节点分割了左右子树，所以，找...
2018-09-25 15:32:53
103
原创 剑指offer系列（62）：二叉搜索树的第k个结点
题目描述 给定一棵二叉搜索树，请找出其中的第k小的结点。 样例（5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。 思路分析方法一：递归法 二叉搜索树按照中序遍历的顺序 打印出来 即为升序排序 设置一计数器 进行中序排序 找到第k个 即可方法二：非递归法 构造一个栈，思路同 中序遍历的非递归法 代码及结果方法一：in...
2018-09-24 16:04:16
2545
1
原创 剑指offer系列（16）：反转链表
题目描述输入一个链表，反转链表后，输出新链表的表头。 样例输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 思路分析双指针法，pre指针用于使原链表断链，指向反向，next指针用于节点的移动 代码及结果public ListNode ReverseL...
2018-09-23 17:25:23
83
原创 leetcode刷题之旅（145）二叉树的后序遍历
题目描述给定一个二叉树，返回它的 后序 遍历。 样例输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 思路分析方法一：递归，按照后序遍历“左右根”的顺序，依次遍历，递归即可方法二：循环写法，写法类似先序和中序，但添加的list时用了头插，实际遍历顺序为右根左方法三：利用双栈，一个栈进行右...
2018-09-23 12:17:13
293
原创 leetcode刷题之旅（94）二叉树的中序遍历
题目描述给定一个二叉树，返回它的中序 遍历 样例输入: [1,null,2,3] 1 \ 2 / 3输出: [1,3,2] 思路分析方法一：递归，按照中序遍历“左根右”的顺序，依次遍历，递归即可方法二：和先序类似，非递归实现，由根节点向左遍历（过程中并不添加），直到叶子节点，随后pop操作相当于返回上一节点，再遍历右子树部...
2018-09-21 01:00:58
164
原创 leetcode刷题之旅（144）二叉树的前序遍历
题目描述给定一个二叉树，返回它的 前序 遍历 样例输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3] 思路分析方法一：递归，由先序“根左右”的顺序，依次遍历，进行递归即可方法二：非递归实现，由根节点向左遍历，直到叶子节点，随后pop操作相当于返回上一节点，再遍历右子树部分即可方法三：双指针...
2018-09-21 00:25:21
164
原创 leetcode刷题之旅（63）不同路径II
题目描述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。说明：m 和 n 的值均不超过 100。 样例输入...
2018-09-18 12:22:24
149
原创 leetcode刷题之旅（62）不同路径
题目描述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？例如，上图是一个7 x 3 的网格。有多少可能的路径？说明：m 和 n 的值均不超过 100。 样例输入: m = 3, n = 2输出: ...
2018-09-18 11:47:23
175
原创 leetcode刷题之旅（43）字符串相乘
题目描述给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 样例示例 1:输入: num1 = "2", num2 = "3"输出: "6"示例 2:输入: num1 = "123", num2 = "456"输出: "56088"说明：num1 和 num2 的长度小
2018-09-10 16:48:17
123
原创 剑指offer系列（2）：替换空格
题目描述请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy 思路分析直接调用String类的replaceAll方法即可 代码public class Solution { public String replaceSpace(StringBuffer st...
2018-09-10 13:00:58
82
原创 剑指offer系列（6） 旋转数组的最小数字
题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。思路分析采用二分法解答这个问题， mid = low + (high - low)/2 需要考虑三种情况...
2018-07-12 15:01:53
106
原创 剑指offer系列（32） 把数组排成最小的数
题目描述‘输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。思路分析对数组中每两个元素进行组合，比较，确认出最小的排列。比如{3，32，321}，3与32组合，332>323,所以交换3和32的位置， 3与321组...
2018-07-12 10:57:48
187
原创 剑指offer系列（28） 数组中出现次数超过一半的数字
题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。思路分析方法一：排序，由于该数字在数组中所占超过一半，输出中位数即可，复杂度O（nlogn）方法二：利用hashmap，key记录数字值，value记录数字出现次数，遍历一遍数组即可...
2018-07-07 17:38:44
211
原创 剑指offer系列（24）二叉树中和为某一值的路径
题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路分析先序遍历，访问节点时，把该节点添加到路径上去，并累加该节点的值如果该节点为叶节点，并且路径中节点值的和刚好等于输入的整数，则符合当前路径要求当前节点访问完毕，要回到父节点访问其他节点，所以，在退出方法前要在路径上删除当前节点并减去当前节点值，以...
2018-07-03 00:47:46
108
原创 剑指offer系列（17）树的子结构
题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）思路分析第一步：在树A中找到和树B的根节点的值一样的节点R第二步：判断树A中以R为根节点的子树是不是包含和树B一样的结构代码public boolean HasSubtree(TreeNode root1,TreeNode root2) { if (root1==null || roo...
2018-07-03 00:25:00
136
原创 算法练习 (8) 01背包问题
题目描述给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。样例输入描述:输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000) 第二行为n个正整数A[i](32位整数)，以空格隔开。输出描述:输出所求的方案数示例1输5 15 5 5 10 2 ...
2018-07-02 09:59:02
240
原创 leetcode刷题之旅（94）Binary Tree Inorder Traversal
题目描述Given a binary tree, return the inorder traversal of its nodes' values. 样例 Input: [1,null,2,3] 1 \ 2 / 3Output: [1,3,2] 思路分析 递归法：按照中序遍历的定义，即“左 根 右”的进行递归即可...
2018-06-30 00:05:16
153
原创 剑指offer系列（23）二叉搜索树的后序遍历序列
题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。样例输入：{5.7.6.9.11.10.8}输出：true思路分析已知条件：后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。 1、确定root； 2、遍历序列（除去root结点），找到第一个大于root的位置，...
2018-06-27 01:33:48
201
原创 剑指offer系列（58）对称二叉树
题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。思路分析此题同原 leetcode（101）Symmetric Tree递归方法 比较对应左子树与右子树值循环方法 层序遍历 比较代码方法一 递归boolean isSymmetrical(TreeNode pRoot){ return isSymmetrical...
2018-06-27 00:41:28
92
转载 java 配置相关 设置Eclipse的类文件和xml文件代码自动补全
我们在平常编写代码的时候，不会记住大多数的类和文件的属性，方法等等，这就需要我们设置类文件和xml文件自动补全的功能，也可以说是代码提示功能。 类文件自动补全 第一步：打开Eclipse菜单栏生的Windows选项，下拉选择其中的最后一个首选项设置Preferance 第二步：在左边的列表里面找到Java，继续在里面找到Editor...
2018-06-23 09:35:58
330
原创 leetcode刷题之旅（101）Symmetric Tree
题目描述Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).判断是否为对称二叉树样例For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / \ 2 2 / \ / \3...
2018-06-23 01:00:03
100
原创 leetcode刷题之旅（100）Same Tree
题目描述Given two binary trees, write a function to check if they are the same or not.Two binary trees are considered the same if they are structurally identical and the nodes have the same value.样例Exampl...
2018-06-23 00:21:06
84
原创 剑指offer系列（18）二叉树的镜像
题目描述操作给定的二叉树，将其变换为源二叉树的镜像。样例二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5思路分析1.获取当前节...
2018-06-22 23:33:58
119
原创 剑指offer系列（39）平衡二叉树
题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。思路分析方法一：平衡二叉树定义：二叉树中任意节点的左，右子树深度不超过1 参考之前二叉树的深度，利用递归，依次求出深度，比较即可得出答案方法二：方法一中，一个节点作为子节点时被遍历，作为根节点时同样被遍历，如此，有太多重复的遍历次数 如果用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个节点之...
2018-06-21 00:47:01
164
原创 剑指offer系列（52）正则表达式匹配
题目描述请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。样例输入aaa a.a 输出 true输入aaa ab*ac*a 输出 true输入aaa aa.a 输出false输入aaa ab*a 输出false思路分析此题要分两种情况当模式中的第...
2018-06-20 01:29:53
155
原创 剑指offer系列（56）删除链表中重复的结点
题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5思路分析循环写法：设置两指针，完成链表的遍历及节点删除，注释里写的很详细了 不多说递归写法：通过判断条件，设置参数为不重复的节点，如此递归，相当于跳过来所有重复的元素，此写...
2018-06-18 20:30:20
99
原创 剑指offer系列（38）二叉树的深度
题目描述输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。思路分析先复习一下概念树的深度：以二叉树的根结点所在的层数为1，根结点的孩子结点所在的层数为2，以此下去。深度是指所有结点中最深的结点所在的层数。递归思路：树的深度为左右子树深度的较大值+1，以此递归到底层，即可得出答案循环思路：借鉴之前打印二叉树的思路，层序遍历，设置一...
2018-06-18 19:24:18
137
原创 剑指offer系列（59）按之字形顺序打印二叉树
题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。思路分析在剑指offer（60）题基础上，再加入一个判断层数奇偶的方法代码大同小异 不多赘述代码import java.util.ArrayList;import java.util.Collections;import java.util.L...
2018-06-17 22:22:18
118
原创 剑指offer系列（60）把二叉树打印成多行
题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。思路分析和剑指offer（22）思路基本一致，不过加入了两个变量，start记录已打印节点数，end记录当前层总节点数，以此来实现分层代码public class 把二叉树打印成多行 { ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ...
2018-06-17 20:58:32
115
原创 剑指offer系列（22）从上往下打印二叉树
题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。样例思路分析构造一个队列容器，即可轻松解决这道题步骤操作队列1 打印节点8 节点6、节点102打印节点6 节点10、节点5、节点73打印节点10节点5、节点7、节点9、节点114打印节点5节点7、节点9、节点115打印节点7节点9、节点116打印节点9节...
2018-06-17 19:55:32
142
原创 java趣谈（3）ArrayList与LinkedList插入效率探究
昨天做题时，看到了Collections的reverse方法，区分了arraylist和linkedlist的情况，一时兴起，看了看源码，发现了一些有趣的情况。情况一 尾插public static void main(String[] args){ List list1 =new ArrayList(); long t1 = System.currentTimeMillis(); f...
2018-06-16 21:37:42
240
原创 剑指offer系列（3）从尾到头打印链表
题目描述输入一个链表，从尾到头打印链表每个节点的值思路分析看到题目，首先想到的是逆转链表，然后打印，但这样会改变链表结构，明显不符合仅仅“打印”的要求随后又想到，构造一种数据结构，使得链表数据插入后可以按反序输出，自然就想到了栈方法一：利用栈的先入后出原则，遍历整个链表后再逐个出栈方法二：利用递归，（递归本质是栈结构）方法三：利用ArrayList的add api，循环写法/** * I...
2018-06-16 01:43:34
106
原创 剑指offer系列（66）机器人的运动范围
题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？思路分析和前题类似，这个方格也可以看做一个m*n...
2018-06-15 00:49:51
102
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人