LeetCode 340. Longest Substring with At Most K Distinct Characters

LC address: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is “ece” which its length is 3.

Analysis:

需要使用start pointer和end pointer来标记我们考察的substring，利用Hashtable记录这个substring中每一个char的最后index。移动end pointer的时候更新value或者增加新entry，移动start pointer的时候视情况删除entry（如果table(s.charAt(start)) == start的话）。

Solution:

import java.util.*;

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k <= 0) {
            return 0;
        }
        int length = 0;
        int start = 0;
        int end = 0;
        Hashtable lastTable = new Hashtable();
        while (end < s.length()) {
            if (lastTable.size() <= k) {
                lastTable.put(s.charAt(end), end);
                length = Math.max(end - start, length);
                end += 1;
                if (end == s.length() && lastTable.size() <= k) {
                    length = Math.max(end - start, length);
                }
            } else {
                while (start != lastTable.get(s.charAt(start))) {
                    start += 1;
                }
                lastTable.remove(s.charAt(start));
                start += 1;
            }
        }
        return length;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 287. Find the Duplicate Number

LC address: https://leetcode.com/problems/find-the-duplicate-number/

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Analysis:

这道题看似简单，但是加上了只能用O(1)空间，O(n^2)时间之内，并且还不能改动原数组这些条件之后，就需要一些思考了。原来最容易想到的例如使用Set或者排序去完成这道题的方法统统不能用了，但是好在O(n^2)时间内给了一点提示，少于O(n^2)的一般就是O(nlogn)或者O(n)，顺着这个思路可以得到本题的两种比较好的解法。

第一种解法我认为是“可以通过练习做题而想到”的，时间为O(nlogn)。说这方法容易想到是因为，之前我们做过比较多的查找missing integer或者是single number之类的有类似的应用场景，那么我们可不可以回归到最原始的数数呢？数一下多少个1，多少个2，等等，直到找到那个重复数。但是显然这个需要O(n^2)的时间，但是考虑这道题的特殊性，是1~n之间的整数，也就是说我们是有范围的寻找的。所以我们可以通过数一下在[1，n/2]范围内有多少个数字，是不是比n/2这个数字大？如果是，说明重复数在[1，n/2]；否则是在[n/2 + 1， n]之中。利用二分查找来数数，不断缩小范围，所以最后我们需要O(nlogn)来完成这个任务。

第二种做法，我认为是“极需灵感”的做法，甚至我感觉出题人本身都没想到这种做法。这种方法首先分析了这道题的情况，套用了一个P链表的模型，用数学知识进行了一些证明，最后利用two pointers来实现。我并没有想到这种做法，是从别处学习到的，也自知没能力讲清楚，所以愿意去了解这个做法的读者，可以到这个博客去看看，定有收获。

Solution:

Solution 1: Binary Count O(nlogn)

