LeetCode-Reverse Nodes in k-Group

这道题是上一道题的一般情况。题目是给出一个k,颠倒这个链表中每k个元素的顺序,返回修改后的链表。(不太好解释,可以参考原题)。

这里我用的是比较笨,但是比较好理解的办法。从头节点开始,我check是否还有足够的节点供我颠倒,如果有,那么返回这k个元素的尾节点(也就是颠倒后的链表的头节点),然后颠倒链表。返回颠倒后的链表的尾节点。这样我们既有了每个sub链表的头节点又有了每个sub链表的尾节点,连起来就行了。代码如下:


public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;
    ListNode tail = null;

    while((tail = tailOfCurrentSet(cur, k)) != null) {
        ListNode next = tail.next;
        ListNode newTail = reverseNextK(cur, k);
        newTail.next = next;
        cur = newTail;
    }
    return dummy.next;
}

private ListNode tailOfCurrentSet(ListNode cur, int k) {
    ListNode temp = cur;
    while(temp.next != null && k > 0) {
        temp = temp.next;
        k --;
    }
    return k == 0 ? temp : null;
}

private ListNode reverseNextK(ListNode head, int k) {
    ListNode cur = head.next;
    ListNode tail = head.next;
    ListNode reverse = null;
    int count = 0;

    while(count < k) {
        ListNode next = cur.next;
        if(reverse == null) {
            reverse = cur;
            reverse.next = null;
            cur = next;
        } else {
            cur.next = reverse;
            reverse = cur;
            cur = next;
        }

        count ++;
    }
    head.next = reverse;
    return tail;
}

LeetCode-Swap Nodes in Pairs

题目要求给出一个链表,将相邻的两个节点交换位置,并返回交换位置之后的链表头。

这里还是推荐一下在链表头节点之前加一个dummy node的办法,这样可以避免表头这个特殊情况的check,从而使代码更加简洁。返回的时候也方便,只需要返回这个dummy node的next即可。

具体如何交换并不需要做太多的赘述,比较简答。代码如下:


public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;

    while(cur != null && cur.next != null && cur.next.next != null) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = cur.next.next;
        cur.next.next = next;
        cur = cur.next.next;
    }
    return dummy.next;
}

LeetCode-Merge k Sorted Lists

这道题明显是之前那道merge 2 sorted lists的升级版,不过思路是一样的。

这里我们用一个priority queue把所有链表的头节点存进去。每次我们都取出最小的节点。当最小的节点被取出之后,如果它后面存在节点,那么我们继续把这个节点存进去。直到这个priority queue为空。代码如下:


public ListNode mergeKLists(ListNode[] lists) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;

    PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(10, new Comparator<ListNode>() {
        @Override
        public int compare(ListNode l1, ListNode l2) {
            return Integer.compare(l1.val, l2.val);
        }
    });

    for(ListNode head: lists) {
        if(head != null) {
            queue.add(head);
        }
    }

    while(!queue.isEmpty()) {
        ListNode min = queue.poll();
        cur.next = min;
        cur = cur.next;
        if(min.next != null) {
            queue.add(min.next);
        }
    }
    return dummy.next;
}

LeetCode-Generate Parentheses

题目要求:给出一个数n,返回所有由n对括号组成的合法的字符串。

因为要求返回所有的,所以这里我们用recursion。首先我们一个一个append括号。我们用两个变量frontLeft 和 endLeft分别表示剩余的前括号和后括号的数量。当这两个数都合法的时候,我们的下一个选择可以是前括号,也可以是后括号。这里我们递归。假如不合法,那么我们终止递归。

思路比较简单,直接贴代码了:


public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<String>();
    generate("", n, n, result);
    return result;
}

public void generate(String str, int frontLeft, int endLeft, List<String> result) {
    if(frontLeft == 0 && endLeft == 0) {
        result.add(str);
        return;
    }
    if(frontLeft < 0 || endLeft < 0 || frontLeft > endLeft) {
        return;
    } else {
        generate(str + "(", frontLeft - 1, endLeft, result);
        generate(str + ")", frontLeft, endLeft - 1, result);
    }
}

