分类目录归档：学习

《创业维艰》

概述

《创业维艰》是今年来读过的印象较为深刻的书籍。

作者本·霍洛维茨作为硅谷投资教父级的任务，本身是一个成功的创业者，带领自己创业的LoudCloud公司活过了互联网泡沫破碎的时代，本人也是个成功的投资家，Facebook, Instagram, Twitter, Airbnb这些赫赫有名的公司都有他的手笔。

书中提到的一些观点个人读到之后觉得较为有趣，虽然并不身处于创业公司，但是读到之后个人还是引发了自己的思考，了解了创业这个方向的另一面。书中作者的措辞和举例的诚恳态度相当让人印象相当深刻。

成功者的经历几乎无法复制，但是成功者的经验却是可能会后来者规避更多陷阱的有效参考。

在Kindle上入了中信的译本，对自己觉得有意思的一些观点做简要的记录。

书摘

寻找一个统一市场，其中只要有一个投资者点头，即可成功。即便30位投资者即便全都摇头拒绝也无关紧要。

笔记：毕竟拥有十足信心的人在少数，即便是到了投资者这个级别，依然也有跟风的现象存在。

每当大公司打算事实一个计划时，该计划总会落到某个人身上，而此人却极有可能延误整个计划。如果此人是工程师，他也许会因为等待上层觉得而踌躇不前；如果此人是管理者，他也许会因为自己无权做出关键性购买决定而犹犹豫豫。这些看似微不足道的踌躇和犹豫很有可能会造成致命的延误

笔记：指令要明确，分工也需要具体，不能存在灰色地带。

大多数管理书籍的重点都是如何正确做事，不要把事情搞砸。但我的经验却是，把事情搞砸之后，如何深刻的理解你必须要做的那些事情。

笔记：然而很多时候个人代替从搞砸了事情中的吸取教训所做的事情却是悔恨与烦恼，并无用处。多人已经提过类似观点，戴尔也说过试错并学习（然而戴尔现在……）。

自己的员工要自己亲自辞退，不能将这项工作推给人力资源部门或某个更严厉的同事，不能像电影《在云端》中雇佣一家外包公司完成。

笔记：last day会被记住。

正确解雇高管的第一步是，搞清楚自己为什么为公司招错了人

如果这名高管是由董事会成员举荐而来的，打电话个人通知就显得尤为重要

说话要果断，不要给讨论留下悬念

向董事会宣布最新的人事变动信息时，一定要用积极正面的方式，不要给人一种“一脚将高管踢出公司的感觉”

此时，你也许会担心员工们曲解消息，以为公司陷入了困境。不要在意这些反应

笔记：不做评论，基本不会用到这些内容，但是最后一条让人对这类事件可以用一个新的角度去看待管理者们的表现。

人，尤其是那些创造事物的人，只愿意听好消息。

笔记：码农的天然乐观是个毒药，要学会接受坏消息。

不要花时间懊悔过去，要将所有时间花在自己可以做的事情上，因为说到底，没人会在意。

笔记：一针见血，懊悔过去当真是对当前的不负责，累计了更多的债务。再次强调，没人会在意自己做错的事情。

和平时期的世界与你每天必须为生活苦苦挣扎的世界完全不同。和平时期，人们有时间关注言行是否得体、长远的文化影响以及人们的情感这类问题。而在你为生活苦苦挣扎的时期，最重要的是奋勇杀敌，带领自己的队伍安全抵达目的地。

笔记：想起《鸿门宴》，沛公曰：“今者出，未辞也，为之奈何？”樊哙曰：“大行不顾细谨，大礼不辞小让。如今人方为刀俎，我为鱼肉，何辞为！”。活下去是第一要素。理解了某些情况下领导的做法。

我们要依次管理好人、产品和利润。

笔记：人生产产品，产品带来利润？

在科技公司里，一旦员工流失，就会出现螺旋式的循环：公司价值下跌，最优秀的员工流失，公司价值继续下跌，最优秀的员工继续流失。这种恶性循环很难逆转。

