Leetcode题目分类

Leetcode Summary

Posted by Jerry on January 5, 2017

不积跬步无以至千里,不积小流无以成江河。每天一道LeetCode

位操作(Bit Manipulation)

  1. 461.Hamming Distance 求两个整数汉明距离,2个整数转换为2进制有多少位不相同。
  2. 477.Total Hamming Distance 给定一个整数数组,求数组内两两整数的汉明距离的总和。关键整数最多在于32位
  3. 476.Number Complement给定一个整数,将其二进制数每位取反,并返回该二进制数,如5,输出则是2.如1,输出0.注意给定整数二进制不会以0开始
  1. 473. Matchsticks to Square给定一堆数,划分为四堆,每堆数总和相等。(partition problem
  2. 140. Word Break II 难度:Hard
  3. 529. Minesweeperdiscuss上的解法总是让人兴奋不已(The code in discuss is always mind blowing….)难度: Medium
This is a typical Search problem, either by using DFS or BFS. Search rules:
If click on a mine ('M'), mark it as 'X', stop further search.
If click on an empty cell ('E'), depends on how many surrounding mine:
2.1 Has surrounding mine(s), mark it with number of surrounding mine(s), stop further search.
2.2 No surrounding mine, mark it as 'B', continue search its 8 neighbors.

动态规划(Dynamic Programming)

  1. 139.WordBreak判断字符串是否可以由字符串集合中元素组成。
  2. 472. Concatenated Words判断字符串数组中可以由其他字符组成的字符串集合,可以由139题结合起来做。
  3. LeetCode39题在递归里的第5道题,有必要看一看

递归、回溯(Backtracking)

  1. 78. Subsets给定一个集合(没有重复的数字),求其所有子集
  2. 90. Subsets II给定一个集合(有重复的数字),求其所有不重复的子集,相对于上题添加一个条件有重复数字,所以产生的子集会重复,解决方法用HashSet处理List,或者,if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
  3. 46. Permutations给定一个集合(没有重复的数字),求全排列。正常解法和上面两题相似,用回溯。查看discuss后发现,用一个简单迭代。n个数的全排列就相当于n-1个数的全排列后,加上第n个数在每个位子上的排列。难度: Easy
如[1,2,3]
首先添加1
{[1]}
再添加2时有两种可能即在1的前面和1的后面,
{[1,2],[2,1]}
再添加3时,则有六种情况,恰好为[1,2,3]的全排列3!个
{[3,1,2],[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1]}
  1. 47. Permutations II这题相对于上一题,加上重复数字,难度感觉上升了许多。关键在于利用一个数组保存数组哪些是使用过的哪些是未使用的。不能直接用contains()函数来判断了。难度: Medium
  2. 39. Combination Sum给定数组(没有重复的数字),和一个目标数字,求所有由数组中数的组成的集合(数组内数字可以重用)。也可以用DP算法难度:Medium
  3. 40. Combination Sum II给定数组(可能有重复的数字),和目标数字,求所有组合,使得组合的和等于目标数字。数组中的数字只能用一次

  4. 60. Permutation Sequence给定1~n,进行排列组合,按照排列后的整数的大小进行编号,求编号为k的序列.这道题思路想到了,可是没实现出来。难度: Medium

  5. 526. Beautiful Arrangementdivisible意思可被整除。类似于第一题的回溯,关键在于将n理解分配到数组里去。难度: Medium

链表(Linked List)

  1. 24. Swap Nodes in Pairs给定一个链表,交换相邻的结点,每个节点只交换一次。 自己完成,提交好几次才成功,用几个指针,分别用来干啥要清楚。Discuss里有个递归算法很棒。 难度: Easy

数组 or 字符串(Array or String)

  1. 31. Next Permutation求给定数字序列的next permutation,next permutation意思是求比当前序列大的序列中最小的序列,如果当前序列是最大值,则求其逆序。 关键求从右到左找到第一个逆序的值i(这里i为数组下标),然后从右向左找到第一个比i值大的数,并交换ij,最后由于ij交换后下标大于i的一定是逆序,所以将其逆转回来,这样就求解出来了
如[1,3,4,4,2,1]
找到逆序3<4
接着找到下标为3的值4
交换[1,4,4,3,2,1]
最后逆序[1,4,4,1,2,3]这样就得到next permutation

  1. 485. Max Consecutive Ones给定一个二进制的数组(数组内数字只有0,1),求最大连续的1的数目是多少。 难度:Easy

  2. 496. Next Greater Element I给定两个数组ABAB的子数组,且A,B中数字不重复,求A中每个数字的在B中对应的数字的下一个大的数字,若没有则为-1.这题用到Map,将数组B的每一个数字作为Mapkeyvalue值就为比key大的下一个数字,若没有则value-1,当时花了20分钟做出来,我做的时间复杂度为O(n^2).看到discuss上的有答案为O(n),发现确实比较巧妙,他的方法用的是一个Map和一个栈,也是将B来Map,巧妙在于他用一个栈来查找比当前大的下一个数字.这方法太巧妙了难度:Easy 自己完成

Input: A=[4,1,2] , B=[1,3,4,2]
Output: [-1,3,-1]
  1. 506. Relative Ranks题目不难,就是排序。不过学到一个,java中数组有个clone方法,用来复制数组。这回discuss上有个细节比我做的好,第一个就是数组复制问题,第二个就是map时可以直接解决问题,自己强行加了一个reverse方法。 难度:Easy 自己完成

  2. 503. Next Greater Element II这题与第三题有点相似,不同的地方在于只有一个数组,但数组是“圆的”,查找下一个大的数时,可以绕一圈求.这题目做起来并不难,但查看discuss发现,也有一个用Stack的时间复杂度为O(n),类似第三题的解法,但也有不同的地方,为了解决“圆的”问题,用了一个2*n的index来解决,但注意只有<n时才进栈. 难度:Easy 自己完成

  3. 498. Diagonal traverse数组里面找规律. 难度:Easy

  4. 504. Base 7给定一个整数返回七进制的字符串。-7则返回-10100则返回202注意StringBuilder有个reverse()方法用来逆转字符串。 难度:Easy 自己完成

  5. 520. Detect Capital,字符串匹配问题,第一时间想到的应该是用正则表达式,java中类java.util.regex中可以查看相应的正则表达式规则。我太蠢了,居然用字符串处理函数substring(),toUpperCase(),toLowerCase(),equals()来检测字符串,不过最后还是做出来了难度:Easy 自己完成

/*
//solution one
        if(word.toUpperCase().equals(word)||word.toLowerCase().equals(word)){
            return true;
        }else if(word.substring(1,word.length()).toLowerCase().equals(word.substring(1,word.length()))&&
        word.substring(0,1).toUpperCase().equals(word.substring(0,1))){
            return true;
        }else{
            return false;
        }*/

//solution two
return word.matches("[A-Z]+|[a-z]+|^[A-Z][a-z]+");
  1. 523. Continuous Subarray Sum判断是否数组里存在连续整数的和为给定值k的倍数。我是用个数组,但是时间复杂度是O(n^2).有个O(n)的时间复杂度和空间复杂度也为O(n)的算法。难度:Medium 自己完成
  2. 524. Longest Word in Dictionary through Deleting给定字符串和要匹配字符串,判断删除某些字符后存在匹配字符串中的最大字符串。不要遍历字符串,遍历匹配字符串难度:Medium
  3. 441. Arranging Coins给定一个整数n,要求返回一个整数s,其中(1+s)*s/2恰好小于等于n,若等于n则返回s,小于则返回s-1.如果按照题目本身叙述来做不难,用O(n)的时间复杂度就能很简单完成。而我这样叙述过后应该可以用二分查找,其时间复杂度为O(lg2_n).还有一种用数学的方式求解,直接用一个公式可以求解出来,就解一个一元二次方程。难度:Easy 自己完成 (x * ( x + 1)) / 2 <= n x = 1 / 2 * (-sqrt(8.0 * n + 1)-1) (负根舍去) or x = 1 / 2 * (sqrt(8.0 * n + 1)-1)

  4. 29. Divide Two Integers两个整数相除,不能用除号、乘号和取余符号。注意返回值也是整数。注意整数越界问题。难度:Medium

二叉树(Binary Tree)

  1. 513. Find Bottom Left Tree Value,给定非空二叉树,查找树中最底端最左的元素,返回该元素。层次遍历,广度优先遍历(Standard travel by level, Java BFS) 题目不难,但通过这次题目让我了解了java 中Queue队列使用,以及复习了层次遍历。Discuss中有个递归算法也还不错,其实最开始想的就是递归算法,但是没做出来。难度:Easy 自己完成
  2. 515. Find Largest Value in Each Tree Row,求出二叉树每层的最大值,以list形式返回。解法同上。难度:Easy 自己完成
  3. 493. Reverse Pairs使用二叉排序树解决题目问题,是一个思路,这思路值得学,可是会TLE(超时),其实用归并排序比较好,在归并过程中比较。归并算法可以用来求解,大小比较个数问题,相对于原位置来说。难度:Hard
  4. 307. Range Sum Query - Mutable可变的范围求和查询,给定一个数组,要求完成一个update()sumRange()函数。这题用的是线段树(segment tree)这里有详细的JAVA实现segment tree的说明与代码。第一次用,感觉不错,类似二叉树,但又有不同的地方。注意还有另外一种使用数状数组(Binary Indexed tree, fenwick tree)的解法。难度:Medium
  5. 530. Minimum Absolute Difference in BSTbst树中序遍历,求绝对值最小的值。难度:Easy

其他(Others)

  1. 495. Teemo Attacking题目那么长,做起来可简单了。给定一个数组A(按升序排序,没有重复的,都大于0)和一个大于0的整数n,Teenmo(LLP中的超级英雄)会在A数组中的每个时刻(数组中每个整数都是一个时刻)投放毒,投放毒的持续时间为n,最后求总的持续时间。难度:Easy 自己完成
Input: [1,4], 2
Output: 4

Input: [1,2], 2
Output: 3
  1. 501. Find Mode in Binary Tree注意Mode这个单词的意思是the value that occurs most frequently in a given set of data.,在给定数据中出现的次数最多的。题目要求如果有多个Mode都输出出来。通过这道题学会map按key和value进行排序难度:Easy 自己完成

  2. 284. Peeking Iterator重写Iterator类,添加一个peek方法,获取迭代器的下一个元素,但不将元素取出来。类似栈里面的getTop方法.解题关键在于利用next方法,因为next方法中是将元素取出来,我们直接将元素取出来,然后保存在类的成员中,这时hasNext方法返回值应当是判断成员的值是否为空.难度:Medium

  3. 365. Water and Jug Problem两只水桶量水问题,给定两个水桶体积分别为x,y,求能否量出z体积的水量(水无限,最后将z体积水,装到这两个桶中的一个或者多个).这题是个纯数学问题,需要数论的知识去证明Bézout’s identity定理(中文名,裴蜀定理).wiki上的解释如下:

Bézout’s identity (also called Bézout’s lemma) is a theorem in elementary number theory: let a and b be nonzero integers and let d be their greatest common divisor. Then there exist integers x and y such that ax + by = d. In addition,

  • the greatest common divisor d is the smallest positive integer that can be written as ax + by
  • every integer of the form ax + by is a multiple of the greatest common divisor d. for example: x = 4, y = 6, z = 8 => gcd(x,y) = 2, and 8 is multiple of 2, so this input is valid and we have:-1 * 4 + 6 * 2 = 8. 参考discuss上的。难度:Medium