查看: 4650|回复: 41
想问问大家，你在面试中遇到过leetcode上hard难度或者更难的算法题吗？
精华主题学分
中级农民-加分请看右边栏-多参与|分享|记录|反馈, 积分 486, 距离下一级还需 14 积分
在线时间 小时
注册一亩三分地论坛，查看更多干货！
才可以下载或查看，没有帐号？
我本科毕业时找过工作，最难只碰见过KMP匹配、快速选择算法。（悲剧的是当时算法底子太差，要么不会，要么写不对）
大家有在实际面试中遇到那种平时都觉得不简单，现场被问更是冷汗直冒的题吗？
精华主题学分
在线时间 小时
终于把&The Skyline Problem&搞定了，这是我所有leetcode题目里耗时最久，出bug最多的一题。
话说最近才发 ...
那是，这道题我可是花了好长时间写出来的，怎么能让你们轻易通过
精华主题学分
在线时间 小时
补充：面试官刻意刁难、强行装X的情况不算在内。
精华主题学分
在线时间 小时
我看的面经里，大家好像都提到，只有在onsite时一些公司会考hard level的题目，比如LRU cache
精华主题学分
在线时间 小时
本帖最后由 zhuli 于
20:04 编辑
终于把&The Skyline Problem&搞定了，这是我所有leetcode题目里耗时最久，出bug最多的一题。
话说最近才发现这题是stelllari出的啊，赞~~&&
精华主题学分
在线时间 小时
这题再次用到了map的强大特性：O(log(N))时间完成增、删、改、查、统计个数、求最大、最小。
这题中这些特性全都用到了，堪称量身定做。
精华主题学分
在线时间 小时
同学去onsite有被问到一个比较难的DP问题。最初的题目是CC150里面的Stack of Boxs，之后的followup是箱子如果能转，怎么求最大高度。
精华主题学分
在线时间 小时
本帖最后由 zhuli 于
22:09 编辑
同学去onsite有被问到一个比较难的DP问题。最初的题目是CC150里面的Stack of Boxs，之后的followup是箱子如 ...
因为可以旋转，所以把每个箱子的有三种不同可能，每次DP时也就要求三种对应的最大高度，对吗？
经典的动归，这儿有个同类型的例题。给定条件稍有不同。
精华主题学分
在线时间 小时
我看的面经里，大家好像都提到，只有在onsite时一些公司会考hard level的题目，比如LRU cache
双向链表的确考验人的细心程度~
精华主题学分
在线时间 小时
那是，这道题我可是花了好长时间写出来的，怎么能让你们轻易通过
卧槽！你出的！膜拜膜拜。
精华主题学分
在线时间 小时
word ladderII好难啊...
精华主题学分
在线时间 小时
本帖最后由 zhuli 于
14:16 编辑
那是，这道题我可是花了好长时间写出来的，怎么能让你们轻易通过
话说怎么确定一个问题可达到的最优复杂度？比如Maximum Subarray III这题，O(N^3)的DP解很快就能想出来，但我想了一个多钟头也没想出O(N^2)的，网上搜了也没有找到平方的解。
有什么比较严谨的办法证明有或者没有吗？难道只能靠脑子想？
更新：刚刚搜了搜论文，说有O(n + k)的解。但是限定条件不同，论文中允许子数组重叠，所以和这个不是一个问题。
再更新：花了俩钟头，终于搞出了O(N * K)的DP解法，怒贴代码~~// O(k * n) DP with O(n) space, yes!
#include &algorithm&
#include &climits&
class Solution {
public:
& & /**
& &&&* @param nums: A list of integers
& &&&* @param k: An integer denote to find k non-overlapping subarrays
& &&&* @return: An integer denote the sum of max k non-overlapping subarrays
& &&&*/
& & int maxSubArray(vector&int& nums, int k) {
& && &&&vector&int& &a =
& && &&&int n = a.size();
& && &&&if (k &= 0 || k & n) {
& && && && &return 0;
& && &&&}
& && &&&vector&vector&int& & dp(2, vector&int&(n, 0));
& && &&&vector&int& mx(n, 0);
& && &&&int i,
& && &&&int f,
& && &&&
& && &&&mx[0] = dp[0][0] = a[0];
& && &&&for (i = 1; i & ++i) {
& && && && &dp[0][i] = max(dp[0][i - 1], 0) + a[i];
& && &&&}
& && &&&mx[0] = dp[0][0];
& && &&&for (i = 1; i & ++i) {
& && && && &mx[i] = max(mx[i - 1], dp[0][i]);
& && &&&}
& && &&&
& && &&&f = 1;
& && &&&nf = !f;
& && &&&for (i = 1; i & ++i) {
& && && && &dp[f][i] = dp[nf][i - 1] + a[i];
& && && && &for (j = i + 1; j & ++j) {
& && && && && & dp[f][j] = max(dp[f][j - 1], mx[j - 1]) + a[j];
& && && && &}
& && && && &mx[i] = dp[f][i];
& && && && &for (j = i + 1; j & ++j) {
& && && && && & mx[j] = max(mx[j - 1], dp[f][j]);
& && && && &}
& && && && &f = !f;
& && && && &nf = !f;
& && &&&}
& && &&&return mx[n - 1];
& & }
};复制代码
精华主题学分
在线时间 小时
那是，这道题我可是花了好长时间写出来的，怎么能让你们轻易通过
我在13年10月左右面微软OS组，第四面挂在这题。。
精华主题学分
在线时间 小时
这题还谁出的。。。。geekforgeek上一百年前的原题。。。。
精华主题学分
在线时间 小时
本帖最后由 zhuli 于
15:57 编辑
这题还谁出的。。。。geekforgeek上一百年前的原题。。。。
我说的是leetcode上那题是stellari添加的。。另外，咱能愉快地交谈吗，一百年前geekforgeek还没开张
没说leetcode所有题都是原创，比如LCA问题才刚刚添加，然而别的OJ都见过无数遍了
精华主题学分
在线时间 小时
本帖最后由 stellari 于
17:34 编辑
话说怎么确定一个问题可达到的最优复杂度？比如Maximum Subarray III这题，O(N^3)的DP解很快就能想出来， ...
应该是不存在“确定一个问题可达到的最优复杂度”的一般方法的，否则我们也不需要一道一道地去证明哪些问题是NP-Hard的了。
Maximum Subarray III这题的思路和Sell/Buy Stock IV的思路基本一样。维护两个二维DP数组，分别是：
global[ k ][ i ] -& 子数组0~i中，取k个subarray能达到的最大值。
local[ k ][ i ]&&-& 子数组0~i 中，取k个subarray，且第k个subarray一定包含元素 i 时能达到的最大值。
最后你会发现，local和global的状态转移方程都分别依赖于对方。并且每个元素都能在O(1)时间内算出，因此最后总时间是O(N*K)。
精华主题学分
在线时间 小时
应该是不存在“确定一个问题可达到的最优复杂度”的一般方法的，否则我们也不需要一道一道地去证明哪些问 ...
嗯，就是这样。
局部最优和全局最优交替更新。
精华主题学分
在线时间 小时
话说怎么确定一个问题可达到的最优复杂度？比如Maximum Subarray III这题，O(N^3)的DP解很快就能想出来， ...
赞，顺便贴一个我的版本：& & int maxSubArray(vector&int& nums, int k) {
& && &&&// write your code here
& && &&&int N = nums.size();
& && &&&vector&vector&int& & local(k+1, vector&int&(N+1, 0));
& && &&&vector&vector&int& & global(k+1, vector&int&(N+1, 0));
& && &&&
& && &&&
& && &&&for (int ic = 1; ic &= N; ++ic) {
& && && && &for (int ir = 1; ir &= ++ir) {
& && && && && & local[ir][ic] = max(global[ir-1][ic-1], local[ir][ic-1]) + nums[ic-1];
& && && && && & if (ir & ic)
& && && && && && &&&global[ir][ic] = max(local[ir][ic], global[ir][ic-1]);
& && && && && & else
& && && && && && &&&global[ir][ic] = local[ir][ic];
& && && && &}
& && &&&}
& && &&&
& && &&&return global[k][N];
& & }复制代码
精华主题学分
在线时间 小时
謝謝大家分享
精华主题学分
在线时间 小时
话说怎么确定一个问题可达到的最优复杂度？比如Maximum Subarray III这题，O(N^3)的DP解很快就能想出来， ...
看来leetcode现在是每个账户公开的题目不一样？比如说很早之前，有个同学告诉我leetcode有一道题目是数n里面含有数字为1的总数，我是前天才看到这道题目的。同样，你说的maximum subarray III我也没有看到啊。
<form method="post" autocomplete="off" id="fastpostform" action="forum.php?mod=post&action=reply&fid=84&tid=137853&extra=&replysubmit=yes&infloat=yes&handlekey=fastpost"
onSubmit="
// TODO Howard 11/3/2015
var sbtn = $('fastpostsubmit');
sbtn.disabled =
sbtn.innerHTML = ' 回复发表中... ';
sbtn.setAttribute('background', sbtn.style.background);
sbtn.setAttribute('bordercolor', sbtn.style.borderColor);
sbtn.style.background = '#C7C7C7';
sbtn.style.borderColor = '#8B8B8B';
var form =
// --product--
var isValid = fastpostvalidate(form, null, 0);
if(!isValid) reoverBtn();
return isV
// --product--
// --testing--
//setTimeout(function() {
// var isValid = fastpostvalidate(form, null, 0);
// if(!isValid) reoverBtn();
//}, 2000);
// --testing--
您需要登录后才可以回帖
回帖并转播
回帖后跳转到最后一页
一亩三分地推荐 /5
地主Warald亲手做你的申请，针对你的背景和目标，考虑申请、学习、就业、移民等系列问题，制定申请策略。
“offer”指全额奖学金，免学费全免+每月工资，Berkeley, CMU, JHU, UIUC, Gatech, UMich, UCLA, Columbia，欢迎观赏。
电子工程、计算机、统计、金数金工、化工等, Stanford, Berkeley, CMU, Cornell, Yale, Columbia, Chicago, Duke, UPenn, UIUC, Brown, UMich, JHU等
有留学、申请、找工、职业规划上的难题？先上论坛提问！
论坛考古也帮不上忙，发帖得到的回答仍然不够？电话找Warald来解答！
WARALD新书上市啦：《你不知道的美国留学》清华大学出版社，各大电商发售
Powered by6477人阅读
android（39）
找了一段时间的实习，总结一下LeetCode上面试出现频率比较高的题，只总结一部分，后续还会继续更新。
一、Two Sum
题意是给出一个数组，输出和为k的两个数。数组为无序的。
这道题的解题思路是先把数组排序，再用两个指针，分别指向头和尾，并算出头和尾的和s，再把s与k比较，如果s小于k，头指针往后移，如果s大小k，尾指针往前移。直到找到为止。如果头尾指针相遇还没找到，则证明不存在。
代码如下：
public class Main {
public static void main(String[] args){
int[] a = {1,3,2,1,4,5};
printK(a,5);
public static void printK(int[] array,int k){
if(array == null||array.length&=0){
int length = array.
Arrays.sort(array);
int start = 0;
int end = length - 1;
while(start & end){
while(array[start] == array[start+1]){
while(array[end] == array[end-1]){
if(array[start] + array[end] == k){
System.out.println(start+" "+end);
if(array[start]+array[end] & k){
if(array[start]+array[end] & k){
题意：从给定的数组中找三个数，让它们的和为0。输出所有可能。
如[1,3,-1,0,-3],那么输出[1,-1,0],[3,0,-3]。
思路：这个其实是以第一个题目为基础，首先进行排序。然后从数组第一位开始遍历，如第一位为1，在剩余后面的数组[3,-1,0,-3]中找出和为-1的两个数。用的就是第一题的思路。
public class Main {
public static void main(String[] args){
int[] array = {-1, 0,1,2,-1,-4};
print3Num(array, 0);
public static void print3Num(int[] array,int k){
Arrays.sort(array);
int length = array.
if(array == null||array.length&=0){
for(int i = 0;i &i++){
if(i&length-1&&array[i] == array[i+1]){
int num = k-array[i];
printK(array,i,length-1,array[i],num);
public static void printK(int[] array,int start,int end, int num,int k){
while(start & end){
while(array[start] == array[start+1]){
while(array[end] == array[end-1]){
if(array[start] + array[end] == k){
System.out.println(num+" "+array[start]+" "+array[end]);
if(array[start]+array[end] & k){
if(array[start]+array[end] & k){
三、Climbing Stairs
题意：有n级楼梯，你一次可以爬一级或两级，问爬上n级楼梯有多少种爬法。这是我一个同学面腾讯时被问到的问题。典型的斐波那契数列。
思路：因为一次你能爬一级或两级，所以除去第一次，n级的爬法f(n)可以等于f(n-1)+f(n-2)。求的就是斐波那契数列。
public class Main {
public static void main(String[] args){
System.out.print(climbStair(5));
public static int climbStairs(int n) {
if(n == 1){
if(n == 2){
return climbStairs(n-1)+climbStairs(n-2);
public static int climbStair(int n) {
int num1 = 1;
int num2 = 2;
int sum = 0;
if(n == 1){
if(n == 2){
for(int i = 2;i &i++){
sum = num1+num2;
num1 = num2;
分别实现了递归和非递归两种方式。
四，Merge Two Sorted Lists
题意：合并两个排序的链表
思路：先选出头小的节点作为新链表的起点，然后开始比较两个链表，那个值小就把链表指向它，被指向的链表往下移一位，新链表也要指向当前最后一个节点。当有一个链表遍历完了，就把另一个链表剩余部分全部赋到新链表的尾部，直接看代码更清晰。
public static ListNode merge(ListNode head1,ListNode head2){
if(head1 == null&& head2 == null){
return null;
if(head1 == null){
return head2;
if(head2 == null){
return head1 ;
ListNode head = null;
if(head1.val &head2.val){
head = head1;
head1 = head1.
head = head2;
head2 = head2.
ListNode result =
while(head1!=null && head2 !=null){
if(head1.val & head2.val){
head.next = head1;
head1 = head1.
head = head.
head.next = head2;
head2 = head2.
head = head.
if(head1 != null){
head.next = head1;
if(head2 != null){
head.next = head2;
五、Merge Sorted Array
题意：给两个数组n1[1,2,3],n2[3,4,5],把n2合并到n1中去，n1长度&=n1.length+m.length。
思路：这道题是不允许多用空间的。最后我想出的方法是从尾部开始比较，大的放到n1数组的最后一位。并把大数所在的数组尾部指针往前移，直到比较结束后，所有数就自然的在n1中排序了。
代码如下：
public class Main {
public static void main(String[] args){
int[] a = {0};
int[] b = {1};
merge(a,0,b,1);
for(int i = 0;i & a.i++)
System.out.print(a[i]+" ");
public static void merge(int[] nums1, int m, int[] nums2, int n) {
if(nums1==null||nums2==null||m&0||n&0){
int index = m+n-1;
int index1 = m-1;
int index2 = n-1;
while(index1&=0&&index2&=0){
if(nums1[index1]&nums2[index2]){
nums1[index--] = nums2[index2--];
nums1[index--] = nums1[index1--];
while(index1&=0){
nums1[index--] = nums1[index1--];
while(index2&=0){
nums1[index--] = nums2[index2--];
六、Valid Palindrome
题意：验证一个字符串是否为回文，只看字母（忽略其它字符），不分大小写。如“A man, a plan, a canal: Panama”就是一个回文，从头读和从尾往前读读出来是一样的。
思路：这道题思路其实很直接，就是两个指针，一个指向头部一个指向尾部，头部依次往后走，尾部依次往前走，一个个比，如果有不同就不是回文，否则如果两指针相遇了还没有不同的，就是回文。
public class Main {
public static void main(String[] args){
System.out.println(isPalindrome("......a....."));
System.out.println(isPalindrome("09"));
public static boolean isPalindrome(String s) {
s = s.toLowerCase();
if(s.length()&=1){
return true;
int length = s.length();
int start = 0;
int end = length-1;
while(start & end){
while(start&end&&!isAlpha(s.charAt(start))){
while(start&end&&!isAlpha(s.charAt(end))){
if(s.charAt(start)!=s.charAt(end)){
return false;
return true;
public static boolean isAlpha(char s){
if(s&='a'&&s&'z'||s&='0'&&s&='9'){
return true;
return false;
七 Valid Parentheses
题意：验证括号是否能正常闭合，如“()[]{}”是可以正常闭合的，但“(]”就是不正常的。
思路：用一个栈，如果是左括号入栈，如果是右括号，则出栈与右括号比，如果最后栈空了，也没的右括号了，则证明正确。
代码写得有点傻，可以继续优化：
public class Main {
public static void main(String[] args){
System.out.println(valid("["));
public static boolean valid(String str){
if(str.length() &= 0){
return false;
Stack&Character& stack = new Stack&Character&();
int length = str.length();
for(int i = 0;i &i++){
if(str.charAt(i) == '{'||str.charAt(i) == '['||str.charAt(i)=='('){
stack.push(str.charAt(i));
if(str.charAt(i)==')'){
if(!stack.isEmpty()){
char c = stack.pop();
if(c != '('){
return false;
return false;
if(str.charAt(i)=='}'){
if(!stack.isEmpty()){
char c = stack.pop();
if(c != '{'){
return false;
return false;
if(str.charAt(i)==']'){
if(!stack.isEmpty()){
char c = stack.pop();
if(c != '['){
return false;
return false;
if(stack.isEmpty())
return true;
return false;
八 Pow(x, n)
题意：就是实现一个Pow(x,n)乘方函数。
思路：首先要注意负数和倒数的问题。其次就是要合理的利用己经算出来的值来算下一个，如计算2^4，我们计算了2*2=4之后，就可以用4*4来计算2^4，减少计算的次数。
代码说话：
public class Main {
public static void main(String[] args){
System.out.println(pow(2,2));
public static double pow(double d,int n){
boolean flag = false;
boolean zhisuFlag = false;
zhisuFlag = true;
if(d == 0.0){
if(n%2==1&&d&0){
flag = true;
double result = power(d, e);
if(zhisuFlag){
result = 1/
result = -
public static double power(double d,int n){
if(n == 1){
if(n == 0){
int k = 1;
while (n/2&0) {
result = result*
result =result * power(pn, n-k);
九 Generate Parentheses
题意：给一个整数n，输出n对小括号所能组成的所有正常闭合的组合。如给出整数3，则输出 “((()))”, “(()())”, “(())()”, “()(())”, “()()()”。
思路：用递归实现所有情况，先定义left存左括号的个数，right存右括号数，首先输出一个“（”，如果剩余右括号多于左括号，可以输出右括号，否则只能输出左括号。
代码如下：
public class Main {
public static void main(String[] args){
generateParenthesis(1);
public static List&String& generateParenthesis(int n) {
ArrayList&String& aList = new ArrayList&String&();
if(n &= 0){
return null;
getList(n,n,"",aList);
public static void getList(int left,int right,String curStr,List&String& aList){
if(left & right){
if(left == 0&&right == 0){
aList.add(curStr);
if(left & 0){
getList(left-1, right, curStr+"(", aList);
if(right & 0){
getList(left, right-1, curStr+")", aList);
题意：判断一棵树是不是BST树。即判断一棵树的左节点是否全比根节点小，所有右节点是否全比根节点大。
思路一：最直接的方法是用中序遍历，发现不是有序的就不是BST，如果是有序那就是BST。
代码如下：
public static boolean isValidBST(TreeNode root) {
if(root == null){
return true;
boolean a = isValidBST(root.left);
if(pre!=null&&pre.val&=cur.val){
return false;
boolean b = isValidBST(root.right);
return a&&b;
思路二：递归遍历子节点，在遍历过程中分别给左子树和右子树设置左屏障和右屏障，什么意思呢？就是保证左子树的右屏障为根节点，也就是最大值小于等于根节点。右子树左屏障为根节点的值，即最小值大小等于根节点的值。
代码如下：
public static boolean isValidBST(TreeNode root) {
int left = Integer.MIN_VALUE;
int right = Integer.MAX_VALUE;
if(root == null){
return true;
if(root.left == null&&root.right==null){
return true;
return validBinary(root, left, right);
public static boolean validBinary(TreeNode head,int left,int right){
if(head == null){
return true;
if(head.val&=left)
return false;
if(head.val&=right)
return false;
return validBinary(head.left,left,head.val)&&validBinary(head.right,head.val,right);
就到这吧，整理的好累，其实LeetCode刷了有一些了，但常见的笔试面试题也就那么几类，个人觉得应该不会出太难。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：99408次
积分：1431
积分：1431
排名：千里之外
原创：37篇
评论：33条
Name: Linxj
文章：10篇
阅读：30757
文章：34篇
阅读：88274
(1)(3)(5)(3)(5)(7)(6)(3)(1)(3)(2)(1)(4)有人在刷leetcode么，現在面试必问的东东 - CNode技术社区
这家伙很懒，什么个性签名都没有留下。
有人在刷leetcode么，現在面试必问的东东
leetcode的题尽快地刷几遍是有好处的，刚入行的可以练练算法，好久不面试的工程师可以适应一下面试题的风格，面试别人跟自己去面试还是不同的。面试跟平时工作写代码也不一样。
leetcode也就只对面试的coding部分有用，对与design部分，architecture部分的面试基本是无用的，这些基本要靠工作经验和对行业的了解。
CNode 社区为国内最专业的 Node.js 开源技术社区，致力于 Node.js 的技术研究。
服务器赞助商为
，存储赞助商为
，由提供应用性能服务。
新手搭建 Node.js 服务器，推荐使用无需备案的