LeetCode-Merge Two Sorted Lists

题目是归并两个有序的链表。这本身是merge sort的一步,思路也很清晰,所以并没有什么难度,直接贴代码了,这里我用了之前推荐的dummy node的方法,避免了check那一个链表的头节点是归并后的链表的头节点,代码会更简洁些:


public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    ListNode cur1 = l1;
    ListNode cur2 = l2;

    while(cur1 != null && cur2 != null) {
        if(cur1.val <= cur2.val) {
            cur.next = cur1;
            cur1 = cur1.next;
        } else {
            cur.next = cur2;
            cur2 = cur2.next;
        }
        cur = cur.next;
        cur.next = null;
    }

    cur.next = cur1 != null ? cur1 : cur2;

    return dummy.next;
}

 

LeetCode-Valid Parentheses

题目要求给出一个由各种括号组成的字符串,返回一个boolean判断这个字符串的括号们是否合法。

非常简单的一道题,思路也非常清晰,是用一个stack或者类似stack的东西。当遇到前括号的时候入栈;如果遇到了后括号,那么出栈并比较括号是否为一对。这个stack也可以用其他东西来替代,不过思路大同小异,代码如下:


public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();

    for(int i = 0; i < s.length(); i ++) {
        char cur = s.charAt(i);
        if(cur == '(' || cur == '[' || cur == '{') {
            stack.push(cur);
        } else {
            if(cur == ')') {
                if(stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            } else if(cur == ']') {
                if(stack.isEmpty() || stack.pop() != '[') {
                    return false;
                }
            } else {
                if(stack.isEmpty() || stack.pop() != '{') {
                    return false;
                }
            }
        }
    }
    return stack.isEmpty();
}

LeetCode-Remove Nth From End

从这道题开始加入了一些链表的题。这里介绍一个做链表题的好办法,我也是在别人的代码里看到的---在链表头之前再加一个dummy node。链表的题在很多情况下都是需要对第一个node进行单独处理的,这样显然不elegant。在输入链表的链表头之前再加一个节点在有些时候就能避免单独的处理。

再来说这道题,题目要求移除一个链表中的倒数第n个节点。并没有什么难度, 所以毫无疑问是easy。这道题肯定要求是one pass的,所以方法是用两个节点从头开始走,第一个先走n步,然后第二个开始走,当第一个到达最后一个节点时,第二个节点正好到达第倒数n + 1个节点。这是我们把这个节点的下下个节点赋给这个节点的下个节点,就完成了移除倒数第n个节点的操作。代码如下:


public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = head;

    for(int i = 0; i < n - 1; i ++) {
        second = second.next;
    }

    while(second.next != null) {
        first = first.next;
        second = second.next;
    }

    first.next = first.next.next;

    return dummy.next;
}

LeetCode-4 Sum

这又是一个n sum的问题,这道题的解法和3 sum应该是一样的,只不过多了一个外层的循环。最内层依然用一个left和一个right来简化,注意对于相邻两个元素相同的情况我们continue循环直到最后一次出现,我们只处理这个最后出现的元素。这样就可以避免重复。代码如下:


public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    Arrays.sort(nums);

    for(int i = 0; i < nums.length - 3; i ++) {
        if(i == 0 || nums[i] != nums[i - 1]) {
            for(int j = i + 1; j < nums.length - 2; j ++) {
                if(j == i + 1 || nums[j] != nums[j - 1]) {
                    int left = j + 1;
                    int right = nums.length - 1;

                    while(left < right) {
                        if(nums[i] + nums[j] + nums[left] + nums[right] == target) {
                            if(nums[left] == nums[left + 1] && right != left + 1) {
                                left ++;
                                continue;
                            } else {
                                List<Integer> quad = new ArrayList<Integer>();
                                quad.add(nums[i]);
                                quad.add(nums[j]);
                                quad.add(nums[left]);
                                quad.add(nums[right]);
                                result.add(quad);
                                left ++;
                            }
                        } else if(nums[i] + nums[j] + nums[left] + nums[right] > target) {
                            right --;
                        } else {
                            left ++;
                        }
                    }
                }
            }
        }
    }
    return result;
}