笔记：论公司的倒掉。

未完待续。

LeetCode-118-119-121-141-155

发表回复

118 Pascal’s Triangle，119 Pascal’s Triangle II，121 Best Time to Buy and Sell Stock，141 Linked List Cycle，155 Min Stack 均较为简单，合并完成解题报告。

118 Pascal’s Triangle

概述

帕斯卡三角绘制。

分析

所谓帕斯卡三角，也叫做杨辉三角（也是贾宪三角……），解释可以在维基百科上得知。

那么只需按照定义，逐层生成即可。

解法

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (numRows <= 0) {
            return result;
        }

        List<Integer> prev = null;

        for (int i = 1; i <= numRows; ++i) {
            List<Integer> now = new ArrayList<Integer>();
            now.add(1);

            if (prev == null) {
                result.add(now);
                prev = now;
                continue;
            }

            for (int j = 0 ; j < prev.size() - 1; ++j) {
                now.add(prev.get(j) + prev.get(j + 1));
            }

            now.add(1);
            result.add(now);
            prev = now;
        }

        return result;
    }
}

public class Solution {

public List<List<Integer>> generate(int numRows) {

List<List<Integer>> result = new ArrayList<List<Integer>>();

if (numRows <= 0) {

return result;

}

List<Integer> prev = null;

for (int i = 1; i <= numRows; ++i) {

List<Integer> now = new ArrayList<Integer>();

now.add(1);

if (prev == null) {

result.add(now);

prev = now;

continue;

}

for (int j = 0 ; j < prev.size() - 1; ++j) {

now.add(prev.get(j) + prev.get(j + 1));

}

now.add(1);

result.add(now);

prev = now;

}

return result;

}

119 Pascal’s Triangle II

概述

只绘制杨辉三角的某行。

分析

属于118 Pascal’s Triangle的扩展题目，可以考虑直接复用118的代码，生成后返回。

问题在于时间复杂度过高。后续可以优化。

解法

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        return this.generate(rowIndex + 1).get(rowIndex);
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (numRows <= 0) {
            return result;
        }

        List<Integer> prev = null;

        for (int i = 1; i <= numRows; ++i) {
            List<Integer> now = new ArrayList<Integer>();
            now.add(1);

            if (prev == null) {
                result.add(now);
                prev = now;
                continue;
            }

            for (int j = 0 ; j < prev.size() - 1; ++j) {
                now.add(prev.get(j) + prev.get(j + 1));
            }

            now.add(1);
            result.add(now);
            prev = now;
        }

        return result;
    }
}

