LeetCode-Java(03)

9. 回文数

class Solution {public boolean isPalindrome(int x) {if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}int revertedNumber = 0;while (x > revertedNumber) {revertedNumber = revertedNumber * 10 + x % 10;x /= 10;}// 当长度为奇数时通过revertedNumber/10 去除处于中位的数字。return x == revertedNumber || x == revertedNumber / 10;}
}

11. 盛最多水的容器

双指针

class Solution {public int maxArea(int[] height) {int ans=0;// 首位指针int i=0,j=height.length-1;while(i<j){ans=Math.max(ans,(j-i)*Math.min(height[i],height[j]));if(height[i]>=height[j]) j--;else i++;}return ans;}
}

写到一起 时间快不少

class Solution {public int maxArea(int[] height) {int ans=0;int i=0,j=height.length-1;while(i<j){if(height[i]>=height[j]) ans=Math.max(ans,(j-i)*height[j--]);else ans=Math.max(ans,(j-i)*height[i++]);}return ans;}
}

12. Integer to Roman

class Solution {public String intToRoman(int num) {// 4、9、40、90、400、900 作为加法因子，它们在结果中只能出现一次。int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};StringBuilder stringBuilder = new StringBuilder();int index = 0;while (index < 13) {// 贪心策略while (num >= nums[index]) {stringBuilder.append(romans[index]);num -= nums[index];}index++;}return stringBuilder.toString();}
}

13. Roman to Integer

和前一道相反，直接累加字符的值

class Solution {public int romanToInt(String s) {// 4、9、40、90、400、900 作为加法因子，它们在结果中只能出现一次。// int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};// String[] romans = {"M", "f", "D", "e", "C", "d", "L", "c", "X", "b", "V", "a", "I"};s = s.replace("IV","a");s = s.replace("IX","b");s = s.replace("XL","c");s = s.replace("XC","d");s = s.replace("CD","e");s = s.replace("CM","f");int res = 0;for (int i=0; i<s.length(); i++) {res += which(s.charAt(i));}return res;}private int which(char ch) {switch(ch) {case 'I': return 1;case 'V': return 5;case 'X': return 10;case 'L': return 50;case 'C': return 100;case 'D': return 500;case 'M': return 1000;case 'a': return 4;case 'b': return 9;case 'c': return 40;case 'd': return 90;case 'e': return 400;case 'f': return 900;}return 0;}
}

优化一下

class Solution {public int romanToInt(String s) {int[] nums = new int[s.length()];int res = 0;for(int i = 0;i <s.length();i ++){nums[i] = trans(s.charAt(i));}for(int i = 0;i < s.length();i ++){// 前面的数字小于后面的数字，加上他们的差值 注意i最多取到倒数第二位 跳出执行下一个if(i != s.length() - 1 && nums[i] < nums[i + 1]){res += nums[i + 1] - nums[i];i ++;continue;}// 一直累加res += nums[i];}return res;}private int trans(char cur){switch(cur){case 'I': return 1;case 'V': return 5;case 'X': return 10;case 'L': return 50;case 'C': return 100;case 'D': return 500;case 'M': return 1000;}return 0;}
}

14. Longest Common Prefix

 每两个字符串进行比较

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];int count = strs.length;for (int i = 1; i < count; i++) {// 找两个字符串的公共最长前缀，两两比较，每次比较前面得出的最长前缀prefix = longestCommonPrefix(prefix, strs[i]);if (prefix.length() == 0) {break;}}return prefix;}public String longestCommonPrefix(String str1, String str2) {int length = Math.min(str1.length(), str2.length());int index = 0;while (index < length && str1.charAt(index) == str2.charAt(index)) {index++;}// substring 的参数索引 左闭右开return str1.substring(0, index);}
}