zeqing-guo / algorithms-study Goto Github PK

View Code? Open in Web Editor NEW

0.0 0.0 1.0 120 KB

License: MIT License

algorithms-study's People

Watchers

Forkers

chanelle7

algorithms-study's Issues

Leetcode-226: Invert Binary Tree

Description

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to
4
/
7 2
/ \ /
9 6 3 1

Note:

You may assume that the array does not change.
There are many calls to sumRange function.

My Solution

代码的 run time 是0 ms (21.92%)。时间复杂度是，空间复杂度是。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root != null) {
            TreeNode left = root.left;
            root.left = invertTree(root.right);
            root.right = invertTree(left);
        }
        return root;
    }
}

Analysis

递归比迭代快==

1 ms 的迭代版本：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode element; 
        TreeNode left;
        TreeNode right;
        LinkedList<TreeNode> ll = new LinkedList<>();
        ll.add(root);

        while (!ll.isEmpty()) {
            element = ll.pop();
            left = element.left;
            right = element.right;

            element.left = right;
            element.right = left;

            if (left != null) {
                ll.push(left);
            }
            if (right != null) {
                ll.push(right);
            }
        }

        return root;
    }
}

Leetcode-172: Factorial Trailing Zeroes

Description

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

My Solution

代码的 run time 是20 ms (20.47%)。时间复杂度是，空间复杂度是。

public class Solution {
    public boolean isPowerOfThree(int n) {
        return (n > 0 && 1162261467 % n == 0);
    }
}

Analysis

这个没啥好说的。。

Leetcode-154: Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

Description

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

My Solution

1 ms, 时间复杂度是O(n)，空间复杂度是O(1)。

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null) {
            return 0;
        }

        int len = nums.length;

        if (len == 1) {
            return nums[0];
        }

        int i;
        for (i = 0; i < len - 1 && nums[i] <= nums[i + 1]; ++i) ;

        if (i + 1 == len) {
            return nums[0];
        } else {
            return nums[i + 1];
        }
    }
}

Analysis

用了个笨方法，最优解应该是二分查找。

Leetcode-36: Valid Sudoku

Description

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

My Solution

代码的run time是3 ms (92.28%)，时间复杂度是，空间复杂度是

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null) {
            return false;
        }

        int[] row = new int[9];
        int[] column = new int[9];
        int[] sub = new int[9];

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                int value = board[i][j] - '1';
                if (value != -3) { // -3 = '.' - '1'
                    int subIndex = i / 3 * 3 + j / 3;
                    int mask = 0x1 << value;
                    if (((row[i] | column[j] | sub[subIndex]) & mask) != 0) {
                        return false;
                    } else {
                        row[i] |= mask;
                        column[j] |= mask;
                        sub[subIndex] |= mask;
                    }
                }
            }
        }
        return true;
    }
}

Analysis

这道题看到leetcode的tag后先入为主选择了HashSet，代码的run time是8 ms，事实上这里使用bit map已经足够。在使用bit map后run time降到3 ms。（不过在第二个版本中我使用了二维数组去记录元素之前有没有出现，这样的空间开销要更大，而且run time 也要更长，为4 ms）

还有一个要注意的地方是&的优先级比|和!=大，所以number & mask != 0会报错。

Leetcode-328: Odd Even Linked List

Description

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in space complexity and time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...

My Solution

代码的 run time 是1 ms (5.79%)。时间复杂度是，空间复杂度是。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode headOdd = head;
        ListNode headEven = head.next;
        ListNode curOdd = headOdd;
        ListNode curEven = headEven;
        head = head.next.next;

        int oddEven = 1;

        while (head != null) {
            if (oddEven == 1) {
                oddEven = 0;
                curOdd.next = head;
                curOdd = curOdd.next;
            } else {
                oddEven = 1;
                curEven.next = head;
                curEven = curEven.next;
            }
            head = head.next;
        }
        curEven.next = null;
        curOdd.next = headEven;

        return headOdd;
    }
}

Analysis

水题，我想知道0 ms的那群人是怎么写的。

Leetcode-168: Excel Sheet Column Title

Description

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB

My Solution

代码的 run time 是0 ms (6.39%)。时间复杂度是，空间复杂度是 $O(\log n)$ 。

public class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) {
            return null;
        }
        StringBuilder sb = new StringBuilder((int) Math.log(n));

        while(n > 0) {
            --n; // make 0 -> A, 1 -> B, ..., 25 -> Z, 26 -> AA
            sb.insert(0, (char) ('A' + n % 26));
            n /= 26;
        }

        return sb.toString();
    }
}

Analysis

进制的题目，如果给出的排列不是从0开始可以调整其至零开始。（例子见上面代码中的注释）

Leetcode-219: Contains Duplicate II

Contains Duplicate II

Description

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

My Solution

代码的run time是 8 ms。代码的时间复杂度是O(n)，空间复杂度也是O(n)。

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null) {
            return false;
        }

        int len = nums.length;
        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < len; ++i) {
            if (i > k) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {
                return true;
            }
        }

        return false;
    }
}

Analysis

超时的方法：

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null) {
            return false;
        }

        int len = nums.length;

        for (int i = 0; i < len - 1; ++i) {
            int bound = i + k;
            for (int j = i + 1; j < len && j <= bound; ++j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

弄了个O(n^2)出来==

慢的方法（14 ms）：

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null) {
            return false;
        }

        int len = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; ++i) {
            Integer val = map.get(nums[i]);
            if (val != null && i - val <= k) {
                return true;
            } else {
                map.put(nums[i], i);
            }
        }

        return false;
    }
}

Java（JDK 6）里HashSet由HashMap实现，所以说数据结构不是慢的原因。
我认为原因是慢的方法维护了一张很大的Hash，而快的方法每次会删掉nums[i - k - 1]。
（我在慢的方法中也加入了remove方法，但是还是会慢一些，我觉得时间差异在于HashSet的add方法和HashMap的get和put的区别）

Leetcode-278: First Bad Version

First Bad Version

Description

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

My Solution

代码的run time是24ms，完整代码如下：

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (isBadVersion(1)) {
            return 1;
        } else if (isBadVersion(2)) {
            return 2;
        } else if (isBadVersion(3)) {
            return 3;
        }

        int start = 1;
        int end = n;

        do {
            int i = start + ((end - start) >> 1); // overflow is use start + end!!!
            if (!isBadVersion(i)) {
                start = i + 1;
                //end = end;
            } else if (isBadVersion(i - 1)) {
                // start = start;
                end = i - 1;
            } else {
                return i;
            }
        } while (start < end);

        return start;
    }
}

Analysis

