blankj / awesome-java-leetcode

:crown: LeetCode of algorithms with java solution(updating).

awesome-java-leetcode

我如今是一名 Android Developer，大学的我曾是一名 ACMer，我一直认为数据结构和算法是作为一名程序员必须掌握和善于利用的，为了不让数据结构和算法淡出我的记忆，所以我打算重拾 LeetCode 之 Algorithm，语言选择的是 Java，题库会一点点完善起来，按简单，中等，困难分类，相应难度下按题号排序，源代码在 src 目录中，相关解题都在 note 目录中，想要学习数据结构和算法或打算刷 LeetCode 的小伙伴们欢迎 star 哦。

如今有机会面试 Facebook，附上 LeetCode 上 Facebook 的面试题目序号，希望可以帮助到以后想入 Facebook 的小伙伴:-)

1,10,13,15,17,20,23,25,26,28,33,38,43,44,49,50,56,57,67,68,69,71,75,76
78,79,80,85,88,90,91,98,102,117,121,125,127,128,133,139,146,157,158,161
168,173,200,206,208,209,210,211,215,218,221,234,235,236,238,252,253,257
261,265,269,273,274,275,277,278,282,283,285,286,297,301,311,314,325,334
341,377,380,398,404,410,461,477,494,523,525,534,535,543,554

如果想知道更多公司 LeetCode 面试题，可以参看 Companies.md。

附上镇楼诗：

明有科举八股，今有 LeetCode。
八股定格式而取文采心意，LeetCode 定题目且重答案背诵。
美其名曰："practice makes perfect."
为何今不如古？
非也非也，
科举为国取士，LeetCode 为 Google 筛码工，各取所需也。

Easy

#	Title	Tag
1	Two Sum	Array, Hash Table
7	Reverse Integer	Math
9	Palindrome Number	Math
13	Roman to Integer	Math, String
14	Longest Common Prefix	String
16.11	跳水板(Diving Board LCCI)	递归、记忆化
20	Valid Parentheses	Stack, String
21	Merge Two Sorted Lists	Linked List
26	Remove Duplicates from Sorted Array	Array, Two Pointers
27	Remove Element	Array, Two Pointers
28	Implement strStr()	Two Pointers, String
35	Search Insert Position	String
38	Count and Say	String
53	Maximum Subarray	Array, Divide and Conquer, Dynamic Programming
58	Length of Last Word	String
66	Plus One	Array, Math
67	Add Binary	Math, String
69	Sqrt(x)	Binary Search, Math
70	Climbing Stairs	Dynamic Programming
83	Remove Duplicates from Sorted List	Linked List
88	Merge Sorted Array	Array, Two Pointers
100	Same Tree	Tree, Depth-first Search
101	Symmetric Tree	Tree, Depth-first Search, Breadth-first Search
104	Maximum Depth of Binary Tree	Tree, Depth-first Search
107	[Binary Tree Level Order Traversal II][107]	Tree, Breadth-first Search
108	Convert Sorted Array to Binary Search Tree	Tree, Depth-first Search
110	Balanced Binary Tree	Tree, Depth-first Search
111	Minimum Depth of Binary Tree	Tree, Depth-first Search, Breadth-first Search
112	Path Sum	Tree, Depth-first Search
118	Pascal's Triangle	Array
119	Pascal's Triangle II	Array
121	Best Time to Buy and Sell Stock	Array, Dynamic Programmin
122	Best Time to Buy and Sell Stock II	Array, Greedy
543	Diameter of Binary Tree	Tree

Medium

#	Title	Tag
2	Add Two Numbers	Linked List, Math
3	Longest Substring Without Repeating Characters	Hash Table, Two Pointers, String
5	Longest Palindromic Substring	String, Dynamic Programming
6	ZigZag Conversion	String
8	String to Integer (atoi)	Math, String
11	Container With Most Water	Array, Two Pointers
12	Integer to Roman	Math, String
15	3Sum	Array, Two Pointers
15	3Sum Closest	Array, Two Pointers
17	Letter Combinations of a Phone Number	String, Backtracking
18	4Sum	Array, Hash Table, Two Pointers
19	Remove Nth Node From End of List	Linked List, Two Pointers
22	Generate Parentheses	String, Backtracking
24	Swap Nodes in Pairs	Linked List
29	Divide Two Integers	Math, Binary Search
33	Search in Rotated Sorted Array	Arrays, Binary Search
43	Multiply Strings	Math, String
49	Group Anagrams	Hash Table, String
50	Pow(x, n)	Math, Binary Search
56	Merge Intervals	Array, Sort
63	不同路径 II(Unique Paths II)	数组、动态规划
209	长度最小的子数组(Minimum Size Subarray Sum)	数组、双指针、二分查找
215	数组中的第K个最大元素(Kth Largest Element in an Array)	堆、分治算法
554	Brick Wall	Hash Table
1014	最佳观光组合(Best Sightseeing Pair)	数组

