作者归档：Young

LeetCode-4

发表回复

概述

作为复杂题的第一题(Median of Two Sorted Arrays)，在时间复杂度为O(log (m+n))（ m，n均为数组长度）的要求之下，求两个已排序数组的中位数。

分析

首先中位数的定义可以在 WikiPedia 上了解到。在已排序的前提下，即奇数元素个数的数组，为中间值；偶数元素个数的数组则为中间二值的算数平均数。

那么两个序列求中位数，可以考虑先将二者合并排序之后，进行中位数的求值。

考虑到两数组已经排序，那么我们所需要做的就是进行一次归并排序。

归并排序作为一个相当稳定的排序方式，在时间复杂度上能够满足需求。

考虑到虽然数组是排序数组，但是并没有说明是升序或是降序，无妨，如果是降序，那么将下标从尾部开始即可，但是个人测试，应该没有出现这类 case 。

解法

public class Solution {
    private static final int ASC = 0;
    private static final int DESC = 1;

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double median = 0;

        if (nums1.length + nums2.length == 0) {
            return 0;
        }

        if (nums1.length == 1 && nums2.length == 1) {
            return (nums1[0] + nums2[0]) / 2.0;
        }

        int[] mergedNums = new int[nums1.length + nums2.length];

        int i = 0;
        int j = 0;
        int nums1order = (nums1.length >= 2 && nums1[0] > nums1[1]) ? DESC : ASC;
        int nums2order = (nums2.length >= 2 && nums2[0] > nums2[1]) ? DESC : ASC;
        int mergedIdx = 0;

        for (;i < nums1.length || j < nums2.length;) {
            int realI = i;
            int realJ = j;

            if (i >= nums1.length) {
                mergedNums[mergedIdx] = nums2[realJ];
                ++j;
                ++mergedIdx;
                continue;
            }

            if (j >= nums2.length) {
                mergedNums[mergedIdx] = nums1[realI];
                ++mergedIdx;
                ++i;
                continue;
            }

            int iVal = nums1[realI];
            int jVal = nums2[realJ];

            if (iVal == jVal) {
                mergedNums[mergedIdx] = iVal;
                ++mergedIdx;
                mergedNums[mergedIdx] = jVal;
                ++mergedIdx;
                ++i;
                ++j;
                continue;
            }

            if (iVal > jVal) {
                mergedNums[mergedIdx] = jVal;
                ++mergedIdx;
                ++j;
                continue;
            }

            if (iVal < jVal) {
                mergedNums[mergedIdx] = iVal;
                ++mergedIdx;
                ++i;
            }
        }

        int mergedSize = mergedNums.length;
        int medianIdx = (mergedSize + 1) / 2 - 1;

        if (mergedSize % 2 == 1) {
            median = mergedNums[medianIdx];
        } else {
            medianIdx = mergedIdx / 2;
            median = (mergedNums[medianIdx] + mergedNums[medianIdx - 1]) / 2.0;
        }

        return median;
    }
}

public class Solution {

private static final int ASC = 0;

private static final int DESC = 1;

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

double median = 0;

if (nums1.length + nums2.length == 0) {

return 0;

}

if (nums1.length == 1 && nums2.length == 1) {

return (nums1[0] + nums2[0]) / 2.0;

}

int[] mergedNums = new int[nums1.length + nums2.length];

int i = 0;

int j = 0;

int nums1order = (nums1.length >= 2 && nums1[0] > nums1[1]) ? DESC : ASC;

int nums2order = (nums2.length >= 2 && nums2[0] > nums2[1]) ? DESC : ASC;

int mergedIdx = 0;

for (;i < nums1.length || j < nums2.length;) {

int realI = i;

int realJ = j;

if (i >= nums1.length) {

mergedNums[mergedIdx] = nums2[realJ];

++j;

++mergedIdx;

continue;

}

if (j >= nums2.length) {

mergedNums[mergedIdx] = nums1[realI];

++mergedIdx;

++i;

continue;

}

int iVal = nums1[realI];

int jVal = nums2[realJ];

if (iVal == jVal) {

mergedNums[mergedIdx] = iVal;

++mergedIdx;

mergedNums[mergedIdx] = jVal;

++mergedIdx;

++i;

++j;

continue;

}

if (iVal > jVal) {

mergedNums[mergedIdx] = jVal;

++mergedIdx;

++j;

continue;

}

if (iVal < jVal) {

mergedNums[mergedIdx] = iVal;

++mergedIdx;

++i;

}

int mergedSize = mergedNums.length;

int medianIdx = (mergedSize + 1) / 2 - 1;

if (mergedSize % 2 == 1) {

median = mergedNums[medianIdx];

} else {

medianIdx = mergedIdx / 2;

median = (mergedNums[medianIdx] + mergedNums[medianIdx - 1]) / 2.0;

}

return median;

}

leetcode-58-263-326-345

发表回复

本次将Length of Last Word，Ugly Number，Power of Three，Reverse Vowels of a String 一起写解题思路。

这四道题都相当简单，整个解题思路都会很简略。

58 Length of Last Word

概述

Length of Last Word 题意是求字符串中最后一组连续非空字符的字符串长度。

分析

从字符串末尾开始向前查找，如果一直是空白字符，那么长度不应被计入。

当开始遇到非空字符，开始计算长度，直到遇到下一个空白字符，返回结果。

解法

public class Solution {
    public int lengthOfLastWord(String s) {
        boolean canCount = false;
        int len = 0;

        for (int i = s.length() - 1; i >= 0; --i) {
            if (s.substring(i, i + 1).equals(" ")) {
                if (canCount) {
                    return len;
                }
            } else {
                if (!canCount) {
                    canCount = true;
                }

                ++len;
            }
        }

        return len;
    }
}

public class Solution {

public int lengthOfLastWord(String s) {

boolean canCount = false;

int len = 0;

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

if (s.substring(i, i + 1).equals(" ")) {

if (canCount) {

return len;

}

} else {

if (!canCount) {

canCount = true;

}

++len;

}

return len;

}

263 Ugly Number

概述

Ugly Number 即判断一个数字其因数只能由2、3、5构成。1也被认为是ugly number。

分析

直接通过循环，尝试对输入数字，分别尝试是否能够整除2、3、5，如果能除到1，说明必然是这三个数字中的1到3个相乘得到的，反之则不是。

解法

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