这道题是一个二分查找的题目。由于只要出现了一个bad version后面所有的version都会变成bad version。因此我们只需要用二分法找到一个节点，这个节点是bad version而它前一个节点不是bad version就好了。由于使用了二分法，因此算法的时间复杂度是$O(lgN)$。

这里要注意一点，当数组很大的时候(start + end) >> 1会溢出。以后在对两数做加法的时候需要注意这个问题。将(start + end) >> 1改写成start + ((end - start) >> 1)是一个很好的pattern，要记住。

Reasons For Not Being Accepted

(start + end) >> 1溢出。

Leetcode-162: Find Peak Element

Description

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

My Solution

代码的run time是0ms (27.16%)，时间复杂度是，空间复杂度是。

public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null) {
            return -1;
        }

        int len = nums.length;

        if (len == 1) {
            return 0;
        } 

        if (nums[len - 1] > nums[len - 2]) {
            return len - 1;
        }

        for (int i = 1; i < len; ++i) {
            if (nums[i] < nums[i - 1]) {
                return i - 1;
            }
        }
        return -1;
    }
}

Analysis

水题，不懂难度为什么是medium。

Leetcode-74: Search a 2D Matrix

Description

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

My Solution

代码的run time是1ms，时间复杂度是，其中n和m分别为matrix的长和宽。
空间复杂度是。

public class Solution {
    int xLen = 0;
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null) {
            return false;
        }
        xLen = matrix[0].length;

        int l = 0;
        int r = xLen * matrix.length - 1;

        while (l < r - 1) {
            int m = (l + r) >> 1;
            int x = fx(m);
            int y = fy(m);

            int mVal = matrix[x][y];
            if (target > mVal) {
                l = m;
            } else if (target < mVal) {
                r = m;
            } else {
                return true;
            }
        }

        if (target == matrix[fx(l)][fy(l)]) {
            return true;
        }

        if (target == matrix[fx(r)][fy(r)]) {
            return true;
        }

        return false;
    }

    int fx(int n) {
        return n / xLen;
    }

    int fy(int n) {
        return n % xLen;
    }
}

Analysis

和昨天写的题目的解法一样（其实我就是挑了一道一样的题写

没什么好说的，直接参照昨天的Leetcode-33: Search in Rotated Sorted Array的做法就好了。

如果有谁优化到0ms求指导。

Leetcode-67: Add Binary

Add Binary

Description

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

My Solution

代码的run time是4 ms，时间复杂度是O(n)，空间复杂度是O(n)。

代码如下所示：

public class Solution {
    public String addBinary(String a, String b) {
        int lenA = a.length();
        int lenB = b.length();
        int minLen;
        int maxLen;
        String maxStr;
        String minStr;

        if (lenA > lenB) {
            maxLen = lenA;
            minLen = lenB;
            maxStr = a;
            minStr = b;
        } else {
            maxLen = lenB;
            minLen = lenA;
            maxStr = b;
            minStr = a;
        }

        StringBuilder sb = new StringBuilder(maxLen + 1);
        int digit = 0;

        int i = maxLen - 1;
        int j = minLen - 1;
        for (; j >= 0; --i, --j) {
            int sum = maxStr.charAt(i) + minStr.charAt(j) + digit - 96; // 2 * '0' = 96
            sb.append(sum & 0x1);
            digit = sum >> 1;
        }
        for (; i >= 0; --i) {
            int sum = maxStr.charAt(i) + digit - 48; // '0' = 48
            sb.append(sum & 0x1);
            digit = sum >> 1;
        }
        if (digit == 1) {
            sb.append('1');
        }

        return sb.reverse().toString();
    }
}

Analysis

这道题很简单，没什么好讲的。不过要注意，字符串动态增减时最好用StringBuilder。可以参考stackoverflow上的回答：

If you use String concatenation in a loop (something like:

String s = "";
for(int i = 0; i < 100; i++) {
  s += ", " + i;
}

then you should use a StringBuilder (not StringBuffer) instead of a String, because it is much faster and consumes less memory.

If you have a single statement:

String s = "1, " + "2, " + "3, " + "4, " ....;

then you can use Strings, because the compiler will use StringBuilder automatically.

Leetcode-71: Simplify Path

Description

Given an absolute path for a file (Unix-style), simplify it.

For example,

path = "/home/", => "/home"

path = "/a/./b/../../c/", => "/c"

My Solution

代码的run time是8ms，时间复杂度是，空间复杂度是。

public class Solution {
    public String simplifyPath(String path) {
        String[] arr = path.split("/");
        int len = arr.length;
        String[] nameArr = new String[len];
        StringBuilder ans = new StringBuilder(len);
        int index = 0;

        for (int i = 0; i < len; ++i) {
            if (arr[i].equals(".") 
                || arr[i].equals("")) {
            } else if (arr[i].equals("..")) {
                if (index > 0) {
                    --index;
                } else {
                    // do nothing
                }
            } else {
                nameArr[index] = arr[i];
                ++index;
            }
        }

        if (index == 0) {
            return "/";
        } else {
            for (int i = 0; i < index; ++i) {
                ans.append('/');
                ans.append(nameArr[i]);
            }
        }

        return ans.toString();
    }
}

Analysis

为了更方便地操作下标，这里用Array替代了Stack。实际上我觉得Stack是ArrayList和LinkedList的子集，在实际中很少真的用到Stack这个class。毕竟Stack有的功能ArrayList和LinkedList都有。

因为代码中存在频繁的字符串拼接操作，所以我用StringBuilder替代了String，防止频繁生成String instance的开销。

这份代码三次运行的时间分别是13ms (33.16%)，_Time Limit Exceeded_和8ms (92.94%)。（大雾

所以我也不知道上面的优化效果怎么样。

Leetcode-209: Minimum Size Subarray Sum

Description

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

My Solution

代码的run time是1ms，时间复杂度是，空间复杂度是。

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null) {
            return 0;
        }

        int len = nums.length;
        int minimalLength = len + 1;
        int l = 0;
        int r = 0;
        if (len == 0) {
            return 0;
        } else if (len == 1) {
            if (nums[0] >= s) {
                return 1;
            } else {
                return 0;
            }
        } else {
            int sum = nums[l];
            while (l <= r && r < len) {
                if (sum >= s) {
                    int currentLength = r - l + 1;
                    minimalLength = (currentLength > minimalLength) ? minimalLength : currentLength;
                    sum -= nums[l];
                    ++l;
                } else {
                    ++r;
                    if (r < len) {
                        sum += nums[r];
                    } else {
                        break;
                    }
                }
            }
        }

        if (minimalLength != len + 1) {
            return minimalLength;
        } else {
            return 0;
        }
    }
}

Analysis

