changetocs的博客

1、404. Sum of Left Leaves Find the sum of all left leaves in a given binary tree. 思路：这题主要学习一下递归，使用递归应该想清楚递归的终止条件，终止时要返回的结果。/** * Definition for a binary tree node. * public class TreeNode { *

解题思路：主要是溢出情况的判断，在乘10之前判断当前值是否大于最大整数除10或者小于最小整数除10，如果满足条件就会溢出，按题意返回0。public class Solution { public int reverse(int x) { int res = 0; while(x != 0){ if(res > Integer.MA

解题思路：这个题目主要是找规律。最后一行和第一行两个元素下标之间相差numRows * 2 - 2，中间的行按照元素两两配对，这两个元素下标之间的距离为step - i * 2。public class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s;

解题思路：二分查找的思路，但是不能用递归，亲测会stackoverflow。那就只能用循环了，要想清终止条件，感觉蛮绕的，自己有待加强，要分析好久才能理清。需要注意的是，在取二分查找的中间值时，不要使用左右相加后再除以2的方式，这样可能会在计算时产生溢出。/* The isBadVersion API is defined in the parent class VersionControl.

解题思路：两个指针，一开始分别指向头和尾，对于两个指针所指的都是字母的情况进行判断，如果二者不相等并且相差的ASCI码绝对值也不是32，返回false。这里有个加快运行时间的技巧是不要先把所有的非字母和数字的字符去掉或者把大写转为小写，直接在运行中一个个来判断，因为有可能还未判断完所有的字符已经返回false了。如果一开始就全部处理了显然做了很多无用功。最终击败数目93.68%，创了我的新高。pub

解题思路：扫描。。。时间复杂度O(N*M)。据说最好的算法是KMP算法，不过我还不会。。。public class Solution { public int strStr(String haystack, String needle) { if(haystack.length() == 0 && needle.length() == 0) { ret

解题思路：用一个长度为10的数组来存储数字0-9在两个字符串中出现的状态。如果相同位置的数字也相同，则直接把A的技术增1即可。否则，处理见程序。解释一下，数组一开始所有元素都为0，由于数组中对应位置的值secret只有++的权利，guess只有–的权利，所以如果判断++之后对应位置的元素还是小于等于0，说明该元素在guess中出现过。反之同理。同时两者的++和–也有相互抵消的作用，保证了在一个字符串

解题思路：从末尾依次对应相加来求，转成int中的相加会使代码比较简洁，因为可以用/和%来分别求出进位和当前往结果中添加的位。然后，把较长的字符串剩下的部分和进位相加放入结果。最后，还要判断进位此时是否为1，如果为1，则需要再往结果中添加1，否则返回结果。public class Solution { public String addBinary(String a, String b) {

解题思路：用一个长度为10的数组来存储数字0-9在两个字符串中出现的状态。如果相同位置的数字也相同，则直接把A的技术增1即可。否则，处理见程序。解释一下，数组一开始所有元素都为0，由于数组中对应位置的值secret只有++的权利，guess只有–的权利，所以如果判断++之后对应位置的元素还是小于等于0，说明该元素在guess中出现过。反之同理。同时两者的++和–也有相互抵消的作用，保证了在一个字符串

解题思路：最长公共前缀肯定不会超过最短字符串的长度。所以先获得最短字符串的长度。然后一个二层循环，外层循环是最短字符串长度的每个位置，内层循环是每个字符串对应的这个位置的字符，然后比较所以字符串这个位置的字符是否相等，如果相同，将该字符加入结果中，否则返回结果。public class Solution { public String longestCommonPrefix(String[]

题目： Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.Example: Given a = 1 and b = 2, return 3.解题思路：用异或算不带进位的和，用与并左移一位来算进位，再把两者相加即可，直到进位为全0。递归的解法如下：public

1、414. Third Maximum Number 题目：Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

1、300. Longest Increasing Subsequence Given an unsorted array of integers, find the length of longest increasing subsequence.For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing s

151. Reverse Words in a StringGiven an input string, reverse the string word by word.For example, Given s = “the sky is blue”, return “blue is sky the”.Update (2015-02-12): For C programmers: Try to

1、LeetCode190. Reverse Bits Reverse bits of a given 32 bits unsigned integer.For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represente

7. Reverse IntegerReverse digits of an integer.Example1: x = 123, return 321 Example2: x = -123, return -321Have you thought about this? Here are some good questions to ask before coding. Bonus point

19. Remove Nth Node From End of ListGiven a linked list, remove the nth node from the end of list and return its head.For example,Given linked list: 1->2->3->4->5, and n = 2.After removing the

146. LRU CacheDesign and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.get(key) - Get the value (will always be positive) of th

207. Course ScheduleThere are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is

1、111. Minimum Depth of Binary Tree Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 分析：在

解题思路：我表示这道题对我来说关键就是理解题意。。。真的没理解题意，网上查了才恍然大悟。首先说一下题意。n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1个1，所以输出11；n=3时，由于上次字符是11，有2个1，所以输出21；n=4时，由于上次字符串是21，有1个2和1个1，所以输出1211。依次类推，写个countAndSay(n)函数返回字符串。理解题意后，关键就是如

解题思路：一开始我的做法是先遍历一遍取得长度，然后长度减去n就知道要删除正着数第几个元素，结果题目要求one pass。那就只能用两个指针，一个快指针先走n步，一个慢指针从头开始走，这样当快指针走到尾部的时候，慢指针所指的就是要删除元素的前一个元素。/** * Definition for singly-linked list. * public class ListNode { *

解题思路：用java写的话有个需要注意的地方就是由于Stack中的元素用了泛型，而泛型不支持基本类型，所以需要基本类型的包装类。而包装类不同于基本类型的是包装类是引用，要比较相等不能简单使用==，要使用equals方法。 LeetCode官网unlock的提示： Hints:Consider space-time tradeoff. How would you keep track of th

解题思路：只有所有阶乘的数里面出现因子2和5相乘才会有0出现。又容易观察到2的个数总是大于5的个数，所以本题转化为求所有小于等于当前n的正整数中因子5的个数。例如n = 30。n/5 = 6。此处的6并不能代表5的个数，因为25中包含两个5。所以求5的个数可以表示成SUM(N/5^1, N/5^2, N/5^3…)。public class Solution { public int tr

解题思路：获取字符串长度，从后往前判断，关键是要理清几种情况。如果字符串尾部是空格，则什么都不做，直到遇到第一个非空格字符，这时候count开始计数，直到再次遇到空格或者i<0返回count。public class Solution { public int lengthOfLastWord(String s) { if(s == null) ret

解题思路：用一个map来存放模式和单词的对应形式，注意由于模式和单词是双向匹配，所以如果来了一个新的模式和单词对应形式，要查看map的keys里面是否已经存在该模式，如果存在，再检查该模式对应的单词是否和新单词一样，如果不一样，返回false。如果不存在该模式，则检查map的values里面是否已经存在该单词，如果存在，则说明对应该单词的模式和新来的模式不一样，返回false。如果map里即不存在该

解题思路：这是一道典型的可以用栈来解决的问题。做一个空栈。一个个读入字符直到字符串结尾。如果字符是一个开放符号，则将其推入栈中。如果字符是一个封闭符号，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开放符号，则报错。在字符串结尾，如果栈非空则报错。public class Solution { public boolean isValid(String s) {

解题思路：找最小要比找最大复杂，因为递归对于最大来说如果一个节点只有左子树或右子树，它无需额外考虑，仍可以一时同仁对左右子树调用递归，只不过对null的子树返回的是0，而在比较取较大者时会自动放弃较小的0值。但对于最小来说，比较的时候是取较小者，不能对null的子树返回0，否则取较小的时候会取该子树，显然这样不符合要求，只有叶子节点才可以返回0。针对这种情况有两种解决方案，一种是分情况讨论，另一种是

解题思路：共有27个九宫格，每个九宫格9个元素，所以初始化一个27*9的数组来表示某个元素在某个九宫格里是否出现过，0表示没出现，1表示出现过。这个27*9的数组前0-8行用来存放1*9的9个九宫格，第9-17行用来存放9*1的9个九宫格，第18-26行用来存放3*3的9个九宫格。位于第i行第j列的元素k，分别位于27*9的数组的三个地方，第i行第k列，第j+9行第k列，第i/3*3+j/3+18行

解题思路：不断取出该整数的头尾的数字进行比较，比较完需要取出头尾的数字。public class Solution { public boolean isPalindrome(int x) { if(x < 0) { return false; } int len = 1; while(x/len>=10)

解题思路：一开始想通过反转链表来做，可发现要求不能改变原来的链表结构，当然反转也可以，大不了再转回来，麻烦。比较简单的做法就是考虑到题目的意思是两个链表要有交叉肯定是在从两个链表相同元素位置一直持续到结尾，所以可以先获得两个链表的长度，使较长的链表先移动到剩下的和较短的链表长度相同，这要就可以同步移动两个链表来比较了。有个注意点是题目中两个元素交叉是指这Node相等，而不是只是Node的值相等。/*