Hard

#	Title	Tag
4	Median of Two Sorted Arrays	Array, Binary Search, Divide and Conquer
10	Regular Expression Matching	String, Dynamic Programming, Backtracking
23	Merge k Sorted Lists	Linked List, Divide and Conquer, Heap
25	Reverse Nodes in k-Group	Linked List
30	Substring with Concatenation of All Words	Hash Table, Two Pointers, String
44	Wildcard Matching	String, Dynamic Programming, Backtracking, Greedy
57	Insert Interval	Array, Sort
68	Text Justification	String
1028	从先序遍历还原二叉树(Recover a Tree From Preorder Traversal)	树、深度优先搜索

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。

awesome-java-leetcode's Issues

003

private static int lengthOfLongestSubstringMe(String s) {
HashMap<Character, Integer> map = new HashMap<>(128);
int max = 0;
int pre = 0;
char temp;
for (int i = 0; i < s.length(); i++) {
temp = s.charAt(i);
if (map.containsKey(temp)) {
max = Math.max(max, i - pre);
pre = Math.max(map.get(temp) + 1, pre);
}
map.put(s.charAt(i), i);
}
return Math.max(max, s.length() - pre);
}

21、合并两个链表

LZ你好，请问一下为什么最后返回的是head.next而不是temp.next？

Blankj同学很有学习的动力啊. 加油加油

加油加油！

我现在还是一名大学生，我希望自己以后能成为一名优秀的ACMer，谢谢楼主这个项目，会持续关注，感谢！

Longest Common Prefix

如果有N个字符串，那就需要N个循环了啊

002里面不是所有case都能通过

试了一下[2,4,3]和[5,6,7]，得到了[7,0,1,1]

two num

两个数相加，如果是Integer的情况，用一个方法处理该如何操作呢？

013 注释错了

    System.out.println(solution.romanToInt("CCCXLVIII"));// 384 ->348

看了楼主的镇楼诗，我果断的点了个star

004题目的疑问

你好，在算法004的题目中，既然是两个已经排序好的数组中，要取这两个数组的中位数，为什么不直接去第一个数组的中位数，再去第二个数组的中位数，最后取这两个中位数的平均值，不就是结果了吗？感觉看004的算法有点复杂。我这样的算法是否有什么问题，还望告知，谢谢！

也在开始走这条LeetCode的路，加油共勉~

很用心，手动点赞

/note/043/README.md Multiply Strings

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int l1 = num1.length(), l2 = num2.length(), l = l1 + l2;
        char[] ans = new char[l];
        char[] c1 = num1.toCharArray();
        char[] c2 = num2.toCharArray();
        for (int i = l1 - 1; i >= 0; --i) {
            int c = c1[i] - '0';
            for (int j = l2 - 1; j >= 0; --j) {
                ans[i + j + 1] +=  c * (c2[j] - '0');
            }
        }
        for (int i = l - 1; i > 0; ++i) { // 这个地方写错了 应该是--
            if (ans[i] > 9) {
                ans[i - 1] += ans[i] / 10;
                ans[i] %= 10;        
            }
         }
        StringBuilder sb = new StringBuilder();
        int i = 0;
        for (; ; ++i) if (ans[i] != 0) break;
        for (; i < ans.length; ++i) sb.append((char) (ans[i] + '0'));
        return sb.toString();
    }
}

如何在Intellij里面run?

设置了java sdk，但是设置不了main class，所以run不了。谢谢解答

判断回文数

class Solution {
public boolean isPalindrome(int x) {
if (x < 0 || (x != 0 && x % 10 == 0)) return false;
int halfReverseX = 0;
while (x > halfReverseX) {
halfReverseX = halfReverseX * 10 + x % 10;
x /= 10;
}
return halfReverseX == x || halfReverseX / 10 == x;
}
}

什么时候会走halfReverseX == x 这条return 路径呢？？

那些公司的目标题目序号，你是怎么知道的？

好屌的样子[比心]

树的打印函数好像对null处理有点问题，麻烦大佬帮看下

例如Leetcode94题，输入: [1,null,2,3]，调用TreeNode.print( )函数，3会丢失