写代码用时23min，因为考虑不全面出现两次WA和一次RE。

代码思路比较简单，就是两点法。

本题还有一种 $n\log n$ 的解法，思路如下：

As to $n\log n$ solution, $\log n$ immediately reminds you of binary search. In this case, you cannot sort as the current order actually matters. How does one get an ordered array then? Since all elements are positive, the cumulative sum must be strictly increasing. Then, a subarray sum can expressed as the difference between two cumulative sum. Hence, given a start index for the cumulative sum array, the other end index can be searched using binary search.

简单说来就是考虑二分法，考虑到数组是乱序但是元素是正数，因此其累加的和是递增的，对递增的和可以使用二分法。引用的原文和代码见此讨论。

这个思路有两个值得注意的地方：

乱序非负数数组的和可以用二分法。
处理subarray时可以把subarray（比如a(i,j)）视为两个从首个元素开始的subarray的差集（比如a(0,i) - a(0,j)）。

Leetcode-35: Search Insert Position

Search Insert Position

Description

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

My Solution

0 ms.

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null) {
            return 0;
        }

        int position = 0;
        int len = nums.length;

        while (position < len && nums[position] < target) ++position;

        return position;
    }
}

Analysis

太简单，没什么好说的。

Leetcode-221: Maximal Square

Maximal Square

Description

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

Return 4.

My Solution

代码的run time为13 ms，代码如下：

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null) {
            return 0;
        } else if (matrix.length == 0) {
            return 0;
        }

        int maxS = Integer.MIN_VALUE;
        int lenX = matrix[0].length;
        int lenY = matrix.length;
        int d[][] = new int[lenY][lenX];

        for (int i = 0; i < lenY; ++i) {
            d[i][0] = matrix[i][0] - '0';
            maxS = maxS > d[i][0] ? maxS : d[i][0];
        }

        for (int i = 0; i < lenX; ++i) {
            d[0][i] = matrix[0][i] - '0';
            maxS = maxS > d[0][i] ? maxS : d[0][i];
        }

        for (int i = 1; i < lenY; ++i) {
            for (int j = 1; j < lenX; ++j) {
                if (matrix[i][j] == '1') {
                    int min = 0;
                    min = Math.min(d[i - 1][j], d[i][j - 1]);
                    min = Math.min(min, d[i - 1][j - 1]);
                    d[i][j] = min + 1;
                    maxS = maxS > d[i][j] ? maxS : d[i][j];
                } else {
                    d[i][j] = 0;
                    maxS = maxS > d[i][j] ? maxS : d[i][j];
                }
            }
        }
        return maxS * maxS;
    }
}

Analysis

这道题是一个DP问题。

设d[x][y]是以(y, x)座标为矩形右下角点的矩形的边长。
递推关系如下：
1. d[x][y] = min (d[x - 1][y],d[x][y - 1], d[x - 1][y - 1]) (x > 0 && y > 0)
2. d[0][y] = matrix[0][y] (x == 0)
3. d[x][0] = matrix[x][0] (y == 0)
Base case为d[x][y](x == 0 || y == 0)。

Leetcode-231: Power of Two

Power of Two

Description

Given an integer, write a function to determine if it is a power of two.

My Solution

代码的run time是2 ms，时间复杂度是O(n)，空间复杂度是O(1)。

代码如下所示：

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }

        while ((n & 0x1) == 0) {
            n = n >> 1;
        }
        return n == 1;
    }
}

Analysis

没什么好说的。

Leetcode-171: Excel Sheet Column Number

Excel Sheet Column Number

Description

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28

My Solution

代码的run time是2 ms，时间复杂度是O(n)，空间复杂度是O(1)。

public class Solution {
    public int titleToNumber(String s) {
        if (s == null) {
            return 0;
        }
        int sum = 0;
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            sum = (s.charAt(i) - 'A' + 1) + sum * 26;
        }
        return sum;
    }
}

Analysis

太简单，没什么好说的。

Leetcode-33: Search in Rotated Sorted Array

Description

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

My Solution

代码的run time是1ms，时间复杂度是 $O(\log n)$ ，空间复杂度是。

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null) {
            return 0;
        }
        int len = nums.length;
        int l = 0;
        int r = len - 1;
        int shift = 0;

        if (nums[l] < nums[r]) {
            shift = 0;
        } else if (nums[l] > nums[r]) {
            while (l < r) {
                int m = (l + r) >> 1;
                if (nums[l] < nums[m]) {
                    l = m;
                } else {
                    r = m;
                }
            }
            shift = l + 1;
        } else {
            if (nums[l] == target) {
                return l;
            } else {
                return -1;
            }
        }

        l = 0;
        r = len - 1;

        while (l < r - 1) {
            int m = (l + r) >> 1;
            if (target > nums[f(m, shift, len)]) {
                l = m;
            } else {
                r = m;
            }
        }
        if (nums[f(r, shift, len)] == target) {
            return f(r, shift, len);
        }
        if (nums[f(l, shift, len)] == target) {
            return f(l, shift, len);
        }
        return -1;
    }

    int f(int n, int shift, int len) {
        return (n + shift) % len;
    }
}

Analysis

变形后的二分查找。

首先需要找到rotated之前的数组的最大值和最小值的下标，设最大值下标为n，那么最小值下标则为n + 1。所以数组每个元素向右移动了n + 1个位置。

接着只需要找到原坐标与rotated之后坐标的对应关系后就可以按照普通的二分查找解题。

对应关系如下：

其中before是rotated前的坐标，shift是数组整体向右移的长度，length是数组的长度。

Leetcode-326: Power of Three

Description

Given an integer n, return the number of trailing zeroes in .

Note: Your solution should be in logarithmic time complexity.

My Solution

代码的 run time 是1 ms (70.84%)。时间复杂度是 $O(\log n)$ ，空间复杂度是。

public class Solution {
    public int trailingZeroes(int n) {
        if (n >= 5) {
            return trailingZeroes(n / 5) + n / 5;
        } else {
            return 0;            
        }
    }
}

Analysis

下面两种写法的 run time 都是2 ms:

public class Solution {
    public int trailingZeroes(int n) {
        if (n < 5) {
            return 0;
        }
        int p = (int) (Math.log(n) / Math.log(5));
        int number = 0;
        for (int i = 1; i <= p; ++i) {
            number += n / Math.pow(5, i);
        }

        return number;
    }
}

public class Solution {
    public int trailingZeroes(int n) {
        if (n >= 5) {
            int divFive = n / 5;
            return trailingZeroes(divFive) + divFive;
        } else {
            return 0;            
        }
    }
}

第一种方法是迭代，第二种方法是递归。开销似乎在变量申明上，1 ms这个 run time 应该是编译器优化的结果。