public class Solution {
    public int findDuplicate(int[] nums) {
        int start = 1;
        int end = nums.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (iteration(start, mid, nums)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    private boolean iteration(int start, int end, int[] nums) {
        int count = 0;
        for (int i : nums) {
            if ((i = start)) {
                count += 1;
                if (count > end - start + 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

Solution 2: Two Pinters O(n)

public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 144. Binary Tree Preorder Traversal

LC address: https://leetcode.com/problems/binary-tree-preorder-traversal/

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Analysis:

基本Stack的应用（或者用recursion）。

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur != null) {
                stack.push(cur.right);
                stack.push(cur.left);
                list.add(cur.val);
            }
        }
        return list;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 94. Bianry Tree Inorder Traversal

LC address: https://leetcode.com/problems/binary-tree-inorder-traversal/

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

Analysis:

基本的stack的运用（或者用recursion）。

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
 
        Stack stack = new Stack();
        TreeNode cur = root;
        
        while(!stack.empty() || cur != null){
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        
        return list;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 367. Valid Perfect Square

LC address: https://leetcode.com/problems/valid-perfect-square/

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

Analysis:

普遍能想到的是O(n)的做法，或者利用binary做O(logn)的做法。推荐大家看一下这个博客，里面有更多的解法，有些还比较有意思。

solution:

public class Solution {
    public boolean isPerfectSquare(int num) {
        int end = Math.min(46340, num);
        int start = 1;
        while (start  mid * mid) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return num == start * start;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 360. Sort Transformed Array

LC address: https://leetcode.com/problems/sort-transformed-array/

Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax² + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example:

nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,

Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Result: [-23, -5, 1, 7]

Analysis:

基本就是一道应用数学题，没什么意思，甚至说比较无聊，仔细一点就可以了。

Solution:

快睡着了，写得不好，也懒得注释了，随便看看吧。

public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] result = new int[nums.length];
        double pivot = (a != 0) ? (- b + 0.0) / (2 * a) :  nums[0];
        boolean isLargest = a < 0 || (a == 0 && b < 0);
        int right = 0;
        double diff = Integer.MAX_VALUE;
        for (int i = 0; i  Math.abs(nums[i] - pivot)) {
                diff = Math.abs(nums[i] - pivot);
                right = i;
            }
        }
        int left = right - 1;
        int i = 0;
        while (right = 0) {
            int j = isLargest ? (nums.length - 1 - i) : i;
            if (Math.abs(nums[left] - pivot) < Math.abs(nums[right] - pivot)) {
                result[j] = calculate(nums[left], a, b, c);
                left -= 1;
            } else {
                result[j] = calculate(nums[right], a, b, c);
                right += 1;
            }
            i += 1;
        }
        while (i < nums.length) {
            int j = isLargest ? (nums.length - 1 - i) : i;
            result[j] = (left < 0) ? calculate(nums[right], a, b, c) : calculate(nums[left], a, b, c);
            left -= 1;
            right += 1;
            i += 1;
        }
        return result;
    }

    private int calculate(int n, int a, int b, int c) {
        return a * n * n + b * n + c;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 268. Missing Number

LC address: https://leetcode.com/problems/missing-number/

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?

Analysis:

换汤不换药的题目，XOR就能解决。

Solution:

public class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            result = result ^ i ^nums[i];
        }
        return result;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 319. Bulb Switcher

LC address: https://leetcode.com/problems/bulb-switcher/

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 
So you should return 1, because there is only one bulb is on.

Analysis:

小学数学题，完全平方数才是符合的。

Solution:

public class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.floor(Math.sqrt(n));
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 370. Range Addition

LC address: https://leetcode.com/problems/range-addition/

Assume you have an array of length n initialized with all 0‘s and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

Given:

    length = 5,
    updates = [
        [1,  3,  2],
        [2,  4,  3],
        [0,  2, -2]
    ]

Output:

    [-2, 0, 3, 5, 3]

Explanation:

Initial state:
[ 0, 0, 0, 0, 0 ]

After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]

After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]

After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

Analysis:

这道题特别有意思，题目肯定不想我们每次收到一个operation就对范围内所有数字蠢蠢地一通操作，因为这样如果每个operation的range特别大，operation的数量又特比大的话效率会特别低，那么怎么提高效率呢？

给大家简化一下题目，试着考虑下面这个问题，假设我们有n盏灯，用一个大小为n的boolean array来表示开关情况，我们的operation变成了将某一range内的灯的开关都按一下，也就是toggle一次。假设我们会有很多operation，而查询某个灯的开关情况的次数比较少的情况下，怎么让我们的复杂度降低呢？其实这个和上面那个题目是一种类型，假设我们有一种开关，可以一下子关闭从某个灯开始之后的所有灯，那么每次toggle的operation我们只需要按两下开关就好了（假设我们的灯质量特别好，不会被按坏）。而我们查询某个灯的时候只需要把在那个灯之前的所有开关查看一下就知道这个灯的开关情况了。这样toggle的操作是O(1)，而查询的操作是O(n)。

根据这个思路，依样画葫芦，就可以做我们这道题了，时间为O(n + k)，其中k是operation的数量，额外空间为O(1)。

Solution:

public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        for (int[] operation : updates) {
            result[operation[0]] += operation[2];
            if (operation[1] < length - 1) {
                result[operation[1] + 1] -= operation[2];
            }
        }
        int temp = 0;
        for (int i = 0; i < length; i++) {
            temp += result[i];
            result[i] = temp;
        }
        return result;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git

LeetCode 320. Generalized Abbreviation

LC address: https://leetcode.com/problems/generalized-abbreviation/

Write a function to generate the generalized abbreviations of a word.

Example:

Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Analysis:

这道题还挺有意思的，乍一看很简单，但是实现的时候感觉还是需要思考的，可能是我个人对于String类型的各种题目不太熟悉吧。

这题有两种解法，首先想到的是bottom-up的方法，就是把一个长单词打散，通过小单元的结合再合成长单词，类似于mergesort，但是这个方法很不高效，需要反复处理string，代码也颇为复杂（至少我是这么觉得的）。另一种就比较简单了，利用dfs的搜索方式从头到尾遍历，每一个char可以有两种选择，变成数字或者保留原型，代码很清晰易懂，O(n^2)的复杂度。

Solution:

solution 1: Bottom-Up 188ms

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> abbrevList = new ArrayList<>();
        if (word.length() == 0) {
            abbrevList.add("");
        } else if (word.length() == 1) {
            abbrevList.add(word);
            abbrevList.add("1");
        } else {
            String lastPattern = "[0-9]+$";
            String firstPattern = "^[0-9]+";
            String left = word.substring(0, word.length() / 2);
            String right = word.substring(word.length() / 2, word.length());
            List<String> leftList = generateAbbreviations(left);
            List<String> rightList = generateAbbreviations(right);
            for (String l : leftList) {
                for (String r : rightList) {
                    String ls = l.replaceAll(lastPattern, "");
                    String rs = r.replaceAll(firstPattern, "");
                    if (ls.length() != l.length() && rs.length() != r.length()) {
                        int ln = Integer.parseInt(l.substring(ls.length()));
                        int rn = Integer.parseInt(r.substring(0, r.length() - rs.length()));
                        int i = ln + rn;
                        abbrevList.add(ls + i + rs);
                    } else {
                        abbrevList.add(l + r);
                    }
                }
            }
        }
        return abbrevList;
    }
}

solution 2: DFS 19ms

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> abbrevList = new ArrayList<>();
        if (word.length() == 0) {
            abbrevList.add("");
        } else {
            String curString = "";
            int start = 0;
            int end = word.length();
            int count = 0;
            dfs(curString, start, end, count, abbrevList, word);
        }
        return abbrevList;
    }
    
    private void dfs(String curString, int start, int end,
        int count, List<String> abbrevList, String original) {
        if (start < end) {
            dfs(curString, start + 1, end, count + 1, abbrevList, original);
            String newString = "";
            if (count > 0) {
                newString += count;
                count = 0;
            }
            newString = curString + newString + original.charAt(start);
            dfs(newString, start + 1, end, count, abbrevList, original);
        } else {
            if (count > 0) {
                curString += count;
            }
            abbrevList.add(curString);
        }
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git