public class Solution {

public List<Integer> getRow(int rowIndex) {

return this.generate(rowIndex + 1).get(rowIndex);

}

public List<List<Integer>> generate(int numRows) {

List<List<Integer>> result = new ArrayList<List<Integer>>();

if (numRows <= 0) {

return result;

}

List<Integer> prev = null;

for (int i = 1; i <= numRows; ++i) {

List<Integer> now = new ArrayList<Integer>();

now.add(1);

if (prev == null) {

result.add(now);

prev = now;

continue;

}

for (int j = 0 ; j < prev.size() - 1; ++j) {

now.add(prev.get(j) + prev.get(j + 1));

}

now.add(1);

result.add(now);

prev = now;

}

return result;

}

121 Best Time to Buy and Sell Stock

概述

给出股价列表，找出最大的获利。

分析

可以想到，获利最大，即买入价最低，卖出价最高。

每个时间段都会有最高的卖出价，在数组中，一个区间的最大值是一定的。从后向前遍历，如果当前值不大于当前位置之后的最大值，那么当前值开始的最大值，仍然是当前值之后的最大值。反之则是当前值。

只需要针对价格，再次遍历数组，获得每个位置的数字的差值，即可知道在哪一位置时获利最大，即差值最大。

解法

public class Solution {
    public int maxProfit(int[] prices) {
        int[] maxNumbers = new int[prices.length];

        for (int i = prices.length - 1; i >= 0; --i) {
            if (i == prices.length - 1) {
                maxNumbers[i] = prices[i];
                continue;
            }

            if (prices[i] > maxNumbers[i + 1]) {
                maxNumbers[i] = prices[i];
                continue;
            }

            maxNumbers[i] = maxNumbers[i + 1];
        }

        int maxProfit = 0;

        for (int i = prices.length - 1; i >= 0; --i) {
            if (maxProfit < (maxNumbers[i] - prices[i])) {
                maxProfit = maxNumbers[i] - prices[i];
            }
        }

        return maxProfit;
    }
}

public class Solution {

public int maxProfit(int[] prices) {

int[] maxNumbers = new int[prices.length];

for (int i = prices.length - 1; i >= 0; --i) {

if (i == prices.length - 1) {

maxNumbers[i] = prices[i];

continue;

}

if (prices[i] > maxNumbers[i + 1]) {

maxNumbers[i] = prices[i];

continue;

}

maxNumbers[i] = maxNumbers[i + 1];

}

int maxProfit = 0;

for (int i = prices.length - 1; i >= 0; --i) {

if (maxProfit < (maxNumbers[i] - prices[i])) {

maxProfit = maxNumbers[i] - prices[i];

}

return maxProfit;

}

141 Linked List Cycle

概述

判断单向链表中是否存在环。

分析

简单的做法，用hash存储当前的节点指针值，如果再次遇到这一指针，说明有环。

但是目前还没有做出不需要额外空间的做法。

解法

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (null == head) {
            return false;
        }

        HashMap<Object, Integer> m = new HashMap<Object, Integer>();

        ListNode h = head;

        while (h != null) {
            if (m.containsKey(h)) {
                return true;
            }

            m.put(h, 1);
            h = h.next;
        }

        return false;
    }
}

public class Solution {

public boolean hasCycle(ListNode head) {

if (null == head) {

return false;

}

HashMap<Object, Integer> m = new HashMap<Object, Integer>();

ListNode h = head;

while (h != null) {

if (m.containsKey(h)) {

return true;

}

m.put(h, 1);

h = h.next;

}

return false;

}

155 Min Stack

概述

用单向链表实现一个可以直接获得最小值的栈。

分析

栈的特点是先进后出。

push 操作，可以看做是更换首节点的操作。同时，由于要直接获得最小值，可以入栈时判断是否比当前的最小值更小，由此可以完成更新操作。

pop 操作，可以看做是删除首节点的操作。同样的，如果pop的数值比小于等于最小值，需要遍历链表找到最小值。

如是，随时获得栈最小值的时间复杂度是O(1)。

解法

public class MinStack {

    /** initialize your data structure here. */
    public class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }

    private boolean gotMin = false;
    private int minVal = Integer.MAX_VALUE;
    private ListNode stack = null;

    public MinStack() {

    }

    public void push(int x) {
        minVal = getMin();

        if (x <= minVal) {
            minVal = x;
        }

        ListNode n = new ListNode(x);
        n.next = stack;
        stack = n;
    }

    public void pop() {
        if (stack == null) {
            gotMin = false;
            minVal = Integer.MAX_VALUE;
            return;
        }

        if (gotMin && stack.val == minVal) {
            gotMin = false;
            minVal = Integer.MAX_VALUE;
        }

        if (stack.next == null) {
            stack = null;
            gotMin = false;
            minVal = Integer.MAX_VALUE;
            return;
        }

        stack = stack.next;
    }

    public int top() {
        if (stack == null) {
            return 0;
        }

        return stack.val;
    }