Leetcoe-115: Distinct Subsequences

Distinct Subsequences

Description

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

My Solution

代碼的run time是16 ms。時間複雜度是O(m * n)，空間複雜度是O(m * n)。
代碼如下所示：

public class Solution {
    public int numDistinct(String s, String t) {
        int lenS = s.length();
        int lenT = t.length();

        if (lenT > lenS) return 0;

        int path[][] = new int[lenS + 1][lenT + 1];

        for (int i = 0; i <= lenS; ++i) {
            path[i][0] = 1;
        }

        // A default value of 0 for arrays of integral types is guaranteed by the language spec

        for (int i = 1; i <= lenS; ++i) {
            for (int j = 1; j <= lenT; ++j) {
                path[i][j] = path[i - 1][j] + (s.charAt(i - 1) == t.charAt(j - 1) ? path[i - 1][j - 1] : 0);
            }
        }

        return path[lenS][lenT];
    }
}

Analysis

算法來自這個鏈接。
這是一個二維的DP問題。

設Ti爲T.substring(0, i)，Sj爲S.substring(0, j)，path[i][j]爲Ti在Sj中的distinct subsequences的數目。
考慮S.charAt(j)。不將它放入subsequences中，那麼distinct subsequences的數目爲path[i][j - 1]。將它放入subsequences中，如果S.charAt == T.chatAt那麼distinct subsequences的數目爲path[i - 1][j - 1]，否則數目爲0。
Base case: path[i][0] = 0，path[0][i] = 1。

Leetcode-228: Summary Ranges

Summary Ranges

Description

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

My Solution

代码的run time是1 ms，代码的时间复杂度是O(n)，空间复杂度也是O(n)。

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        if (nums == null) {
            return null;
        }

        int len = nums.length;
        LinkedList<String> list = new LinkedList<>();
        if (len <= 0) {
            return list;
        }

        int start = nums[0];
        int end = 0;
        for (int i = 1; i < len; ++i) {
            int numsi = nums[i];
            int numsiOne = nums[i - 1];
            if (numsi - 1 != numsiOne) {
                end = numsiOne;
                if (end != start) {
                    list.add(start + "->" + end);
                } else {
                    list.add("" + start);
                }
                start = numsi;
            }
        }
        end = nums[len - 1];
        if (start != end) {
            list.add(start + "->" + end);
        } else {
            list.add("" + start);
        }
        return list;
    }
}

Analysis

不知道应该怎么优化到0 ms。

Leetcode-237: Delete Node in a Linked List

Delete Node in a Linked List

Description

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

My Solution

代码的run time是1 ms，代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        if (node == null) {
            return;
        }

        while (node.next.next != null) {
            node.val = node.next.val;
            node = node.next;
        }

        node.val = node.next.val;
        node.next = null;
    }
}

Analysis

其实就是一个有点脑筋急转弯的处理技巧：把next node的val赋给current node，一直迭代下去直到倒数第二个node，然后把这个node的next赋值为null。

Leetcode-169: Majority Element

Majority Element

Description

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

My Solution

代码的run time是3 ms，时间复杂度是O(n)，空间复杂度是O(1).
代码如下所示：

public class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        int size = len;
        int tmpSize = len;

        while (tmpSize > 1) {
            tmpSize = 0;
            for (int i = 1; i < size; i += 2) {
                if (nums[i] == nums[i - 1]) {
                    nums[tmpSize++] = nums[i];
                }
            }
            if ((size & 0x1) == 0) {
                size = tmpSize;
            } else {
                nums[tmpSize++] = nums[size - 1];
                size = tmpSize;
            }
        }

        return nums[0];
    }
}

Analysis

这道题还有其他时间复杂度为O(n)的解法：

Hash map：这种解法的空间复杂度是O(n)。
第二种方法和我的方法都是采用鸽笼原理，不过表述方法不同：

int solution3(vector<int> &nums){
    int cur = nums[0];
    for(int i = 1, count = 1; i < nums.size(); i++){
        if(nums[i] == cur) count++;
        else count--;
        if(count == -1){
            cur = nums[i];
            count = 1;
        }
    }
    return cur;
}

Leetcode-205: Isomorphic Strings

Description

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

My Solution

代码的run time是10ms (94.14%)，时间复杂度是，空间复杂度是。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        for (int i = 0; i < len; ++i) {
            char sc = ss[i];
            char tc = ts[i];
            Character c = map.get(sc);
            if (c != null) {
                if (c != tc) {
                    return false;
                } else {
                    // do nothing
                }
            } else {
                if (set.contains(tc)) {
                    return false;
                } else {
                    map.put(sc, tc);
                    set.add(tc);
                }
            }
        }
        return true;
    }
}

Analysis

这个代码我写了好几个版本：

版本一

代码的run time是23ms (73.13%)，时间复杂度是。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        if (len != t.length()) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        for (int i = 0; i < len; ++i) {
            char sc = s.charAt(i);
            Character c = map.get(sc);
            if (c != null) {
                if (c != t.charAt(i)) {
                    return false;
                } else {
                    // do nothing
                }
            } else {
                char tc = t.charAt(i);
                if (map.containsValue(tc)) {
                    return false;
                } else {
                    map.put(sc, t.charAt(i));
                }
            }
        }
        return true;
    }
}

这里时间复杂度高的原因是使用了s.charAt和map.containsValue。

版本二

代码的run time是16ms (83.81%)，时间复杂度仍然是。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        if (len != t.length()) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < len; ++i) {
            char sc = s.charAt(i);
            Character c = map.get(sc);
            if (c != null) {
                if (c != t.charAt(i)) {
                    return false;
                } else {
                    // do nothing
                }
            } else {
                char tc = t.charAt(i);
                if (set.contains(tc)) {
                    return false;
                } else {
                    map.put(sc, tc);
                    set.add(tc);
                }
            }
        }
        return true;
    }
}

这里的主要问题是对string t在i位置的char连续使用了两次charAt。

版本三

代码的run time是15ms (85.42%)，时间复杂度是

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        if (len != t.length()) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < len; ++i) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            Character c = map.get(sc);
            if (c != null) {
                if (c != tc) {
                    return false;
                } else {
                    // do nothing
                }
            } else {
                if (set.contains(tc)) {
                    return false;
                } else {
                    map.put(sc, tc);
                    set.add(tc);
                }
            }
        }
        return true;
    }
}

使用了charAt导致复杂度降不下来。

版本四