为生活忙碌

终于在忙碌中度过了2015的上半年,虽然这半年来发生的事情太多让我猝不及防,但是好歹一切都算是过去了。接下来是四天的小假期,下午组里的弟兄们一起去看了个电影,也算是庆祝下顺利度过了这个忙碌的季度。或许组里的大部分人会选择休息下,但是由于有刷题的压力我可能休息不了。

已经好久没有更新leetcode有关的日志了,但这并不代表我没有在刷,相反,由于没有更新日志我每天可以多做一道题了,因为有时候写这些思路的时间比我做题的时间还要长。现在的进度大概是刷了一半,而写了思路的远远少于这个数字。每天做题的时间也由原来的每天晚上改成了每天早晨。这一是因为写了一天代码之后脑子总是混混沌沌的解题思路不太清晰,二是因为最近睡眠不好早晨起的总是特别早。那么干脆就早点睡早点起趁脑子清醒的时候做最需要脑子的事情,反正工作上的代码并不需要耗费太多的脑力。这样做的结果就是每天都觉得过得很累,起个大早写两个小时代码,然后开车去上班,又是写一天代码。不过虽然累但是推的速度确实比以前快了不少。照这个进度大概可以在招聘季开始前刷完一遍多,应该是差不多够用了(hopefully)。

h1b没抽中的通知也正式下来了,虽然早就知道了是这个结果但是当律师把那个回执的扫描件发给我的时候心里还是挺难过的,有一种失去了老天宠爱的感觉。也许人生就是如此,无论你再怎么努力,操控不了的东西终究还是操控不了。偶尔每天早晨起床想起这件事的时候还会叹一口气。本该是抽中之后谋划如何回国度假的节奏,但是现在只能一边抽出边角的时间来刷题,一边省下自己的假期留给以后可能的on site。而且最近看起来即使是旗舰公司对l1的政策也是越来越不友好,即使跳槽成功能不能给办l1还是个未知数。而对我来说唯一的办法就是:走一步看一步。写到这里只能再次叹一口气。每当周围的美国人抱怨这抱怨那的时候,我都会苦笑着说一句“at least you don’t have to worry about whether you can stay here”。

托某苹果员工的福,我也终于换了台15寸的macbook pro,确实比以前的thinkpad好使很多也轻了很多。也是可以躺在床上把电脑放到肚子上写代码了。而且os x的terminal明显比windows那个不知道是什么吊东西的cmd好用了太多。买macbook的另外一个原因是想试试swift,至少在自己需要的时候能给自己的手机写一个不算太复杂的app。不过从用惯了的windows过度到os x也并不是那么平滑,至少找一个能播放avi的播放器就花了我一些时间。os x支持的软件应该也比windows少很多。不过鉴于这台电脑基本是写代码用的,要求也不是那么高,要娱乐的话换回windows的电脑就是了。

我的健身大计也终于是在2015年的第二季度开始了,雇了一个personal trainer帮我制定计划和矫正动作,虽然有点贵但我觉得这些钱还是有必要花的。想到自己不抽烟不喝酒不怎么买衣服现在连零食吃的也少了,那么投入点钱在健身上还是完全可以接受的,毕竟是为了long term的健康着想。虽然还没看出肌肉的形状但是胸似乎是比以前大了些, 肚子也比以前小了些,体重还涨了五斤。姑且认为这是把一部分肥肉转化成了肌肉。每次上健身课都是一种折磨,但是想到自己花了不少钱不应该偷懒还是咬牙坚持过来了。trainer每次都会说我很aggressive,我姑且认为他是在夸奖我。今天成功的把dead lift的成绩提升到了185lbs,也就是自己的体重,还被教练录了个视频发到了他的instagram上。

