1.罗马数字转整数
13. 罗马数字转整数 - 力扣（LeetCode）
罗马数字包含以下七种字符:
I，V，X，L，C，D和M。字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000例如， 罗马数字
2写做II，即为两个并列的 1 。12写做XII，即为X+II。27写做XXVII, 即为XX+V+II。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做
IIII，而是IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。给定一个罗马数字，将其转换成整数。
//这个题需要找规律
class Solution {public static int romanToInt(String s) {HashMap<Character,Integer> hashMap=new HashMap<>();hashMap.put('I',1);hashMap.put('V',5);hashMap.put('X',10);hashMap.put('L',50);hashMap.put('C',100);hashMap.put('D',500);hashMap.put('M',1000);Integer length=s.length();Integer sum=0;for (int i=0;i<s.length();i++){char ch=s.charAt(i);int value=hashMap.get(ch);if(i<length-1&&value<hashMap.get(s.charAt(i+1))){sum=sum-value;}else {sum=sum+value;}//特殊情况//IV:4 IX:9//XL:40 XC:90//CD:400 CM:900}return sum;}}找规律看清楚题目很重要
2.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
""。示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
14. 最长公共前缀 - 力扣（LeetCode）
class Solution2 {public static String longestCommonPrefix(String[] strs) {if(strs==null||strs.length==0){return "";}int length=strs.length;for(int i=0;i<strs[0].length();i++){//第一个字符串的截止范围char ch=strs[0].charAt(i);//字符串的第一个字母for(int j=1;j<length;j++){//和每一个字符串是否匹配if(i==strs[j].length()||strs[j].charAt(i)!=ch){//弹出的条件return strs[0].substring(0,i);}}}return strs[0];}
}
3.三数之和
15. 三数之和 - 力扣（LeetCode）
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为
0且不重复的三元组。注意：答案中不可以包含重复的三元组。
下题解有重复的结果
class Solution3 {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list=new ArrayList<>();int length=nums.length;for(int i=0;i<length-2;i++){for(int j=i+1;j<length-1;j++){for(int z=j+1;z<length;z++){int sum=nums[i]+nums[j]+nums[z];if(sum==0){List<Integer> ls=new ArrayList<>();ls.add(nums[i]);ls.add(nums[j]);ls.add(nums[z]);list.add(ls);}}}}return list;}
}方法一：排序 + 双指针
class Solution {public static List<List<Integer>> threeSum(int[] nums) {int n=nums.length;//把数组从大到小进行排序Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();//枚举a,b,c//其实就是三层循环//枚举abc//不能出现bac//所以需要将数组从大到小进行排序//同时已经有了abc，再出现a需要跳出循环for(int first=0;first<n;first++){//需要和上一次的枚举有所不同if(first>0&&nums[first]==nums[first-1]){continue;//跳出循环}//a是一层循环//bc左右双指针进行遍历//c对应的指针初始指向数组的最右端int third=n-1;int target=-nums[first];//b,c之和需要是targetfor(int second=first+1;second<n;second++){//同样需要和上一次枚举的数有所不同if(second>first+1&&nums[second]==nums[second-1]){continue;}//需要保证b的指针在c的指针的左侧while(second<third&&nums[second]+nums[third]>target){--third;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if (second == third) {break;//跳出本层循环}if (nums[second] + nums[third] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}}4.最接近的三数之和
16. 最接近的三数之和 - 力扣（LeetCode）
学会使用while循环
给你一个长度为
n的整数数组nums和 一个目标值target。请你从nums中选出三个整数，使它们的和与target最接近。返回这三个数的和。
假定每组输入只存在恰好一个解。
超出时间限制
class Solution {public static int threeSumClosest(int[] nums, int target) {int sumsave = Integer.MAX_VALUE;int absave = Integer.MAX_VALUE;// 同样是将数组进行排序// 排序是从小到大进行排序的Arrays.sort(nums);// 1.如果第一层有一个数组大于target，它的下一个我们便结束遍历for (int first = 0; first < nums.length; first++) {// 跳出第一层循环的时刻// 同时不用a,b,c中的a是相同的if (first > 0 && nums[first] == nums[first - 1]) {continue;// 跳出本层循环}if (first > 1 && nums[first - 1] > target) {break;// 直接跳出整个循环}int third = nums.length - 1;int second = first + 1;// 同样是左右指针for (second = first + 1; second < nums.length; second++) {if (second > first + 1 && nums[second] == nums[second - 1]) {continue;// 跳出本层循环}if (second > first + 1 && nums[second - 1] > target) {break;// 直接跳出整个循环}while (second < third) {int sum = nums[third] + nums[second] + nums[first];int abs = Math.abs(sum - target);// abs需要最小的时刻if (abs==0) {return sum;} else if (abs < absave) {sumsave = sum;absave = abs;third--;} }}}return sumsave;}
}class Solution {public static int threeSumClosest(int[] nums, int target) {int sumsave = Integer.MAX_VALUE;int absave = Integer.MAX_VALUE;// 同样是将数组进行排序// 排序是从小到大进行排序的Arrays.sort(nums);// 1.如果第一层有一个数组大于target，它的下一个我们便结束遍历for (int first = 0; first < nums.length; first++) {// 跳出第一层循环的时刻// 同时不用a,b,c中的a是相同的if (first > 0 && nums[first] == nums[first - 1]) {continue;// 跳出本层循环}if (first > 1 && nums[first - 1] > target) {break;// 直接跳出整个循环}int third = nums.length - 1;int second = first + 1;/*// 同样是左右指针for (second = first + 1; second < nums.length; second++) {if (second > first + 1 && nums[second] == nums[second - 1]) {continue;// 跳出本层循环}if (second > first + 1 && nums[second - 1] > target) {break;// 直接跳出整个循环}while (second < third) {int sum = nums[third] + nums[second] + nums[first];int abs = Math.abs(sum - target);// abs需要最小的时刻if (abs == absave) {return sumsave;} else if (abs < absave) {sumsave = sum;absave = abs;third--;} else {break;}}}*///左右指针while (second<third){//如果target大了右指针向左//如果target小了做指针向右int sum = nums[third] + nums[second] + nums[first];int abs = Math.abs(sum - target);// abs需要最小的时刻if (sum==target) {sumsave=sum;return sumsave;}else if(sum<target){if(absave>abs){absave=abs;sumsave=sum;}second++;}else if(sum>target){if(absave>abs){absave=abs;sumsave=sum;}third--;}}}return sumsave;}
}5.电话号码和字母组合（有问题）
17. 电话号码的字母组合 - 力扣（LeetCode）
//实现递归
class Solution {public List<String> letterCombinations(String digits) {List<String> combinations = new ArrayList<String>();if (digits.length() == 0) {return combinations;}Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};backtrack(combinations, phoneMap, digits, 0, new StringBuffer());return combinations;}public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {if (index == digits.length()) {combinations.add(combination.toString());} else {char digit = digits.charAt(index);String letters = phoneMap.get(digit);int lettersCount = letters.length();for (int i = 0; i < lettersCount; i++) {combination.append(letters.charAt(i));backtrack(combinations, phoneMap, digits, index + 1, combination);combination.deleteCharAt(index);}}}
}
//不加入该语句时
//combination.deleteCharAt(index);
//递归过程 //先经历了一层循环，即就是每个字母字符串的大小 //1. //a //d //然后将字符串加入list中 //一层遍历结束后，需要删除第digit遍历的