代码的run time是12ms (91.63%)。时间复杂度是。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        if (len != t.length()) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        for (int i = 0; i < len; ++i) {
            char sc = ss[i];
            char tc = ts[i];
            Character c = map.get(sc);
            if (c != null) {
                if (c != tc) {
                    return false;
                } else {
                    // do nothing
                }
            } else {
                if (set.contains(tc)) {
                    return false;
                } else {
                    map.put(sc, tc);
                    set.add(tc);
                }
            }
        }
        return true;
    }
}

这里终于开窍开始用toCharArray了。

版本五

代码的run time是10ms。时间复杂度是。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        for (int i = 0; i < len; ++i) {
            char sc = ss[i];
            char tc = ts[i];
            Character c = map.get(sc);
            if (c != null) {
                if (c != tc) {
                    return false;
                } else {
                    // do nothing
                }
            } else {
                if (set.contains(tc)) {
                    return false;
                } else {
                    map.put(sc, tc);
                    set.add(tc);
                }
            }
        }
        return true;
    }
}

眼神一抽发现传入的两个string长度一定相等。所以把最上面的那行求长度的的length()去掉了。

Leetcode-202: Happy Number

Happy Number

Description

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

My Solution

最开始我用的是HashMap的办法，算法的时间复杂度和空间复杂度不好分析，感觉是O(n^2)。
代码的run time是5 ms。
代码如下所示：

public class Solution {
    public boolean isHappy(int n) {
        if (n < 1) {
            return false;
        }
        if (n == 1 || n == 19) {
            return true;
        }
        int map[] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
        HashSet<Integer> set = new HashSet<>();
        while (true) {
            if (n == 1) {
                return true;
            } else if (!set.add(n)) {
                return false;
            }
            int newN = n;
            n = 0;
            while (newN != 0) {
                n += map[newN % 10];
                newN /= 10;
            }
        }
    }
}

之后我看到这个链接中的方法。
这个方法把问题等价为经典的链表找环问题。
代码的run time是3 ms。
代码如下所示：

public class Solution {
    public boolean isHappy(int n) {
        if (n < 1) {
            return false;
        }
        if (n == 1 || n == 19) {
            return true;
        }

        int slow = n;
        int fast = n;

        do {
            slow = digitSum(slow);
            fast = digitSum(digitSum(fast));
        } while (fast != slow);

        return slow == 1;
    }

    public int digitSum(int n) {
        int map[] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
        int sum = 0;
        while (n != 0) {
            sum += map[n % 10];
            n /= 10;
        }
        return sum;
    }
}

Analysis

感觉有循环都可以套套这个方法。

Leetcode-26: Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

Description

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

My Solution

代码的run time为1 ms，代码如下：

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null) {
            return 0;
        }

        int len = nums.length;
        int count = 1;

        if (len == 0) {
            return 1;
        }

        for (int i = 1; i < len; ++i) {
            if (nums[i] != nums[i - 1]) {
                nums[count++] = nums[i];
            }
        }

        return count;
    }
}

Analysis

对于数组使用的两点法，一个是count另一个是i。
其中i从1到len作用于一个for循环，用以比较i和i - 1是否相等，若不相等count会记录下i处的值并向前移一位。
因为i和count不会冲突，所以可以直接用nums储存新值。

Leetcode-61: Rotate List

Rotate List

Description

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

My Solution

代码的run time是1 ms，时间复杂度为O(n)，空间复杂度是O(1)。
代码如下所示：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k < 1) {
            return head;
        }

        ListNode prev = head;
        ListNode curr = head;
        int len = 0;

        for (len = 0; len < k && curr != null; ++len) {
            curr = curr.next;
        }

        int remainder = k % len;
        if (len != k && remainder != 0) {
            k = remainder;
            curr = head;
            for (len = 0; len < k && curr != null; ++len) {
                curr = curr.next;
            }            
        } else if (curr == null) {
            return head;
        }

        while (curr.next != null) {
            curr = curr.next;
            prev = prev.next;
        }

        curr.next = head;
        head = prev.next;
        prev.next = null;

        return head;
    }
}

Analysis

这道题使用双指针处理。
假设k的值小于list的长度，指针初始化指向list开头。
我们先让一个指针curr向前移动长度k，然后让prev和curr每次移一步，
直到curr的next指向null。
这时prev距list最后一个元素距离为k。
所以我们只要把prev.next作为指针的开头重新拼接列表就可以得到要求的list。

注意，在测试用例中k值是有可能大于list长度的。
这时需要特别考虑。
因为这种情况下len的值会等于list的长度，所以我们可以直接对k取余数。
余数为0且len等于list长度时操作对list无影响，所以直接返回list。
其他时候取余数后重新计算curr。

Leetcode-279: Perfect Squares

Perfect Squares

Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

My Solution

代码的run time是79 ms，完整代码如下：

public class Solution {
    public int numSquares(int n) {
        int sqrtN = (int) Math.sqrt(n);
        int psnPos = 1;

        int minForN[] = new int[n + 1];
        int psn[] = new int[sqrtN + 1];

        for (int i = 1; i <= sqrtN; ++i) {
            psn[i] = i * i;
        }

        for (int i = 1; i <= n; ++i) {
            if (psnPos <= sqrtN && psn[psnPos] == i) {
                minForN[i] = 1;
                ++psnPos;
            } else {
                int minTemp = Integer.MAX_VALUE;
                int minIndex = 0;
                for (int j = 1; j <= sqrtN && psn[j] < i; ++j) {
                    int temp = i - psn[j];
                    if (minTemp > minForN[temp]) {
                        minTemp = minForN[temp];
                        minIndex = temp;
                    }
                }
                minForN[i] = minForN[minIndex] + 1;
            }
        }
        return minForN[n];
    }
}

Analysis

这是一道DP。方法不是最优，有时间补上效率更高的方法。

Leetcode-234: Palindrome Linked List

Palindrome Linked List

Description

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

My Solution

代码的run time是2 ms，代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            ListNode tmp = slow.next;
            slow.next = tmp.next;
            tmp.next = head;
            head = tmp;
        }

        slow = slow.next;
        if (fast.next == null) { // length of the list is odd
            head = head.next;
        }

        for (; slow != null && slow.val == head.val; slow = slow.next, head = head.next);

        if (slow != null) {
            return false;
        } else {
            return true;
        }
    }
}

Analysis

两点法，使用了快慢指针。时间复杂度O(n)，空间复杂度O(1)。

想法是将list的前半部分翻转。然后比较前半部分和后半部分对应项的值是否相等。

慢指针每次走一步并将走过的list进行reverse。
快指针每次走两步，当快指针的next或者next.next变成了null说明慢指针恰好走了一半的距离。
此时让指向list的head的指针和慢指针每次走一步，走时对比两边的值是否都一样。
若存在不一样的value输出false，都一样输出true。

Leetcode-238: Product of Array Except Self

