标签归档：LeetCode

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;

}

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);

}