        if (1 == num) {
            return true;
        }

        int[] factors = {2, 3, 5};

        int n = num;

        for (int factor: factors) {
            while (0 == n % factor) {
                n /= factor;

                if (n == 1) {
                    return true;
                }
            }
        }

        return false;
    }
}

public class Solution {

public boolean isUgly(int num) {

if (num <= 0) {

return false;

}

if (1 == num) {

return true;

}

int[] factors = {2, 3, 5};

int n = num;

for (int factor: factors) {

while (0 == n % factor) {

n /= factor;

if (n == 1) {

return true;

}

return false;

}

326 Power of Three

概述

Power of Three 即判断输入数字是否是是3的n次幂。

分析

如果用循环除法，那么只需要判断能不能除到1即可。

在不使用循环的情况下，考虑到输入的数字范围仅仅是int，那么结果个数是有限的，可以通过提前算出结果，判断输入是否等于这些结果之一判断。

解法

public class Solution {
    public boolean isPowerOfThree(int n) {
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        m.put(1, 1);
        m.put(3, 1);
        m.put(9, 1);
        m.put(27, 1);
        m.put(81, 1);
        m.put(243, 1);
        m.put(729, 1);
        m.put(2187, 1);
        m.put(6561, 1);
        m.put(19683, 1);
        m.put(59049, 1);
        m.put(177147, 1);
        m.put(531441, 1);
        m.put(1594323, 1);
        m.put(4782969, 1);
        m.put(14348907, 1);
        m.put(43046721, 1);
        m.put(129140163, 1);
        m.put(387420489, 1);
        m.put(1162261467, 1);

        return m.containsKey(n);
    }
}

public class Solution {

public boolean isPowerOfThree(int n) {

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

m.put(1, 1);

m.put(3, 1);

m.put(9, 1);

m.put(27, 1);

m.put(81, 1);

m.put(243, 1);

m.put(729, 1);

m.put(2187, 1);

m.put(6561, 1);

m.put(19683, 1);

m.put(59049, 1);

m.put(177147, 1);

m.put(531441, 1);

m.put(1594323, 1);

m.put(4782969, 1);

m.put(14348907, 1);

m.put(43046721, 1);

m.put(129140163, 1);

m.put(387420489, 1);

m.put(1162261467, 1);

return m.containsKey(n);

}

345 Reverse Vowels of a String

概述

Reverse Vowels of a String 需要我们完成的是交换字符串中所有元音字母的位置。

分析

如果一个字符串仅仅包含元音字母，那么对调位置其实与反转字符串操作等同。

可以考虑抽取所有的元音字母组成一个字符串，反转之后重新遍历字符串，遇到元音字母替换即可。

解法

public class Solution {
    public String reverseVowels(String s) {
        HashMap<String, Boolean> vowels = new HashMap<String, Boolean>();
        vowels.put("a", true);
        vowels.put("e", true);
        vowels.put("i", true);
        vowels.put("o", true);
        vowels.put("u", true);
        vowels.put("A", true);
        vowels.put("E", true);
        vowels.put("I", true);
        vowels.put("O", true);
        vowels.put("U", true);

        String allVowels = "";
        StringBuilder sb = new StringBuilder();

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

            if (vowels.containsKey(c + "")) {
                sb.append(c);
            }
        }

        String reversedVowels = sb.reverse().toString();
        int reversedIdx = 0;
        StringBuilder result = new StringBuilder();

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

            if (vowels.containsKey(c + "")) {
                result.append(reversedVowels.charAt(reversedIdx));
                ++reversedIdx;
                continue;
            }

            result.append(c);
        }

        return result.toString();
    }
}

public class Solution {

public String reverseVowels(String s) {

HashMap<String, Boolean> vowels = new HashMap<String, Boolean>();

vowels.put("a", true);

vowels.put("e", true);

vowels.put("i", true);

vowels.put("o", true);

vowels.put("u", true);

vowels.put("A", true);

vowels.put("E", true);

vowels.put("I", true);

vowels.put("O", true);

vowels.put("U", true);

String allVowels = "";

StringBuilder sb = new StringBuilder();

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

char c = s.charAt(i);

if (vowels.containsKey(c + "")) {

sb.append(c);

}

String reversedVowels = sb.reverse().toString();

int reversedIdx = 0;

StringBuilder result = new StringBuilder();

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

char c = s.charAt(i);

if (vowels.containsKey(c + "")) {

result.append(reversedVowels.charAt(reversedIdx));

++reversedIdx;

continue;

}

result.append(c);

}

return result.toString();

}

LeetCode-3

发表回复

概述

今天份的LeetCode题目 Longest Substring Without Repeating Characters 也是一道 Medium 的题目。

大意即找出给定字符串中的连续最长非重复子序列的长度。

分析

首先，字符串连续的前提之下，若在位置 n 与 m (m>n)出现了重复的字符，n位置以及之前的字符是不能再继续算入连续的非重复字符串的，所以，这时候统计的字符串的起始位置要变为 n + 1 位置下的字符。

在出现重复时，判断当前已经连续的非重复字符的个数是否已经大于已记录的最长字符串的长度，如大于则替换之。

最后返回计算出的结果即可。

这一方法只需一次遍历字符串即可得知最大的长度，由于使用了HashMap存储最长子串中的字符与下标的对应关系，时间复杂度为O(n)。

解法

public class Solution {
        public int lengthOfLongestSubstring(String s) {
        int longest = 0;
        int startIdx = 0;

        for (int i = 0; i < s.length(); ++i) {             String atI = s.substring(i, i + 1);             String currentLongest = s.substring(startIdx, i);             int repeatIdx = currentLongest.indexOf(atI);             if (repeatIdx >= 0) {
                if (currentLongest.length() > longest) {
                    longest = currentLongest.length();
                }

                startIdx += (repeatIdx + 1);
            }
        }

        if (s.substring(startIdx).length() > longest) {
            longest = s.substring(startIdx).length();
        }

        return longest;
    }
}

public class Solution {

public int lengthOfLongestSubstring(String s) {

int longest = 0;

int startIdx = 0;

for (int i = 0; i < s.length(); ++i) { String atI = s.substring(i, i + 1); String currentLongest = s.substring(startIdx, i); int repeatIdx = currentLongest.indexOf(atI); if (repeatIdx >= 0) {

if (currentLongest.length() > longest) {

longest = currentLongest.length();

}

startIdx += (repeatIdx + 1);

}

if (s.substring(startIdx).length() > longest) {

longest = s.substring(startIdx).length();

}

return longest;

}

LeetCode-2

发表回复

概述

Add Two Numbers 难度为Medium，这一题目简单来说即给出两个序列，代表两个整数，模拟加法运算。

分析

这一题难度个人认为依然不大，即把正常加法的算式过程用程序表示。需要特殊处理的是进位这一操作。

正常的加法竖式运算，需要将最低位对其，然后开始从低位向高位计算。

再具体一些，考虑一个加法运算，两个数相加，一个数字长度为n，一个数字为m，m>n，那么，和的字符个数至多为m+1。

对于进位值的计算，其实就是将当前位数的值以及前期的进位值相加，除以10即为进位制。

这一解法可以在O(n)的时间复杂度上解决问题。

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Map<Integer, Integer> lm1 = new HashMap<>();
        Map<Integer, Integer> lm2 = new HashMap<>();
        
        ListNode l = l1;
        int idx = 0;
        
        while (l != null) {
            lm1.put(idx, l.val);
            ++idx;
            l = l.next;
        }
        
        l = l2;
        idx = 0;
        
        while (l != null) {
            lm2.put(idx, l.val);
            ++idx;
            l = l.next;
        }
        
        Map<Integer, Integer> longer = (lm1.size() > lm2.size() ? lm1 : lm2);
        Map<Integer, Integer> shorter = (lm1.size() <= lm2.size() ? lm1 : lm2);
        int lengthGap = longer.size() - shorter.size();
        
        ListNode result = new ListNode(0);
        ListNode resultRef = result;
        int carryVal = 0;
        
        for (int i = 0; i < longer.size(); ++i) {
            int nowVal = 0;
            
            if (i >= shorter.size()) {
                nowVal = longer.get(i) + carryVal;
            } else {
                nowVal = longer.get(i) + shorter.get(i) + carryVal;
            }
            
            carryVal = (nowVal / 10);
            resultRef.val = (nowVal >= 10 ? nowVal % 10 : nowVal);
            
            if (i != longer.size() - 1) {
                resultRef.next = new ListNode(carryVal);
                resultRef = resultRef.next;
            } else {
                if (carryVal > 0) {
                    resultRef.next = new ListNode(carryVal);
                    resultRef = resultRef.next;
                }
                
                resultRef.next = null;
            }
        }
        
        return result;
    }
}

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

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

* }

public class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

Map<Integer, Integer> lm1 = new HashMap<>();

Map<Integer, Integer> lm2 = new HashMap<>();

ListNode l = l1;

int idx = 0;

while (l != null) {

lm1.put(idx, l.val);

++idx;

l = l.next;

}

l = l2;

idx = 0;

while (l != null) {

lm2.put(idx, l.val);

++idx;

l = l.next;

}

Map<Integer, Integer> longer = (lm1.size() > lm2.size() ? lm1 : lm2);

Map<Integer, Integer> shorter = (lm1.size() <= lm2.size() ? lm1 : lm2);

int lengthGap = longer.size() - shorter.size();

ListNode result = new ListNode(0);

ListNode resultRef = result;

int carryVal = 0;

for (int i = 0; i < longer.size(); ++i) {

int nowVal = 0;

if (i >= shorter.size()) {

nowVal = longer.get(i) + carryVal;

} else {

nowVal = longer.get(i) + shorter.get(i) + carryVal;

}

carryVal = (nowVal / 10);

resultRef.val = (nowVal >= 10 ? nowVal % 10 : nowVal);

if (i != longer.size() - 1) {

resultRef.next = new ListNode(carryVal);

resultRef = resultRef.next;

} else {

if (carryVal > 0) {

resultRef.next = new ListNode(carryVal);

resultRef = resultRef.next;

}

resultRef.next = null;

}

return result;

}

LeetCode-1

发表回复

概述

作为简单题的第一题(Two Sum)，简答来说就是给出一个序列以及目标值，求出能加和出目标值的两个数字在数组中的下标。

分析

这个题目可以说是一目了然，直接能够想到的解法就是遍历这一个序列，然后遍历下标大于当前遍历到的数字的元素，如果有匹配的数字就直接返回结果即可。

如果单纯遍历，时间复杂度高达O(n²)，这个复杂度不太令人满意。

那么是否可以通过空间换时间呢？自然是没问题的。

后续考虑通过使用HashMap的方式记录每个值对应的元素的下标，每次检查是否有当前值相加得到目标值的的key存在，将时间复杂度降低到了O(n)，不过空间复杂度也上升到了O(n)。

解法

public class Solution {
    public int[] twoSum(int[] nums, int target) {
                Map<Integer, Integer> numIdxMap = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; ++i) {
            numIdxMap.put(nums[i], i);
        }

        int[] idx = new int[2];

        for (int i = 0; i < nums.length; ++i) {
            if (numIdxMap.containsKey(target - nums[i])) {
                int j = numIdxMap.get(target - nums[i]);

                if (i == j) {
                    continue;
                }

                idx[0] = i;
                idx[1] = j;

                if (idx[0] > idx[1]) {
                    int tmp = idx[1];
                    idx[1] = idx[0];
                    idx[0] = tmp;
                }

                break;
            }
        }

        return idx;
    }
}

public class Solution {

public int[] twoSum(int[] nums, int target) {

Map<Integer, Integer> numIdxMap = new HashMap<Integer, Integer>();

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

numIdxMap.put(nums[i], i);

}

int[] idx = new int[2];

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

if (numIdxMap.containsKey(target - nums[i])) {

int j = numIdxMap.get(target - nums[i]);

if (i == j) {

continue;

}

idx[0] = i;

idx[1] = j;

if (idx[0] > idx[1]) {

int tmp = idx[1];

idx[1] = idx[0];

idx[0] = tmp;

}

break;

}

return idx;

}