Product of Array Except Self

Description

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

My Solution

代码的run time是2 ms，时间复杂度是O(n)，空间复杂度是O(1).
代码如下所示：

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null) {
            return nums;
        }

        int len = nums.length;
        int left = 1; int right = 1;
        int arr[] = new int[len];

        for (int i = 0; i < len; ++i) {
            arr[i] = left;
            left *= nums[i];
        }
        for (int i = len - 1; i >= 0; --i) {
            arr[i] *= right;
            right *= nums[i];
        }

        return arr;
    }
}

Analysis

此方法参考了这个答案。
很有意思的解法。

Leetcode-203: Remove Linked List Elements

Remove Linked List Elements

Description

Remove all elements from a linked list of integers that have value val.

Example

Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

My Solution

代码的run time是2 ms，代码如下所示：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }

        while (head != null && head.val == val) {
            head = head.next;
        }

        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;

        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        return head;
    }
}

Analysis

基础题，没有有意思的点。

Leetcode-242: Valid Anagram

Description

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

My Solution

代码的 run time 是6 ms (77.88%)。时间复杂度是，空间复杂度是。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s == null || t == null) {
            return false;
        }

        byte[] record = new byte[128];
        int sLength = s.length();
        int tLength = t.length();

        if (sLength != tLength) {
            return false;
        }

        for (int i = 0; i < tLength; ++i){
            ++record[s.charAt(i)];
        }

        for (int i = 0; i < sLength; ++i) {
            --record[t.charAt(i)];
        }

        for (int i = 0; i < 128; ++i) {
            if (record[i] != 0) {
                return false;
            }
        }

        return true;
    }
}

Analysis

这道题虽然归类在Hash Table里面，但是实际上不需要Hash Table。直接使用数组开销更小，速度也更快。

Leetcode-303: Range Sum Query - Immutable

Description

Given an integer array nums, find the sum of the elements between indices and ( $i \leq j$ ), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

You may assume that the array does not change.
There are many calls to sumRange function.

My Solution

代码的 run time 是3 ms (26.34%)。时间复杂度是，空间复杂度是。

public class NumArray {

    int[] sumNums;
    public NumArray(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            nums[i] += nums[i - 1];
        }
        sumNums = nums;
    }

    public int sumRange(int i, int j) {
        if (i == 0) {
            return sumNums[j];
        }
        return sumNums[j] - sumNums[i - 1];
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

Analysis

没什么好讲的。

Leetcode-104: Maximum Depth of Binary Tree

Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

My Solution

代码的run time是5ms (2.24%)，时间复杂度是，空间复杂度是。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 1;
        int maxDepth = depth;
        TreeNode node = null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> depthes = new LinkedList<>();

        stack.addLast(root);
        depthes.addLast(depth);
        while (!stack.isEmpty()) {
            node = stack.removeLast();
            depth = depthes.removeLast();
            if (depth > maxDepth) {
                maxDepth = depth;
            }
            ++depth;
            if (node.left != null) {
                stack.addLast(node.left);
                depthes.addLast(depth);
            }
            if (node.right != null) {
                stack.addLast(node.right);
                depthes.addLast(depth);
            }
        }
        return maxDepth;
    }
}

Analysis

这个代码写得比最基本的递归(1 ms)还慢，没救了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

Leetcode-86: Partition List

Partition List

Description

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

My Solution

代码的run time是1 ms，时间复杂度是O(n)，空间复杂度是O(1)。代码如下所示：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }

        ListNode less = new ListNode(0);
        ListNode lessCur = less;
        ListNode more = new ListNode(0);
        ListNode moreCur = more;

        while (head != null) {
            if (head.val < x) {
                lessCur.next = head;
                lessCur = lessCur.next;
                head = head.next;
                lessCur.next = null;

            } else {
                moreCur.next = head;
                moreCur = moreCur.next;
                head = head.next;
                moreCur.next = null;
            }
        }

        less = less.next;
        if (less == null) {
            return more.next;
        } else {
            lessCur.next = more.next;
            return less;
        }
    }
}

Analysis

有一点要注意，处理list时如果觉得node.next比较乱，一定要小心。
上面程序中的lessCur.next = null和moreCur.next = null就是一个例子。

Leetcode-160: Intersection of Two Linked Lists

Intersection of Two Linked Lists

Description

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

My Solution

代码的run time是2 ms，代码如下所示：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;

        // computer length
        while (curA != null && curB != null) {
            curA = curA.next;
            curB = curB.next;
            ++lenA;
        }
        lenB = lenA;
        while (curA != null) {
            curA = curA.next;
            ++lenA;
        }
        while (curB != null) {
            curB = curB.next;
            ++lenB;
        }

        if (lenA > lenB) {
            int diff = lenA - lenB;
            while (diff != 0) {
                headA = headA.next;
                --diff;
            }

            while (headA != null && headA != headB) {
                headA = headA.next;
                headB = headB.next;
            }

            return headA;
        } else {
            int diff = lenB - lenA;
            while (diff != 0) {
                headB = headB.next;
                --diff;
            }

            while (headA != null && headA != headB) {
                headA = headA.next;
                headB = headB.next;
            }

            return headA;
        }


    }
}

Analysis

也可以算是两点法，先循环一圈找出两个list的长度。
然后让长一点的那个指针先往前走，直到两个长度一样。
然后每次往前走一步，比较两者是否相等，相等则输出节点，直到最后都不相等则输出null。

Leetcode-189: Rotate Array

Rotate Array

Description

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

My Solution

我用了两种方法，其中第一种方法比较蠢。
第一种方法代码的run time是1 ms，时间复杂度是O(n)，空间复杂度是O(n)。
代码如下所示：

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null) {
            return;
        }

        int n = nums.length;

        if (n == 0 || n == 1) {
            return;
        }


        k = k % n;

        if (k == 0) {
            return;
        }

        int newNums[] = new int[n];
        System.arraycopy(nums, 0, newNums, 0, n);

        int i, j;
        for (i = n - k, j = 0; i < n; ++i, ++j) {
            nums[j] = newNums[i];
        }
        for (i = 0; j < n; ++i, ++j) {
            nums[j] = newNums[i];
        }
    }
}

既然都用了System.arraycopy那么下面两个for循环也可以用嘛=。=
第二种方法的run time是0 ms。时间复杂度和空间复杂度与前一个一样，因为本质上是同一种方法。
代码如下所示：

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null) {
            return;
        }

        int n = nums.length;

        if (n == 0 || n == 1) {
            return;
        }

        k = k % n;

        if (k == 0) {
            return;
        }

        int newNums[] = new int[n];
        System.arraycopy(nums, 0, newNums, 0, n);
        System.arraycopy(newNums, n - k, nums, 0, k);
        System.arraycopy(newNums, 0, nums, k, n - k);
    }
}

