冰天烈火-CSDN博客

原创 101. Symmetric Tree

问题描述：判断一棵树是否镜像对称。思路：先将每一层的节点按序获取，然后进行首尾比较。如果相同，继续比较它们子节点直到叶子结点。原答案： public boolean isSymmetric(TreeNode root) { if(root==null) return true; List<TreeNode> nodeL...

2018-10-11 22:49:23 79

原创 235. Lowest Common Ancestor of a Binary Search Tree

问题描述：给你一个二叉树与两个目标节点，找到距离这两个目标节点的公共父节点中，层级最低的那个。思路：遍历二叉树找出从根节点到两个目标节点的路径。遍历并比较两个节点的路径。原答案： private List<TreeNode> path= new ArrayList<TreeNode>(); public TreeNode lowestCommo...

2018-10-11 00:01:17 103

原创 415. Add Strings

问题描述：实现两个由0~9数字组成的String加和，两个String长度小于5100且不以零开头。不可以使用BigInteger 类库，不可以将字符转换为数字。思路：既然不能用原生方法，那就用老办法，将数字从末尾开始一位一位加和计算。原答案： public static String addStrings(String num1, String num2) { cha...

2018-09-25 22:08:44 118

原创 118. Pascal's Triangle

问题描述：输出杨辉三角。思路：两边的11直接拼接，中间的数字都是由上一个拼接好的数列两两加和得到。原答案： public List<List<Integer>> generate(int numRows) { List<Integer> list=new ArrayList<Integer>(); List...

2018-09-25 21:24:13 80

原创 836. Rectangle Overlap

问题描述：给你两个各包含四个数字的数组。每个数组前两个数字表示长方形左下角的坐标。后两个数字代表右上角坐标。判断这两个矩形是否相交。原答案： public boolean isRectangleOverlap(int[] rec1, int[] rec2) { if(rec2[0]>=rec1[0]&&rec1[2]>rec2[0])...

2018-08-10 19:32:51 354

原创 257. Binary Tree Paths

问题描述：找出一个二叉树中，根节点到所有叶子节点的路径。思路：如果节点左右子树都不存在，表明为叶子节点。将路径保存并返回。只是根节点就是叶子节点时，要特殊判断下。原答案： private List<String> resList=new ArrayList<String>(); public List<String> binaryTr...

2018-08-09 19:56:56 79

原创 21. Merge Two Sorted Lists

问题描述：将两个排序好的ListNode对象合并为一个合并好的ListNode对象。思路：这相当于归并排序中合并的部分。然而由于是面向对象，所以我想不到办法一次遍历解决。原答案： public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null) return l...

2018-08-07 19:56:15 68

原创 844. Backspace String Compare

问题描述：两个字符串中#代表一次删除操作，比较这两个字符串最终输出是否相等。你能否在O(n)空间与O(1)时间内完成。思路：使用stack，不是#代表压栈，否则就是出栈。最后比较两个栈是否相等。O（n）时间是没问题。O(1)空间实在做不到。原答案： public boolean backspaceCompare(String S, String T) { char...

2018-08-06 21:18:18 94

原创 830. Positions of Large Groups

问题描述：一个由小写字母构成的字符串，找出其中连续出现超过三次字母的起始位置。并按照出现的顺序返回结果。思路：转换为数组，遍历即可。原答案： public List<List<Integer>> largeGroupPositions(String S) { List<List<Integer>> resList...

2018-08-06 20:39:32 93

原创 661. Image Smoother

问题描述：将一个正整数二维数组的数字替换为上下左右，左上左下右上右下8个相邻数字与自身数字平均数向下取整后的数字。数组中数字大小在[1,255]。数组的长度为[1, 150]。思路：没什么好思路，遍历然后加和计算。原答案： public int[][] imageSmoother(int[][] M) { int length=M.length; ...

2018-08-02 23:05:43 95

问题描述：给你一个整数数组，这些数组中的数字用来表示二维平面上点的坐标。现在如果有三个点i，j，k。如果i到j的距离等于i到k的距离。那么(i,j,k)的组合就被称为Boomerangs（区分排序，即(i,k,j)也算）。那么这个数组中有多少个Boomerangs。思路：循环计算一个点与其它各个点的距离。如果距离为l的点有n个。那么能组合出来的Boomerangs就有n*(n-1)。然而并不是...

2018-08-01 23:22:34 145

原创 202. Happy Number

问题描述：将一个数字的每位数字的平方和相加，如果重复进行此操作后和为1。返回true。而如果无限循环也无法得出1，返回false。思路：原想着可能是个数学题有什么捷径，翻了下讨论区才发现是暴利破解。原答案： private Map<Integer,Boolean> record=new HashMap<Integer,Boolean>(); ...

2018-06-15 21:53:54 107

原创 458. Poor Pigs

问题描述：有1000桶水，其中一桶是有毒的，一只猪喝完有毒的水之后会在15分钟内死亡。一个小时内用多少只猪可以找出有毒的水。并且推广来讲，一共buckets桶水，总时间为minutesToTest，猪会在minutesToDie时间内死亡。求解需要多少只猪。思路：无论如何也想不到最佳答案。翻看讨论区答案了。总结如下：假设猪喝完毒水后15分钟死亡。一个小时内2只猪可以找出25桶水。方法为将2...

2018-06-12 23:10:32 127

原创 107. Binary Tree Level Order Traversal II

问题描述：讲一个二叉树每一层由左向右由下向上形成一个。思路：递归返回左右子树已排好序的list。由于合并比较麻烦，所以就干脆先合并成由左向右，由上到下的list。最后在对这个list倒序排列下。原答案： public List<List<Integer>> levelOrderBottom(TreeNode root) { List&...

2018-06-12 22:46:13 75

原创 121. Best Time to Buy and Sell Stock

问题描述：给你一个整数数组代表每天的股票价格，在只允许一次买入卖出的情况下，最大收益是多少。思路：当价格上升时，保持累加。当价格开始下降时，记录当前的最大值。继续保持累加，当累加到负数时，表明出现了新的最低点。因此将累加和设置为0。原答案： public int maxProfit(int[] prices) { int maxProfit=0; ...

2018-06-11 21:36:10 93

原创 674. Longest Continuous Increasing Subsequence

问题描述：返回一个整形数组中连续增加子序列的长度。思路：判断下个数字是否大于当前，是则当前长度+1。否，则判断当前长度是否最长。重置当前长度为1。原答案： public int findLengthOfLCIS(int[] nums) { int maxLength=0; int length=nums.length; if(l...

2018-05-16 22:24:50 71

原创 504. Base 7

问题描述：将一个数字转换为7进制形式。思路：仿照转换为二进制形式。原答案： public String convertToBase7(int num) { StringBuffer sb=new StringBuffer(); boolean flag=false; if(num>=0) flag...

2018-04-21 17:45:04 90

原创 541. Reverse String II

问题描述：将一个字符串中的每2K个字符的前K个颠倒，后面保持原顺序。思路：就按照题目所说，颠倒前K个，跳过后面K个。原答案： public String reverseStr(String s, int k) { if(k==0) return s; char [] cArray=s.toCharArray(); ...

2018-04-21 17:04:13 119

原创 744. Find Smallest Letter Greater Than Target

问题描述：在一个由小写字母构成的已排好序的数组中找出比目标字符大的最小字符，注意，这个数组可以是环形的。思路：由于数组是环形的且已排好序，所以如果目标值》=数组最后一个字符。直接返回第一个字符即可。否则遍历数组找出最小值。原答案： public char nextGreatestLetter(char[] letters, char target) { if(...

2018-04-17 21:26:18 69

原创 350. Intersection of Two Arrays II

问题描述：找出两个数组中重复的数字。思路：用map记录一个数组中数字出现的次数。从而得出另一个数组中重复的数字有哪些。原答案： public int[] intersect(int[] nums1, int[] nums2) { Map<Integer,Integer> map=new HashMap<Integer,Integer>(...

2018-04-17 20:39:01 83

原创 108. Convert Sorted Array to Binary Search Tree

问题描述：将一个已排好序的数组构建成BST树。思路：一个BST树从上向下看就是一个排好序的数组。所以取中间数字为根节点，然后递归构建左右子树。原答案： public TreeNode sortedArrayToBST(int[] nums) { int length=nums.length; if(length==0) ...

2018-04-16 21:11:50 61

原创 551. Student Attendance Record I

问题描述：一个字符串中如果连续出现三次L或者A出现总数超过两次，返回false。思路：遍历char数组，根据遍历到的字符判断。原答案： public boolean checkRecord(String s) { char [] cArray=s.toCharArray(); boolean contn=false; int lNu...

2018-04-16 19:58:50 96

原创 506. Relative Ranks

问题描述：给你一组代表运动员成绩的整数，按照他们的成绩返回String数组，第一名对应Gold Medal，第二名对应Silver Medal，第三名对应Bronze Medal。其他则是排名。思路：构建数组记录成绩。然后倒序遍历成绩从而得出名次。再遍历原成绩，根据成绩记录数组得出对应的名次。原答案： public String[] findRelativeRanks(int...

2018-04-10 22:04:15 123

原创 409. Longest Palindrome

问题描述：从一个字符串中构建回文子字符串（大小写敏感）。返回最长回文子字符串长度。思路：出现次数为偶数次的字符串全部采用，出现次数为奇数次的将出现次数最大的采用。其余的采用次数-1。原答案： public int longestPalindrome(String s) { char [] c=s.toCharArray(); int [] re...

2018-04-02 15:54:36 71

原创 401. Binary Watch

问题描述：如下所示的手表，根据亮起的灯数。输出可能的时间。由于直接翻了讨论区所以就不打算写了。无论如何我也想不到讨论区里的解法。最佳答案JAVA版： String[][] hour = {{"0"}, {"1", "2", "4", "8"}, {"3", "5", "6",

2018-04-02 14:47:28 97

原创 543. Diameter of Binary Tree

问题描述：找出一颗树中，相隔最长的路径。原代码： private int diameter=0; public int diameterOfBinaryTree(TreeNode root) { if(root==null) return 0; int left=findDiameter(root.left); ...

2018-04-02 14:06:05 81

原创 268. Missing Number

问题描述：一个长度为n的数组由0~n中n-1个不同的数字组成。找出没有的那一个。思路：原想通过位运算，但没想出来。后来想到可以将数组中数加和。然后与n个数的和相减即可得。原代码： public int missingNumber(int[] nums) { int totalNum=0; for(int i=0;i<nums.length...

2018-03-30 19:09:39 64

原创 599. Minimum Index Sum of Two Lists

问题描述：给你两个字符串数组，找出这两个数组中相同字符串对应索引之和最小的字符串。思路：使用map。原代码： public String[] findRestaurant(String[] list1, String[] list2) { String []s=new String[Math.max(list1.length,list2.length)]; ...

2018-03-28 17:55:11 97

原创 697. Degree of an Array

问题描述：给你一个数组，这个数组中出现次数最大的一个或几个数字，找出包含这些数字的最短子串。原答案： public int findShortestSubArray(int[] nums) { int[] record=new int[50000]; int[] begin=new int[50000]; int[] end=new...

2018-03-27 19:49:22 77

原创 538. Convert BST to Greater Tree

问题描述：将一个BST树节点加上该BST树中所有节点比它大的值。思路：后序遍历。原答案： private int totalSum=0; public TreeNode convertBST(TreeNode root) { if(root==null) return root; convertBST(r...

2018-03-21 15:17:36 84

原创 217. Contains Duplicate

问题描述：找出一个数组中是否有重复出现的数字。思路：两种实现方式：1、通过map。2、排序，然后比较数字。后一种运行时间较好。原答案： public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); int length=nums.length-1; for(i...

2018-03-20 22:07:54 81

原创 530. Minimum Absolute Difference in BST

问题描述：找出一颗BST树中，两个节点差值绝对值得最小值是多少。思路：由于是所有节点，所以想不出来怎么递归了。所以不如中序遍历树，记录所有值。记录中的数据就是已排好序的数字，随后将记录的值遍历取最小差值。原答案： public int getMinimumDifference(TreeNode root) { int min=Integer.MAX_VALUE...

2018-03-20 21:51:52 99

原创 387. First Unique Character in a String

问题描述：找出一个字符串中第一个唯一的字符。返回其位数。思路：用数组记录字符是否出现，第一次出现赋值为出现的位数。再次出现更新成-1。只要记录大于0或者是-1就更新成-1。否则更新为位数。原答案： public int firstUniqChar(String s) { char[] c=s.toCharArray(); int[] record=...

2018-03-15 22:47:11 60

原创 237. Delete Node in a Linked List

问题描述：给你一个单向链表，删除给定的元素。思路：如果知道要删除元素的上一级，直接修改指向就完成了删除。然而，这是个单向链表。所以唯一“删除”的办法，就是把后一个元素的值给前一个元素。循环操作直到末尾。原代码：public void deleteNode(ListNode node) { ListNode nextNode=node.next; ...

2018-03-13 21:08:00 100

原创 563. Binary Tree Tilt

问题描述：给你一个二叉树，找出这个二叉树上所有节点的左子树上所有节点的和与有节点上所有节点的和之间差值绝对值得和。思路：递归。原代码：class Solution { public int findTilt(TreeNode root) { if(root==null) return 0; return searchT...

2018-03-12 21:46:40 75

原创 455. Assign Cookies

问题描述：给你两个数组，将后一个数组中数字与前一个数组中不大于它的数字配对。不重复使用数字的情况下，这样的配对最多能有多少个。思路：归并排序中，有一步是两个数组互相比较然后组合。这个步骤与这道题中思路一致。如果对两个数组进行同样的归并操作。那么就可以知道后一个数组有多少个是比前一个数组大的。而归并的前提是这两个数组已经排好序，所以使用Arrays.sort先对两个数组进行排序。原代码：...

2018-03-10 10:55:44 70

原创 167. Two Sum II - Input array is sorted

问题描述：给你一个已经排好序的数组与目标值target。返回这个数组中两个数相加之和为target的数字位置。假定数组中这样的数有且只有一组。思路：用map来保存当前数字的目标值和下标。后续遍历遇上目标值时，返回当前序号与下标。原代码： public int[] twoSum(int[] numbers, int target) { Map<Intege...

2018-03-08 21:51:39 77

原创 242. Valid Anagram

问题描述：给你两个字符串s,t判断t是否由s中所有字母乱序组成。思路：用数组记录s中字符出现的次数，遍历t时没出现一次减一。如有负数，return false。原代码： public boolean isAnagram(String s, String t) { int [] record=new int[26]; char [] sChar=s....

2018-03-08 21:23:20 79

原创 404. Sum of Left Leaves

问题描述：求一个二叉树中所有左叶子节点的和。思路：递归，由于只是左叶子，所以需要有一个是否相加的判断。原代码： public int sumOfLeftLeaves(TreeNode root) { int sum=0; if(root==null) return sum; else{ ...

2018-03-07 22:26:02 93

原创 100. Same Tree

问题描述：判断两个二叉树是否相等。相等条件为二叉树的结构一致且对应点上数值一致。思路：递归，根相同就判断左右子树，不同直接返回false。原代码： public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null){ if(q==null) re...

2018-03-07 21:30:03 88

空空如也

空空如也