篮球则是一如既往的没什么进展。最近天气实在太热,折返跑跑个五六回合就喘得和狗一样。进攻也是没什么力气,速度也提不起来。再加上打的场子对抗本来就比较厉害,所以打18个球只进一两个也是常有的事情。而且我们每周打球是在周三,而周二和周四都要去健身,体力没法完全恢复。不过打球本身也就是图个乐,想要打的和那些每天都花几个小时打球的黑大哥一样好也不太现实,玩得高兴就好了。

如果说这上半年有什么可以让我开心点的事情,那莫过于鼓起勇气成功的把jgh的微信加了回来。但事实证明这并没有什么卵用,而且希望越大失望越大。除了有了朋友圈的访问权限其他似乎并没有什么变化。无法发信息和发了不回似乎并没有什么本质的区别,如果说真有那么后者可能还更惨一些。留给我的似乎也只有试着跑去德州一起吃个饭这一种方法,但是总感觉以现在这种态势希望有些渺茫,而且失败了几乎意味着可以彻底死心了。最近总有人对我说女孩子是要靠吸引的,仔细想想确实很有道理,我本身也确实没有什么太大的吸引力,相较于那些长得比我帅,身材比我好又温柔体贴的白大哥来说,我这个英语都说不利索的人就是地道的矮穷挫。一个连获得合法身份都要操心的人,确实没办法奢求太多。也只能祝福她嫁个好人家了吧。

无论怎样我已经决定这次之后彻底翻页,或许听家里的相个亲也能遇到不错的妹子呢。但是好不甘心,好不甘心,好不甘心。

这就是乱七八糟的2015上半年,也是异常艰难的半年。最近在知乎看到了一句话:生活本来就不容易,如果你觉得容易,那是有人帮你承担了这份不容易。最近十分反感听到xxx也不容易,你得体谅下他。那tm到底是你容易还是我容易?当想要靠自己撑起一片天的时候,才发现这是真他妈难。

为爱情付出 为活着而忙碌
为什么而辛苦 我仔细纪录
用我的双眼 在梦想里找路

 

 

LeetCode-Letter Combinations of a Phone Number

个人感觉这是道没什么营养的题,大部分时间都花在了初始化那个数字与字母的映射上。思路很简单,递归。

题目要求给出一串数字,返回这些数字在九宫格键盘上所有可能的字母组合。

思路就是递归,每次减去一个数字,知道只剩下一个数字为止。把上一步返回的每个答案最后都加上当前数字所有可能的字母。代码如下:

public List<String> letterCombinations(String digits) {

    if(digits.length() == 0) return new ArrayList<String>();

    if(digits.length() == 1) {
        return getLetterFromDigit(digits);
    } else {
        List<String> last = letterCombinations(digits.substring(0, digits.length() - 1));
        List<String> result = new ArrayList<String>();
        List<String> letters = getLetterFromDigit(digits.substring(digits.length() - 1));
        for(int i = 0; i < last.size(); i ++) {
            for(int j = 0; j < letters.size(); j ++) {
                result.add(last.get(i) + letters.get(j));
            }
        }
        return result;
    }
}

private List<String> getLetterFromDigit(String s) {
    List<String> result = new ArrayList<String>();
    switch(s) {
        case "2":
            result.add("a");
            result.add("b");
            result.add("c");
            break;
        case "3":
            result.add("d");
            result.add("e");
            result.add("f");
            break;
        case "4":
            result.add("g");
            result.add("h");
            result.add("i");
            break;
        case "5":
            result.add("j");
            result.add("k");
            result.add("l");
            break;
        case "6":
            result.add("m");
            result.add("n");
            result.add("o"); 
            break;
        case "7":
            result.add("p");
            result.add("q");
            result.add("r");
            result.add("s");
            break;
        case "8":
            result.add("t");
            result.add("u");
            result.add("v");
            break;
        case "9":
            result.add("w");
            result.add("x");
            result.add("y");
            result.add("z");
            break;
        default:
            break;
    }
    return result;
}