Analysis

本题再次说明用系统的方法一般比手写快。

Leetcode-59: Spiral Matrix II

Spiral Matrix II

Description

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

My Solution

代码的run time是0 ms，时间复杂度是O(n)，空间复杂度是O(1)。

public class Solution {
    public int[][] generateMatrix(int n) {
        int i = 0;
        int count = 0;
        int matrix[][] = new int[n][n];

        while (n > 1) {
            int tmp1 = n + i - 1;
            int tmp2 = i + 1;
            for (int j = i; j < tmp1; ++j) {
                matrix[i][j] = ++count;
            }
            for (int j = i; j < tmp1; ++j) {
                matrix[j][tmp1] = ++count;
            }
            for (int j = tmp1; j >= tmp2; --j) {
                matrix[tmp1][j] = ++count;
            }
            for (int j = tmp1; j >= tmp2; --j) {
                matrix[j][i] = ++count;
            }
            n -= 2;
            ++i;
        }
        if (n == 1) {
            for (int j = i; j < i + n; ++j) {
                matrix[j][i] = ++count;
            }
        }
        return matrix;
    }
}

Analysis

这个和Problem 54 Spiral Matrix基本一模一样，没什么好说的。

Leetcode-54: Spiral Matrix

Spiral Matrix

Description

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

My Solution

代码的run time是2 ms，时间复杂度是O(n)，空间复杂度是O(1)。

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null) return null;

        int m = matrix.length;
        LinkedList<Integer> list = new LinkedList<>();
        if (m < 1) {
            return list;
        }
        int n = matrix[0].length;
        int i = 0;


        while (m > 1 && n > 1) {
            for (int j = i; j < n + i - 1; ++j) {
                list.add(matrix[i][j]);
            }
            for (int j = i; j < m + i - 1; ++j) {
                list.add(matrix[j][i + n - 1]);
            }
            for (int j = i + n - 1; j >= i + 1; --j) {
                list.add(matrix[i + m - 1][j]);
            }
            for (int j = i + m - 1; j >= i + 1; --j) {
                list.add(matrix[j][i]);
            }
            m -= 2;
            n -= 2;
            ++i;
        }
        if (m == 1) {
            for (int j = i; j < i + n; ++j) {
                list.add(matrix[i][j]);
            }
        } else if (n == 1) {
            for (int j = i; j < i + m; ++j) {
                list.add(matrix[j][i]);
            }
        }
        return list;
    }
}

Analysis

思路很简单，做之前最好在纸上画清楚，不要放在脑子里，否则很容易出bug。

Leetcode-217: Contains Duplicate

Contains Duplicate

Description

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

My Solution

代码的run time是9 ms，时间复杂度是O(n)，空间复杂度是O(n)。
代码如下所示：

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums == null) {
            return false;
        }

        int len = nums.length;

        if (len == 0) {
            return false;
        }

        HashSet<Integer> set = new HashSet<>(len);

        for (int num : nums) {
            if (!set.add(num)) {
                return true;
            }
        }

//        for (int i = 0; i < len; ++i) {
//            if (set.contains(nums[i])) {
//                return true;
//            } else {
//                set.add(nums[i]);
//            }
//        }

        return false;
    }
}

Analysis

注释掉的代码和上面的for循环等价，由于HashSet的add方法的返回值是bool值，所以不需要先判断是否contains。

Leetcode-258: Add Digits

Add Digits

Description

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Solution

程序的run time是2ms，完整代码如下：

public class Solution {
    public int addDigits(int num) {
        if (num == 0) {
            return 0;
        }
        int ans = num % 9;
        ans = (ans == 0) ? 9 : ans;
        return ans;
    }
}

Analysis

这道题需要使用基础的数论知识。假设$\overline{abcd}$是一个四位正整数，则有$1000 * a + 100 * b + 10 * c + d \equiv a + b + c + d \pmod{9}$。然后再对$a + b + c + d$的和做同样的事情直到和变为个位数。此时我们发现$\overline{abcd}$模9和将$\overline{abcd}$各位反复相加直到得到的个位数同余。由于我们模的是9，因此$\overline{abcd}$除以9得到的余数就是答案。

Reasons For Not Accepted

没审清楚题目，题目说的是非负数。

Leetcode-96: Unique Binary Search Trees

Unique Binary Search Trees

Description

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

My Solution

代码的run time是0 ms，代码如下所示：

public class Solution {
    public int numTrees(int n) {
        int a[] = new int[n + 1];

        a[0] = 2;
        a[1] = 1;

        for (int i = 2; i <= n; ++i) {
            int iMinTwo = i - 2;
            int iMinOne = i - 1;
            for (int j = 0; j <= iMinTwo; ++j) {
                a[i] += a[j] * a[iMinOne - j];
            }
        }

        return a[n];
    }
}

Analysis

这是一道DP问题。

令a[n]为BST储存1..n时的树的数目，并假设a[0]=2。
对于a[n]有如下递推关系：$a[n] = \Pi_{i = 0}^{n - 2}a[i]a[n - 1 - i]$。
对于base case来说，a[0] = 2(为了方便假设出来的)，a[1] = 1。

Leetcode-206: Reverse Linked List

Reverse Linked List

Description

Reverse a singly linked list.

My Solution

代码的run time是0 ms，代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        while (cur.next.next != null) {
            ListNode middleTmp = cur.next;
            cur.next = middleTmp.next;
            middleTmp.next = head;
            head = middleTmp;
        }

        cur.next.next = head;
        head = cur.next;
        cur.next = null;

        return head;
    }
}

Analysis

这个比较简单，每次迭代把current指向的地址只向它的下一个的下一个，并把它的下一个移到head之前，最后使head指向移到它前面的那个node。

Leetcode-155: Min Stack

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

My Solution

class MinStack {
    private LinkedList<Integer> ll = new LinkedList<>();
    private LinkedList<Integer> llm = new LinkedList<>();

    public void push(int x) {
        ll.addFirst(x);
        if (llm.isEmpty()) {
            llm.addFirst(x);
        } else {
            int minValue = llm.peekFirst();
            if (minValue > x) {
                llm.addFirst(x);
            } else {
                llm.addFirst(minValue);
            }
        }
    }

    public void pop() {
        ll.pop();
        llm.pop();
    }

    public int top() {
        return ll.peekFirst();
    }

    public int getMin() {
        return llm.peekFirst();
    }
}

Analysis

这道题我用了两个stack。一个用于储存数据，另一个用于储存当前stack中的最小值。