67.二进制求和，重复判断

不需要在循环里再判断p1,p2是否大于等0了，循环条件就是p1 >=0 && p2 >=0。
while (p1 >= 0 && p2 >= 0) {
//carry += p1 >= 0 ? a.charAt(p1--) - '0' : 0;
//carry += p2 >= 0 ? b.charAt(p2--) - '0' : 0;
carry += a.charAt(p1--) - '0';
carry += b.charAt(p2--) - '0';
sb.insert(0, (char) (carry % 2 + '0'));
carry >>= 1;
}

注释的这两行代码，真的困扰了我 ~~，我都去复习运算符的顺序了，汗。

链表中的数值两两交换

class Solution
{
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode node = head.next;
head.next = swapPairs(node.next);
node.next = head;
return node;
}
}

为什么 if (head == null || head.next == null) 两个条件交换一下顺序就会报错呢？？

_028#优化建议

public int strStr(String haystack, String needle) {
    int l1 = haystack.length(), l2 = needle.length();
    if (l1 < l2) return -1;
    for (int i = 0; ; i++) {
        //if(i+l2>l1)return -1;
        for (int j = 0; ; j++) {
            if (j == l2) return i;
            **if (i + j == l1) return -1;**
            if (haystack.charAt(i + j) != needle.charAt(j)) break;
        }
    }
}

使用第5行取代第8行，减少循环次数。
假如needle只有最后一个字符不同，原代码几乎需要把needle遍历完才进入第8行的分支

第一题思路一的解有问题

刚刚开始看leetcode，大家共勉。
第一题思路一
for (int i = 0; i < nums.length; ++i) {
是否应该是 i < nums.length - 1会更好

_008#优化建议

32位正整数最大值 2^31-1 = 2147483647 负整数最大值-2^31 = -2147483648,判断是否溢出时要区分符号，正数时tmp>7则溢出，负数时tmp>8 才溢出。同时也避免了一次取余操作。

021的题目有点问题吧？？

题目本意应该是移除数组中的相同的元素，是不是弄错了？

招聘贴：阿里巴巴消息业务/基础团队招聘（校招/社招）

我们团队都是Java哈，也有cpp、ios和android，大家刷好题了就可以随时来碾压我们了。欢迎大家加入。
招聘, 微信：kerisle，
大家也可以直接发邮件
[email protected]

关于第一题思路1的表述问题

我看了代码之后才知道是怎么回事，这样表述如何？
利用 HashMap 作为存储，键为目标值减去当前元素值，索引为值，比如 i = 0 时，此时首先要判断 nums[0] = 2 是否在 map的key 中，如果不存在，那么插入键值对 key = 9 - 2 = 7, value = 0，之后当 i = 1 时，此时判断 nums[1] = 7 已存在于 map的key 中，那么取出此时 value = 0 作为第一个返回值，当前 i 作为第二个返回值，具体代码如下所示。

还有虽然思路二只有一个循环，但是为什么我测试了一个发现思路二反而更慢？

public class P01TwoSum {

/**
 * @param args
 */
public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] nums = {2, 7, 11, 15}; int target = 18;
	
	//伪代码  
	long startTime=System.nanoTime();   //获取开始时间  
	int[] res = twoSum1(nums, target);  //测试的代码段  
	long endTime=System.nanoTime(); //获取结束时间
	
	System.out.println("程序运行时间： "+(endTime-startTime)+"ns"); 
	
			
	long startTime1=System.nanoTime();   //获取开始时间  
	int[] res2 = twoSum2(nums, target);  //测试的代码段  
	long endTime1=System.nanoTime(); //获取结束时间
	
	System.out.println("程序运行时间： "+(endTime1-startTime1)+"ns"); 
	
	
}

public static int[] twoSum1(int[] nums, int target) {
	
	for (int i = 0; i < nums.length; i++) {
		for (int j =i + 1; j < nums.length; j++) {
			if (nums[i] + nums[j] == target) {
				return new int[] {i,j};
			}
		}
	}
	
	return null;
}

public static int[] twoSum2(int[] nums, int target) {
    int len = nums.length;
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < len; ++i) {
        if (map.containsKey(nums[i])) {
            return new int[]{map.get(nums[i]), i};
        }
        map.put(target - nums[i], i);
    }
    return null;
}

}

程序运行时间： 2356ns
程序运行时间： 36646ns

_107-Solution.java-L27编译报错

我的jdk是1.7版本，请问是JDK版本的问题吗？

挺好的，楼主很用心，点赞