    public int getMin() {
        if (gotMin) {
            return minVal;
        }

        ListNode h = stack;

        while (h != null) {
            if (h.val <= minVal) {
                gotMin = true;
                minVal = h.val;
            }

            h = h.next;
        }

        return minVal;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
 ```

public class MinStack {

/** initialize your data structure here. */

public class ListNode {

public int val;

public ListNode next;

public ListNode(int x) { val = x; }

}

private boolean gotMin = false;

private int minVal = Integer.MAX_VALUE;

private ListNode stack = null;

public MinStack() {

}

public void push(int x) {

minVal = getMin();

if (x <= minVal) {

minVal = x;

}

ListNode n = new ListNode(x);

n.next = stack;

stack = n;

}

public void pop() {

if (stack == null) {

gotMin = false;

minVal = Integer.MAX_VALUE;

return;

}

if (gotMin && stack.val == minVal) {

gotMin = false;

minVal = Integer.MAX_VALUE;

}

if (stack.next == null) {

stack = null;

gotMin = false;

minVal = Integer.MAX_VALUE;

return;

}

stack = stack.next;

}

public int top() {

if (stack == null) {

return 0;

}

return stack.val;

}

public int getMin() {

if (gotMin) {

return minVal;

}

ListNode h = stack;

while (h != null) {

if (h.val <= minVal) {

gotMin = true;

minVal = h.val;

}

h = h.next;

}

return minVal;

}

/**

* Your MinStack object will be instantiated and called as such:

* MinStack obj = new MinStack();

* obj.push(x);

* obj.pop();

* int param_3 = obj.top();

* int param_4 = obj.getMin();

```

leetcode-66-67-83-217

发表回复

标题中提到的4道题目都较为简单，合并到一起写解题记录。

66 Plus One

概述

Plus One 即给定以数组形式表示各位的数字，将这一数字加1的结果输出为数组即可。

分析

这一题主要处理的是常规的运算的进位问题，同时，由于数组并没有确定数字为int，那么位数不定，需要按照正常的竖式运算的步骤进行。

当计算发现最高位需要进位时，申请更大的空间，返回结果。

解法

public class Solution {
    public int[] plusOne(int[] digits) {
        int[] r = new int[digits.length];
        int now = 1;

        for (int i = digits.length - 1; i >= 0; --i) {
            r[i] = (now + digits[i]) % 10;
            now = (now + digits[i]) / 10;
        }

        if (now > 0) {
            int[] result = new int[digits.length + 1];

            for (int i = digits.length; i >= 1; --i) {
                result[i] = r[i - 1];
            }

            result[0] = now;

            return result;
        }

        return r;
    }
}

public class Solution {

public int[] plusOne(int[] digits) {

int[] r = new int[digits.length];

int now = 1;

for (int i = digits.length - 1; i >= 0; --i) {

r[i] = (now + digits[i]) % 10;

now = (now + digits[i]) / 10;

}

if (now > 0) {

int[] result = new int[digits.length + 1];

for (int i = digits.length; i >= 1; --i) {

result[i] = r[i - 1];

}

result[0] = now;

return result;

}

return r;

}

67 Add Binary

概述

Add Binary 与 66 Plus One 很相似，只不过由十进制数变为了二进制数的加法。

输入是字符串，输出也是字符串。

分析

二进制加法，仍然按照竖式计算的方式进行即可。无需多说。

解法

public class Solution {
    public String addBinary(String a, String b) {
        int now = 0;
        String result = "";
        int ai = a.length() - 1;
        int bi = b.length() - 1;

        for (; ai >= 0 || bi >= 0; --ai, --bi) {
            int val = 0;

            if (ai >= 0 && bi >= 0) {
                char ac = a.charAt(ai);
                char bc = b.charAt(bi);

                val = now + (ac - '0') + (bc - '0');
            } else if (ai >= 0) {
                char ac = a.charAt(ai);
                val = now + (ac - '0');
            } else {
                char bc = b.charAt(bi);
                val = now + (bc - '0');
            }

            result = val % 2 + result;
            now = val / 2;
        }

        if (now > 0) {
            result = 1 + result;
        }

        return result;
    }
}

public class Solution {

public String addBinary(String a, String b) {

int now = 0;

String result = "";

int ai = a.length() - 1;

int bi = b.length() - 1;

for (; ai >= 0 || bi >= 0; --ai, --bi) {

int val = 0;

if (ai >= 0 && bi >= 0) {

char ac = a.charAt(ai);

char bc = b.charAt(bi);

val = now + (ac - '0') + (bc - '0');

} else if (ai >= 0) {

char ac = a.charAt(ai);

val = now + (ac - '0');

} else {

char bc = b.charAt(bi);

val = now + (bc - '0');

}

result = val % 2 + result;

now = val / 2;

}

if (now > 0) {

result = 1 + result;

}

return result;

}

83 Remove Duplicates from Sorted List

概述

Remove Duplicates from Sorted List 即在已排序的单向链表中完成去重。

分析

链表已排序，去重工作变得相当容易，只需要判断当前节点的值是否等于上一节点的值，如果等于则将链表当前的下一指针指向下下一个节点，周而复始。

解法

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (null == head) {
            return null;
        }

        ListNode r = head;
        int now = 0;

        while (r.next != null) {
            now = r.val;

            if (now == r.next.val) {
                r.next = r.next.next;
            } else {
                r = r.next;
            }
        }

        return head;
    }
}

public class Solution {

public ListNode deleteDuplicates(ListNode head) {

if (null == head) {

return null;

}

ListNode r = head;

int now = 0;

while (r.next != null) {

now = r.val;

if (now == r.next.val) {

r.next = r.next.next;

} else {

r = r.next;

}

return head;

}

217 Contains Duplicate

概述

Contains Duplicate 判断数组中是否有重复的值。

分析

使用Hash完成这一判断最为容易，判断一个值是否在 HashMap 中存在即可。

解法

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

        for (int n : nums) {
            if (m.containsKey(n)) {
                return true;
            }

            m.put(n, 1);
        }

        return false;
    }
}

public class Solution {

public boolean containsDuplicate(int[] nums) {

HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

for (int n : nums) {

if (m.containsKey(n)) {

return true;

}

m.put(n, 1);

}

return false;

}

LeetCode-24-26-27

发表回复

24 Swap Nodes in Pairs

概述

Swap Nodes in Pairs 即是将相邻的两个节点交换形成新的链表，要求在于不能修改值，只能做链表节点操作。

对于空间复杂度上也要要求，只能在 O(1) 这个复杂度上完成。

分析

对于链表操作，无需多说，这里需要注意的地方在于：

第一组元素（前2个）的第二个节点需要变成新链表的首节点
在循环中，前一组的第一个节点要连接的是下一组的第二个节点

明确上述两个关键步骤之后，需要做的就是申请变量暂存目前处理节点的位置以及记录上一组节点的第一个节点。

解法

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode firstOfPair = null;
        ListNode nowNode = head;
        ListNode privNode = null;
        int i = 1;

        while (nowNode != null) {
            if (i % 2 == 1) {
                firstOfPair = nowNode;
                nowNode = nowNode.next;
            } else {
                if (firstOfPair == null) {
                    return head;
                }

                if (privNode != null) {
                    privNode.next = nowNode;
                }

                privNode = firstOfPair;
                firstOfPair.next = nowNode.next;
                nowNode.next = firstOfPair;

                if (i == 2) {
                    head = nowNode;
                }

                nowNode = firstOfPair.next;
            }

            ++i;
        }

        return head;
    }
}

public class Solution {

public ListNode swapPairs(ListNode head) {

ListNode firstOfPair = null;

ListNode nowNode = head;

ListNode privNode = null;

int i = 1;

while (nowNode != null) {

if (i % 2 == 1) {

firstOfPair = nowNode;

nowNode = nowNode.next;

} else {

if (firstOfPair == null) {

return head;

}

if (privNode != null) {

privNode.next = nowNode;

}

privNode = firstOfPair;

firstOfPair.next = nowNode.next;

nowNode.next = firstOfPair;

if (i == 2) {

head = nowNode;

}

nowNode = firstOfPair.next;

}

++i;

}

return head;

}

26 Remove Duplicates from Sorted Array

概述

Remove Duplicates from Sorted Array 即通过数组元素移动操作，去除数组中重复的数字，并且返回不重复数字的个数。

分析

本题的需要注意，单纯返回非重复数字的长度是不够的，由于空间复杂度也有要求，需要在原数组中通过移位等操作将重复元素删除。

在是已经排序了的数组的情况下，相同数字必然是连续的，只需要遍历一遍数字，遇到相同的数字，将下一数字之后的数组元素前移即可。

下一次循环开始的

解法

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }

        int nowIdx = 1;

        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] != nums[i - 1]) {
                nums[nowIdx] = nums[i];
                ++nowIdx;
            }
        }

        return nowIdx;
    }
}

public class Solution {

public int removeDuplicates(int[] nums) {

if (nums.length <= 1) {

return nums.length;

}

int nowIdx = 1;

for (int i = 1; i < nums.length; ++i) {

if (nums[i] != nums[i - 1]) {

nums[nowIdx] = nums[i];

++nowIdx;

}

return nowIdx;

}

27 Remove Element

概述

Remove Element 同样是remove，和26的区别是给定的数字进行去除。

分析

与 Remove Duplicates from Sorted Array 的解法类似，不同的是考虑终止条件的时候需要注意删除了元素之后相当于产生了一个数组，长度是发生了变化，循环时需要考虑这一因素。

解法

public class Solution {
    public int removeElement(int[] nums, int val) {
        int removed = 0;

        for (int i = 0; i < nums.length - removed; ++i) {
            if (nums[i] == val) {
                for (int j = i; j + 1 < nums.length; ++j) {
                    nums[j] = nums[j + 1];
                }

                ++removed;
                --i;
            }
        }

        return nums.length - removed;
    }
}

public class Solution {

public int removeElement(int[] nums, int val) {

int removed = 0;

for (int i = 0; i < nums.length - removed; ++i) {

if (nums[i] == val) {

for (int j = i; j + 1 < nums.length; ++j) {

nums[j] = nums[j + 1];

}

++removed;

--i;

}

return nums.length - removed;

}

其他

26 与 27 逐个搬迁并不是最佳解法，还有优化的空间。

LeetCode-19-20-21

发表回复

19 Remove Nth Node From End of List

概述

Remove Nth Node From End of List 即删除单向链表中从链表尾部开始的第N个节点。

分析

单向链表只能通过逐步前进才能到达指定节点，是无法在 O(1) 的时间复杂度下拿到链表的长度的，可以考虑通过一次遍历将链表明确节点节点位置与值的对应关系，之后通过链表的节点操作完成删除节点的效果。

节点位置与值的关系可以通过Hash进行存储，由于链表长度不定，预先留出数组空间的方式个人认为并不是好的选择。

解法

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        HashMap<Integer, ListNode> idxListMap = new HashMap<Integer, ListNode>();

        ListNode it = head;
        int i = 1;

        for(; it != null; it = it.next, ++i) {
            idxListMap.put(i, it);
        }

        if (idxListMap.size() == 1) {
            return null;
        }

        if (n == 1) {
            idxListMap.get(idxListMap.size() - 1).next = null;
            return head;
        }

        if (n == idxListMap.size()) {
            head = head.next;
            return head;
        }

        if (idxListMap.containsKey(idxListMap.size() - n) && idxListMap.containsKey(idxListMap.size() - n + 2)) {
            idxListMap.get(idxListMap.size() - n).next = idxListMap.get(idxListMap.size() - n + 2);
        }

        return head;
    }
}

public class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {

HashMap<Integer, ListNode> idxListMap = new HashMap<Integer, ListNode>();

ListNode it = head;

int i = 1;

for(; it != null; it = it.next, ++i) {

idxListMap.put(i, it);

}

if (idxListMap.size() == 1) {

return null;

}

if (n == 1) {

idxListMap.get(idxListMap.size() - 1).next = null;

return head;

}

if (n == idxListMap.size()) {

head = head.next;

return head;

}

if (idxListMap.containsKey(idxListMap.size() - n) && idxListMap.containsKey(idxListMap.size() - n + 2)) {

idxListMap.get(idxListMap.size() - n).next = idxListMap.get(idxListMap.size() - n + 2);

}

return head;

}

20 Valid Parentheses

概述

Valid Parentheses 即判断括号是否匹配。

分析

括号需要一一对应，即一个左括号，需要对应一个右括号，简单来说，在字符串遍历过程中，右括号出现之后，需要判断上一个括号是不是一个左括号，如果是一个左括号，那么说明这个括号完成了匹配。否则，说明没有完成匹配。

从数据结构上来说，栈是一个非常适合的数据结构，左括号直接入栈，出现右括号则比较栈顶元素，如果相同，则出栈，继续比较，否则则说明不匹配。完成比较之后，如果栈已空，则说明括号完成了完全的匹配。

但是，使用字符串操作其实也能做到这一效果，完全不需要使用 Java 内置的栈。即栈顶元素可以看成是字符串的最后一个元素，出栈则是删除最后一个字符串。

解法

public class Solution {
    public boolean isValid(String s) {
        String p = "";

        for (int i = 0; i < s.length(); ++i) {
            String c = s.substring(i, i + 1);

            if ("([{".contains(c)) {
                p = p + c;
                continue;
            }

            if (")]}".contains(c)) {
                if (p.length() == 0) {
                    return false;
                }

                String topOfStack = p.substring(p.length() - 1, p.length());

                if (c.equals(")") && !topOfStack.equals("(")) {
                    return false;
                }

                if (c.equals("]") && !topOfStack.equals("[")) {
                    return false;
                }

                if (c.equals("}") && !topOfStack.equals("{")) {
                    return false;
                }

                p = p.substring(0, p.length() - 1);
            }
        }

        return p.length() == 0;
    }
}

public class Solution {

public boolean isValid(String s) {

String p = "";

for (int i = 0; i < s.length(); ++i) {

String c = s.substring(i, i + 1);

if ("([{".contains(c)) {

p = p + c;

continue;

}

if (")]}".contains(c)) {

if (p.length() == 0) {

return false;

}

String topOfStack = p.substring(p.length() - 1, p.length());

if (c.equals(")") && !topOfStack.equals("(")) {

return false;

}

if (c.equals("]") && !topOfStack.equals("[")) {

return false;

}

if (c.equals("}") && !topOfStack.equals("{")) {

return false;

}

p = p.substring(0, p.length() - 1);

}

return p.length() == 0;

}

21 Merge Two Sorted Lists

概述

Merge Two Sorted Lists 即单向链表归并。

分析

归并已排序链表，首先需要判断两个链表是否已经到达链表终点，达到链表终点之后只需要处理另一个没有到达终点的链表。

在两个链表没有到达终点时，比较二者的首节点的值，在升序的情况下，较小的值添加到结果链表中，较小值所在的链表向前前进一个节点，之后周而复始的比较。

解法

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }

        ListNode head = new ListNode(Integer.MIN_VALUE);
        ListNode it = head;

        while (l1 != null || l2 != null) {
            int val = 0;

            if (l1 == null) {
                val = l2.val;
                l2 = l2.next;
            } else if (l2 == null) {
                val = l1.val;
                l1 = l1.next;
            } else if (l1.val < l2.val) {
                val = l1.val;
                l1 = l1.next;
            } else {
                val = l2.val;
                l2 = l2.next;
            }

            if (it.val == Integer.MIN_VALUE) {
                it.val = val;
                continue;
            }

            it.next = new ListNode(val);
            it = it.next;
        }

        return head;
    }
}

public class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

if (l1 == null && l2 == null) {

return null;

}

ListNode head = new ListNode(Integer.MIN_VALUE);

ListNode it = head;

while (l1 != null || l2 != null) {

int val = 0;

if (l1 == null) {

val = l2.val;

l2 = l2.next;

} else if (l2 == null) {

val = l1.val;

l1 = l1.next;

} else if (l1.val < l2.val) {

val = l1.val;

l1 = l1.next;

} else {

val = l2.val;

l2 = l2.next;

}

if (it.val == Integer.MIN_VALUE) {

it.val = val;

continue;

}

it.next = new ListNode(val);

it = it.next;

}

return head;

}