月度归档：2016年06月

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;

}

LeetCode-9

发表回复

概述

Palindrome Number 判断文字是否是回文，输出布尔值。

分析

作为一道 Easy 的题目，看起来并不是特别麻烦，不过这题要求无需增加附加的空间复杂度。

题目要求判断是否为回文数，那么负数肯定不是回文数，因为负数带有符号位。

从字符串的角度来看，回文只需判断反转之后是否相同即可，那么针对数字亦可以使用这一方法。

考虑到数字反转之后会出现溢出的情况，而正数溢出之后在 Java 中的处理方式则是变为一个负数（参见 SO 上的问题 How does Java handle integer underflows and overflows and how would you check for it?），那么反转后变为负数的数字自然不是一个回文数了，因为反转之后在非负整数的范围内显然这个数字不存在。

不新增变量的情况下，只能通过递归来解决问题了。

解法

public class Solution {
    public static int len(int v) {
        return (v == 0 ? 0 : 1 + len(v / 10));
    }

    public static int reverse(int x) {
        if (x < 10) {
            return x;
        }

        return reverse(x / 10) + (x % 10) * (int)Math.pow(10, len(x) - 1);
    }

    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        if (x == 0) {
            return true;
        }

        return x == reverse(x);
    }
}

public class Solution {

public static int len(int v) {

return (v == 0 ? 0 : 1 + len(v / 10));

}

public static int reverse(int x) {

if (x < 10) {

return x;

}

return reverse(x / 10) + (x % 10) * (int)Math.pow(10, len(x) - 1);

}

public boolean isPalindrome(int x) {

if (x < 0) {

return false;

}

if (x == 0) {

return true;

}

return x == reverse(x);

}

LeetCode-6

发表回复

概述

作为一道简单题，ZigZag Conversion 即将字符串按照之字形显示后，再逐行打印字符串。

分析

这一题题意自然是很明显的，但是，这个之字形的形状需要注意，这一个之字形的形状应该是：

A     G     M     S     Y
B   F H   L N   R T   X Z
C E   I K   O Q   U W
D     J     P     V

A G M S Y

B F H L N R T X Z

C E I K O Q U W

D J P V

而不是类似字母 N 的模样。这里是需要注意的一点，题目中的示例为三行，并不是很明显。

简单来说，可以直接模拟重新排布字字母的过程，字母可以看做填写在一个 m * n 的矩阵中（m * n >= s.length()）。

如果想要在 O(n) 的时间复杂度内解决问题，那么最理想的方法应该是根据行列的位置，确定当前是填充字母还是留空。

观察这一个矩阵，若行数为 n，那么可以看做有多个 n * (n - 1) 的子矩阵，形状都是重复的，只需要得到各个位置上的字符与源字符串中的下标的对应关系即可得知当前应该出现的字母。

对于一个行数为 n 的子矩阵，包含的字符个数应为 <= 2n – 2。从左往右，第 i 个（i >= 1）子矩阵的字符串包含的字母下标范围为 [(i - 1) * (2n - 2), i * (2n - 2))

从行的角度来看，每行在每个子矩阵中，子矩阵的第一列一定是有字母的，而这个字母在源字符串中正是连续的，所以，每行直接输出子矩阵对应的字母的前 n 个字符即可。

而剩下的 n – 2 个字符，则是类似斜率为1的一条直线的排布，我们要做的，即当运行到对应点时，结合横纵位置，判断当前是否有字符，如果没出现下标越界，说明此处应显示对应的字母。

解法

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }

        int sLen = s.length();
        int colNum = (int) Math.ceil(1.0 * sLen / numRows);
        int sectionNum = 2 * numRows - 2;

        String result = "";

        for (int r = 0; r < numRows; ++r) {
            for (int c = 0; c < colNum; ++c) {
                int idx = c * sectionNum + r;

                if (idx < sLen) {
                    result += s.substring(idx, idx + 1);

                    if (r >= 1 && r <= numRows - 2) {
                        int idxAppend = (c + 1) * sectionNum - r;

                        if (idxAppend >= 0 && idxAppend < sLen) {
                            result += s.substring(idxAppend, idxAppend + 1);
                        }
                    }
                }
            }
        }

        return result;
    }
}

public class Solution {

public String convert(String s, int numRows) {

if (numRows == 1) {

return s;

}

int sLen = s.length();

int colNum = (int) Math.ceil(1.0 * sLen / numRows);

int sectionNum = 2 * numRows - 2;

String result = "";

for (int r = 0; r < numRows; ++r) {

for (int c = 0; c < colNum; ++c) {

int idx = c * sectionNum + r;

if (idx < sLen) {

result += s.substring(idx, idx + 1);

if (r >= 1 && r <= numRows - 2) {

int idxAppend = (c + 1) * sectionNum - r;

if (idxAppend >= 0 && idxAppend < sLen) {

result += s.substring(idxAppend, idxAppend + 1);

}

return result;

}