跑了两次，一次超时一次10ms (57.88%)。不知道Leetcode出什么问题了。

Leetcode-73: Set Matrix Zeroes

Set Matrix Zeroes

Description

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?

A straight forward solution using O(mn) space is probably a bad idea.

A simple improvement uses O(m + n) space, but still not the best solution.

Could you devise a constant space solution?

My Solution

代码的run time是2 ms，时间复杂度是O(n)，空间复杂度是O(1)。

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null) {
            return;
        }

        int zeroColZero = 1;
        int lenRow = matrix.length;
        int lenCol = matrix[0].length;

        for (int i = 0; i < lenRow; ++i) {
            int j = 0;
            if (matrix[i][j++] == 0) {
                zeroColZero = 0;
            }
            for (; j < lenCol; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        for (int i = lenRow - 1; i >= 0; --i) {
            for (int j = lenCol - 1; j >= 1; --j) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (zeroColZero == 0) {
                matrix[i][0] = 0;
            }
        }
    }
}

Analysis

这道题我的思路是将第一行作为记录这一列是否需要全部变为零的标记位，每一行的第一列作为这一行是否需要全部变为零的标记位。
这样的话第一列需要用一个单独的标记记录这一列是否全为零，所以我引入了一个新变量zeroColZero。

Leetcode-92: Reverse Linked List II

Reverse Linked List II

Description

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

My Solution

代码的run time是0 ms，代码的时间复杂度是O(n)，空间复杂度是O(1)。
代码如下所示：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m == n || head.next == null) {
            return head;
        }

        ListNode head0 = new ListNode(0);
        head0.next = head;
        head = head0;

        ListNode cur = head;
        n = n - m;

        while (m > 1) {
            --m;
            cur = cur.next;
        }

        ListNode beforeReverse = cur;
        cur = cur.next;
        while (cur.next != null && n > 0) {
            ListNode afterBeforeReverse = beforeReverse.next;
            beforeReverse.next = cur.next;
            cur.next = beforeReverse.next.next;
            beforeReverse.next.next = afterBeforeReverse;
            --n;
        }

        head = head.next;
        return head;
    }
}

Analysis

想法很简单，但是有个处理的小技巧：
我的算法需要操作List中第m个node之前的那个node（在代码里用beforeReverse表示）
当m = 1时这个beforeReverse实际上是不存在的。
针对这个问题可以用if分情况处理，但是我这里在List之前加了一项。
由于m >= 1，因此处理后beforeReverse一定是存在的。
这种做法和开数组是开a[n + 1]以避免处理边界情况的手法很像。

针对这种操作指针的问题可以把图画出来，一步步推，然后按照图上的写。

Leetcode-204: Count Primes

Description

Count the number of prime numbers less than a non-negative number, n.

My Solution

代码的 run time 是18 ms (95.01%)。时间复杂度是 $O(n \log \log n)$ ，空间复杂度是。（时间复杂度分析见wiki和stackoverflow）

public class Solution {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        int count = 1;
        boolean[] notPrimer = new boolean[n + 1]; 

        notPrimer[2] = false; 
        for (int i = 3; i < n; i += 2) {
            if (notPrimer[i]) {
            } else {
                ++count;
                for (int j = i * 3; j < n; j += (i * 2)) {
                    notPrimer[j] = true;
                }
            }
        }

        return count;
    }
}

Analysis

塞法。这个是参考这个回答优化后的解法。

优化思路：因为除2外的素数全部是奇数，所以内外层的循环都不需要遍历偶数，这样可以使内外循环遍历次数减半。

Leetcode-223: Rectangle Area

Rectangle Area

Description

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

My Solution

代码的run time是4 ms，时间复杂度是O(1)，空间复杂度是O(1)。

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int cma = C - A;
        int dmb = D - B;
        int gme = G - E;
        int hmf = H - F;

        long diffX = cma + gme - ((long)Math.max(C, G) - Math.min(A, E));
        long diffY = dmb + hmf - ((long)Math.max(D, H) - Math.min(B, F));
        if (diffX < 0) diffX = 0;
        if (diffY < 0) diffY = 0;
        return cma * dmb + gme * hmf - (int)diffX * (int)diffY;
    }
}

Analysis

(Math.max(C, G) - Math.min(A, E))溢出坑死了。

Leetcode-268: Missing Number

Missing Number

Description

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

My Solution

代码的run time是1 ms，代码的时间复杂度是O(n)，空间复杂度是O(1)。
代码如下所示：

public class Solution {
    public int missingNumber(int[] nums) {
        if (nums == null) {
            return 0;
        }

        long len = nums.length;
        long sumOfNums = 0;

        for (int num : nums) {
            sumOfNums += num;
        }

        long sumOfArray = len * (len + 1) >> 1;

        return (int) (sumOfArray - sumOfNums);
    }
}

Analysis

用int也行，测试用例不会溢出。

Leetcode-128: Longest Consecutive Sequence

Longest Consecutive Sequence

Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

My Solution

代码的run time是14 ms，时间复杂度是O(n)，空间复杂度是O(n)。
代码如下所示：

public class Solution {
    public int longestConsecutive(int[] nums) {
        int maxVal = -1;
        int len = nums.length;
        HashMap<Integer, Integer> hm = new HashMap<>(len);

        for (int num : nums) {
            if (!hm.containsKey(num)) {
                Integer left = hm.get(num - 1);
                Integer right = hm.get(num + 1);
                int sum;
                if (left == null && right == null) {
                    sum = 1;
                } else if (right == null) {
                    sum = left + 1;
                    hm.put(num - left, sum);
                } else if (left == null) {
                    sum = right + 1;
                    hm.put(num + right, sum);
                } else {
                    sum = right + left + 1;
                    hm.put(num - left, sum);
                    hm.put(num + right, sum);
                }
                hm.put(num, sum);
                maxVal = maxVal >= sum ? maxVal : sum;
            }
        }

        return maxVal;
    }
}

Analysis

这个算法是参照这篇文章写出。
原始代码如下：

public int longestConsecutive(int[] num) {
    int res = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int n : num) {
        if (!map.containsKey(n)) {
            int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
            int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
            // sum: length of the sequence n is in
            int sum = left + right + 1;
            map.put(n, sum);

            // keep track of the max length
            res = Math.max(res, sum);

            // extend the length to the boundary(s)
            // of the sequence
            // will do nothing if n has no neighbors
            map.put(n - left, sum);
            map.put(n + right, sum);
        }
        else {
            // duplicates
            continue;
        }
    }
    return res;
}

HashMap储存了连续数字串的长度。
当有新的值插入时，算法只更改这个连续数字串两端的数字储存的长度。

这个代码的run time是16 ms。三次map.put的开销比较大。