本次将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题目 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;

}

Wislay

月度归档：2016年05月

leetcode-58-263-326-345

58 Length of Last Word

概述

分析

解法

263 Ugly Number

概述

分析

解法

326 Power of Three

概述

分析

解法

345 Reverse Vowels of a String

概述

分析

解法

LeetCode-3

概述

分析

解法