标签归档：LeetCode

LeetCode-6

概述

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

分析

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

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

A G M S Y

B F H L N R T X Z

C E I K O Q U W

D J P V

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

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

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

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

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

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

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

解法

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

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

        String result = "";

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

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

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

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

        return result;
    }
}

public class Solution {

public String convert(String s, int numRows) {

if (numRows == 1) {

return s;

}

int sLen = s.length();

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

int sectionNum = 2 * numRows - 2;

String result = "";

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

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

int idx = c * sectionNum + r;

if (idx < sLen) {

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

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

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

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

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

}

return result;

}

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;

}