二叉搜索树的第k大元素 问题陈述 给定一棵二叉搜索树，请找出其中第k大的节点。 示例： 1234567输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4 思路分析 由二叉搜索树的特点，知其中序遍历序列有序，为递增序列。这里可以仿中序弄一个倒中序（右根左）然后得到一个递减序列，第k个元素即为第k大节点。 代码实现 123456789101112131415161718192021222324252627public class KElementBST { public int getKthElement(TreeNode root,int k){ List<Integer> list=new ArrayList<>(); helper(root,list); return list.get(k); } //二叉搜索树中序有序，可倒中序遍历，正好得到降序序列 public void helper( ...

平衡二叉树 问题陈述 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 思路分析 深度遍历每个结点，判断其左右子树高度之差是否<=1。 代码实现 12345678910class Solution{ public boolean isBalanced(TreeNode root){ if(root==null) return true; return Math.abs(deepth(root.left)-deepth(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right); } public int deepth(TreeNode root){ if(root==null) return 0; return Math.max(deepth(root.left),deepth( ...

人生的二十几岁，似乎是每个人的成长蜕变的时刻，我的生命，以一贯的孤独与失意肆意行走着。 小时候，在乡村，教育资源的匮乏使得我们并没有学习到过多的知识，更多的日子里，是在田间地头玩着、和小伙伴打打闹闹。坐在老屋的门口，穿着奶奶补了又补的衣裳，吃着地里种的甜瓜。一天好像就是三餐和到处溜达寻思着把弄一些自己做的小玩具。 小学一到四年级的时候，在村里，只有两个上了年纪的老师给我们教语文和数学，偶尔校长教我们画画。读五六年级的时候，从村里去了乡里的小学，开始认识更多的老师，是女孩子，而且比较年轻，最记得我们的语文老师，好几次找到我说我语文学的不错，作文写的很好，那个时候，其实能读到的东西并不多，我们家除了学校给发的语文课本和一点课外阅读就是两本字典，一本是新编汉语字典，是我外公给我的，我还清楚的记得他送我这本字典的那天，他叫我去到他住的屋子，打开一扇木制的柜橱，然后找到一个木盒子，把这本字典取出来给我，让我好好去认字，于是我便毕恭毕敬的接受了，还有一本是我姐买来的成语字典，总记得夏天无事的时候，就爱翻开这两本字典。 快小学毕业的时候，有一次我姐的朋友约她去城里的上顿渡买学习辅导书，回来的时候给我 ...

两个链表的第一个公共结点 问题陈述 输入两个链表，找出它们的第一个公共节点。 如下面的两个链表**：** 在结点c1开始相交。 思路分析 分析一： 先得到A，B链的长度，若A长，则A先走A-B个长度；若B长，则B先走B-A个长度。然后一起走，直到两者相等，返回当前结点。 代码实现： 12345678910111213141516171819202122232425public class sulotion{ public ListNode getIntersection(ListNode headA,ListNode headB){ int lengthA=getLength(headA),lengthB=getLength(headB); ListNode first=headA,second=headB; if(lengthA>lengthB){ for(int i=0;i<lengthA-lengthB;i++){ fi ...

数组中数字出现的次数 问题陈述 一个整型数组 nums里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例： 12输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1] 思路分析 你知道异或吗？ 代码实现 123456789101112131415161718192021222324252627public int[] singleNumbers(int[] nums) { int sum=0; //将数组所有元素进行异或，最后的结果一定是那两个单一数字的异或结果。看上图示例 //用示例[4,4,6,1]最后的抑或结果就是 6和1异或的结果 7 for (int i = 0; i <nums.length ; i++) { sum^=nums[i];//异或符^ } int first = 1; //通过与运算找到result第一个不为0的首位，7 ...

字符串转换整数 请你来实现一个 atoi 函数，使其能将字符串转换成整数。 提示：本题中的空白字符只包括空格字符 ’ ’ 。 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。 示例： 12输入: "42"输出: 42 1234输入: " -42"输出: -42解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。 123输入: "4193 with words"输出: 4193解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。 1234输入: "words and 987"输出: 0解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。 1234输入: &qu ...

统计数字在排序数组中出现的次数 问题陈述 统计一个数字在排序数组中出现的次数。 示例： 12输入: nums = [5,7,7,8,8,10], target = 8输出: 2 思路分析 使用二分法分别找到该数字区的 左边界 left和 右边界 right ，易得数字 target 的数量为 right - left - 1 。 如上例 left=7，right=10。 初始化： 左边界 i = 0，右边界 j = len(nums) - 1 。 循环二分： 当闭区间 [i, j]无元素时跳出； 计算中点 m = (i + j) / 2（向下取整）； 若 nums[m] < target ，则 target 在闭区间 [m + 1, j]中，因此执行 i = m + 1； 若 nums[m] > target ，则 target 在闭区间 [i, m - 1] 中，因此执行 j = m - 1； 若 nums[m] = target，则右边界 right 在闭区间 [m+1, j]中；左边界 left在闭区间 [i, m-1]中。因此分为以下两种情况： 若查找 右边界 ...

把数组排成最小的数 问题陈述 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例： 12输入: [3,30,34,5,9]输出: "3033459" 说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 思路分析 将数字转化为字符串进行比较。如“3”，“30”比较方法：错位组合比较，330和303，得303更小。 代码实现 12345678910111213141516class Solution { public String minNumber(int[] nums) { if(nums==null||nums.length==0) return ""; //判断数组是否为空 int n=nums.length; String[] minArray=new String[n]; //定义一个字符串数组放入整数元素并用空格隔开。 f ...

无重复字符的最长子串 问题陈述 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例： 123输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 思路分析 可使用滑动窗口解题，定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复。 初始化start，end为窗口的首尾，皆指向字符串第一个字符；end++，在不出现重复的情况下将新元素加入map，并每轮记录当前窗口的最大值；若出现了重复，则start移动到该重复元素。 代码实现 123456789101112131415class solution{ public int lengthOfsubString(String s){ int n=s.length(),res=0; Map<Character,Integer> map=new HashMap<> ...

把数字翻译成字符串 问题陈述 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 示例： 123输入: 12258输出: 5解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 思路分析 此题类似于小孩爬楼梯，一次可爬一级或两级。可运用动态规划的思想解题。 0-25翻译为26个字母，在区间[10,25]内，如11，可翻译为bb或l。不在此区间的话则只能单个翻译。 记数字num第i位数字为xix_ixi​,数字num的位数为n。 状态定义：设动态规划列表 dp ，dp[i] 代表以 xix_ixi​为结尾的数字的翻译方案数量。 转移方程：若xix_ixi​和xi−1x_{i-1}xi−1​组成的两位数字可以被翻译，则dp[i]=dp[i-1]+ ...