缺失的第一个正整数
具体做法
step 1:构建一个哈希表,用于记录数组中出现的数字。
step 2:从1开始,遍历到n,查询哈希表中是否有这个数字,如果没有,说明它就是数组缺失的第一个正整数,即找到。
step 3:如果遍历到最后都在哈希表中出现过了,那缺失的就是n+1.
import java.util.*; public class Solution { public int minNumberDisappeared (int[] nums) { int n = nums.length; HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); //哈希表记录数组中出现的每个数字 for (int i = 0; i < n; i++) mp.put(nums[i], 1); int res = 1; //从1开始找到哈希表中第一个没有出现的正整数 while (mp.containsKey(res)) res++; return res; } }
*三数之和
具体做法
step 1:排除边界特殊情况。
step 2:既然三元组内部要求非降序排列,那我们先得把这个无序的数组搞有序了,使用sort函数优先对其排序。
step 3:得到有序数组后,遍历该数组,对于每个遍历到的元素假设它是三元组中最小的一个,那么另外两个一定在后面。
step 4:需要三个数相加为0,则另外两个数相加应该为上述第一个数的相反数,我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾,如果二者相加为目标值,那么可以记录,而且二者中间的数字相加可能还会有。
step 5:如果二者相加大于目标值,说明右指针太大了,那就将其左移缩小,相反如果二者相加小于目标值,说明左指针太小了,将其右移扩大,直到两指针相遇,剩余子数组找完了。
注:对于三个数字都要判断是否相邻有重复的情况,要去重。
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>(); int n = num.length; //不够三元组 if(n < 3) return res; //排序 Arrays.sort(num); for(int i = 0; i < n - 2; i++){ if(i != 0 && num[i] == num[i - 1]) continue; //后续的收尾双指针 int left = i + 1; int right = n - 1; //设置当前数的负值为目标 int target = -num[i]; while(left < right){ //双指针指向的二值相加为目标,则可以与num[i]组成0 if(num[left] + num[right] == target){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.add(num[i]); temp.add(num[left]); temp.add(num[right]); res.add(temp); while(left + 1 < right && num[left] == num[left + 1]) //去重 left++; while(right - 1 > left && num[right] == num[right - 1]) //去重 right--; //双指针向中间收缩 left++; right--; } //双指针指向的二值相加大于目标,右指针向左 else if(num[left] + num[right] > target) right--; //双指针指向的二值相加小于目标,左指针向右 else left++; } } return res; } }
递归/回溯
*没有重复项数字的全排列
思路
全排列就是对数组元素交换位置,使每一种排列都可能出现。因为题目要求按照字典序排列输出,那毫无疑问第一个排列就是数组的升序排列,它的字典序最小,后续每个元素与它后面的元素交换一次位置就是一种排列情况,但是如果要保持原来的位置不变,那就不应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变,不会漏情况。
如何保证每个元素能和从自己开始后的每个元素都交换位置,这种时候我们可以考虑递归。为什么可以使用递归?我们可以看数组[1,2,3,4],如果遍历经过一个元素2以后,那就相当于我们确定了数组到该元素为止的前半部分,前半部分1和2的位置都不用变了,只需要对3,4进行排列,这对于后半部分而言同样是一个全排列,同样要对从每个元素开始往后交换位置,因此后面部分就是一个子问题。那我们考虑递归的几个条件:
终止条件: 要交换位置的下标到了数组末尾,没有可交换的了,那这就构成了一个排列情况,可以加入输出数组。
返回值: 每一级的子问题应该把什么东西传递给父问题呢,这个题中我们是交换数组元素位置,前面已经确定好位置的元素就是我们返还给父问题的结果,后续递归下去会逐渐把整个数组位置都确定,形成一种排列情况。
本级任务: 每一级需要做的就是遍历从它开始的后续元素,每一级就与它交换一次位置。
如果只是使用递归,我们会发现,上例中的1与3交换位置以后,如果2再与4交换位置的时候,我们只能得到3412这种排列,无法得到1432这种情况。这是因为遍历的时候1与3交换位置在2与4交换位置前面,递归过程中就默认将后者看成了前者的子问题,但是其实我们1与3没有交换位置的情况都没有结束,相当于上述图示中只进行了第一个分支。因此我们用到了回溯。处理完1与3交换位置的子问题以后,我们再将其交换回原来的情况,相当于上述图示回到了父节点,那后续完整的情况交换我们也能得到。
//遍历后续的元素 for(int i = index; i < num.size(); i++){ //交换二者 swap(num, i, index); //继续往后找 recursion(res, num, index + 1); //回溯 swap(num, i, index); }
具体做法
step 1:先将数组排序,获取字典序最小的排列情况。
step 2:递归的时候根据当前下标,遍历后续的元素,交换二者位置后,进入下一层递归。
step 3:处理完一分支的递归后,将交换的情况再换回来进行回溯,进入其他分支。
step 4:当前下标到达数组末尾就是一种排列情况。
import java.util.*; public class Solution { //交换位置函数 private void swap(ArrayList<Integer> num, int i1, int i2 ){ int temp = num.get(i1); num.set(i1, num.get(i2)); num.set(i2, temp); } public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> num, int index) { //分枝进入结尾,找到一种排列 if (index == num.size() - 1) { res.add(num); } else { //遍历后续的元素 for (int i = index; i < num.size(); i++) { //交换二者 swap(num, i, index); //继续往后找 recursion(res, num, index + 1); //回溯 swap(num, i, index); } } } public ArrayList<ArrayList<Integer>> permute(int[] num) { //先按字典序排序 Arrays.sort(num); ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> nums = new ArrayList<Integer>(); //数组转ArrayList for (int i = 0; i < num.length; i++) nums.add(num[i]); recursion(res, nums, 0); return res; } }
字符串
字符串变形
思路
将单词位置的反转,那肯定前后都是逆序,不如我们先将整个字符串反转,这样是不是单词的位置也就随之反转了。但是单词里面的成分也反转了啊,既然如此我们再将单词里面的部分反转过来就行。
具体做法
step 1:遍历字符串,遇到小写字母,转换成大写,遇到大写字母,转换成小写,遇到空格正常不变。
step 2:第一次反转整个字符串,这样基本的单词逆序就有了,但是每个单词的字符也是逆的。
step 3:再次遍历字符串,以每个空间为界,将每个单词反转回正常。
import java.util.*; public class Solution { public String trans(String s, int n) { if (n == 0) return s; StringBuffer res = new StringBuffer(); for (int i = 0; i < n; i++) { //大小写转换 if (s.charAt(i) <= 'Z' && s.charAt(i) >= 'A') res.append((char)(s.charAt(i) - 'A' + 'a')); else if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') res.append((char)(s.charAt(i) - 'a' + 'A')); else //空格直接复制 res.append(s.charAt(i)); } //翻转整个字符串 res = res.reverse(); //翻转整个字符串的每个单词 for (int i = 0; i < n; i++) { int j = i; //以空格为界,找到每个单词 while (j < n && res.charAt(j) != ' ') j++; //找到每个单词后反转替换res中的单词,重置i的位置,继续找后一个单词 String temp = res.substring(i, j); StringBuffer buffer = new StringBuffer(temp); temp = buffer.reverse().toString(); res.replace(i, j, temp); i = j; } return res.toString(); } }
最长公共前缀
思路
既然是公共前缀,那我们可以用一个字符串与其他字符串进行比较,从第一个字符开始,逐位比较,找到最长公共子串。
具体做法
step 1:处理数组为空的特殊情况。
step 2:因为最长公共前缀的长度不会超过任何一个字符串的长度,因此我们逐位就以第一个字符串为标杆,遍历第一个字符串的所有位置,取出字符。
step 3:遍历数组中后续字符串,依次比较其他字符串中相应位置是否为刚刚取出的字符,如果是,循环继续,继续查找,如果不是或者长度不足,说明从第i位开始不同,前面的都是公共前缀。
step 4:如果遍历结束都相同,最长公共前缀最多为第一个字符串。
import java.util.*; public class Solution { public String longestCommonPrefix (String[] strs) { int n = strs.length; //空字符串数组 if (n == 0) return ""; //遍历第一个字符串的长度 for (int i = 0; i < strs[0].length(); i++) { char temp = strs[0].charAt(i); //遍历后续的字符串 for (int j = 1; j < n; j++) //比较每个字符串该位置是否和第一个相同,i == strs[j].length()是长度不足 if (i == strs[j].length() || strs[j].charAt(i) != temp) //不相同则结束,也就是截取第一个字符串的指定长度 return strs[0].substring(0, i); } //上面截取后第一个字符串就是最长公共前缀 return strs[0]; } }
*验证IP地址
思路
我们可以先对IP字符串进行分割,然后依次判断每个分割是否符合要求。
具体做法
step 1:写一个split函数(或者内置函数)。
step 2:遍历IP字符串,遇到.或者:将其分开储存在一个数组中。
step 3:遍历数组,对于IPv4,需要依次验证分组为4,分割不能缺省,没有前缀0或者其他字符,数字在0-255范围内。
step 4:对于IPv6,需要依次验证分组为8,分割不能缺省,每组不能超过4位,不能出现除数字小大写a-f以外的字符。
import java.util.*; public class Solution { boolean isIPv4 (String IP) { if(IP.indexOf('.') == -1){ return false; } String[] s = IP.split("\\."); //IPv4必定为4组 if(s.length != 4) return false; for(int i = 0; i < s.length; i++){ //不可缺省,有一个分割为零,说明两个点相连 if(s[i].length() == 0) return false; //比较数字位数及不为零时不能有前缀零 if(s[i].length() < 0 || s[i].length() > 3 || (s[i].charAt(0)=='0' && s[i].length() != 1)) return false; int num = 0; //遍历每个分割字符串,必须为数字 for(int j = 0; j < s[i].length(); j++){ char c = s[i].charAt(j); if (c < '0' || c > '9') return false; //转化为数字比较,0-255之间 num = num * 10 + (int)(c - '0'); if(num < 0 || num > 255) return false; } } return true; } boolean isIPv6 (String IP) { if (IP.indexOf(':') == -1) { return false; } String[] s = IP.split(":",-1); //IPv6必定为8组 if(s.length != 8){ return false; } for(int i = 0; i < s.length; i++){ //每个分割不能缺省,不能超过4位 if(s[i].length() == 0 || s[i].length() > 4){ return false; } for(int j = 0; j < s[i].length(); j++){ //不能出现a-fA-F以外的大小写字符 char c = s[i].charAt(j); boolean expr = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F') ; if(!expr){ return false; } } } return true; } String solve(String IP) { if(isIPv4(IP)) return "IPv4"; else if(isIPv6(IP)) return "IPv6"; return "Neither"; } }
*大数加法
思路
大整数相加,就可以按照整数相加的方式,从个位开始,逐渐往上累加,换到字符串中就是从两个字符串的末尾开始相加。
具体做法
step 1:若是其中一个字符串为空,直接返回另一个,不用加了。
step 2:交换两个字符串的位置,我们是s为较长的字符串,t为较短的字符串,结果也记录在较长的字符串中。
step 3:从后往前遍历字符串s,每次取出字符转数字,加上进位制,将下标转换为字符串t中从后往前相应的下标,如果下标为非负数则还需要加上字符串t中相应字符转化的数字。
step 4:整型除法取进位,取模算法去掉十位,将计算后的结果放入较长数组对应位置。
step 5:如果遍历结束,进位值还有,则需要直接在字符串s前增加一个字符‘1’
import java.util.*; public class Solution { public String solve (String s, String t) { //若是其中一个为空,返回另一个 if (s.length() <= 0) return t; if (t.length() <= 0) return s; //让s为较长的,t为较短的 if (s.length() < t.length()) { String temp = s; s = t; t = temp; } int carry = 0; //进位标志 char[] res = new char[s.length()]; //从后往前遍历较长的字符串 for (int i = s.length() - 1; i >= 0; i--) { //转数字加上进位 int temp = s.charAt(i) - '0' + carry; //转较短的字符串相应的从后往前的下标 int j = i - s.length() + t.length(); //如果较短字符串还有 if (j >= 0) //转数组相加 temp += t.charAt(j) - '0'; //取进位 carry = temp / 10; //去十位 temp = temp % 10; //修改结果 res[i] = (char)(temp + '0'); } String output = String.valueOf(res); //最后的进位 if (carry == 1) output = '1' + output; return output; } }
双指针
合并两个有序的数组
思路
既然是两个已经排好序的数组,如果可以用新的辅助数组,那很容易我们可以借助归并排序的思想,将排好序的两个子数组合并到一起。但是这道题要求我们在数组A上面添加,那因为数组A后半部分相当于为空,则我们可以考虑逆向使用归并排序思想,从较大的开始排。对于两个数组每次选取较大的值,因此需要使用两个同时向前遍历的双指针。
具体做法
step 1:使用三个指针,i指向数组A的最大元素,j指向数组B的最大元素,k指向数组A空间的结尾处。
step 2:从两个数组最大的元素开始遍历,直到某一个结束,每次取出较大的一个值放入数组A空间的最后,然后指针一次往前。
step 3:如果数组B先遍历结束,数组A前半部分已经存在了,不用管;但是如果数组A先遍历结束,则需要把数组B剩余的前半部分依次逆序加入数组A前半部分,类似归并排序最后的步骤。
import java.util.*; public class Solution { public void merge(int A[], int m, int B[], int n) { //指向数组A的结尾 int i = m - 1; //指向数组B的结尾 int j = n - 1; //指向数组A空间的结尾处 int k = m + n - 1; //从两个数组最大的元素开始,直到某一个数组遍历完 while(i >= 0 && j >= 0){ //将较大的元素放到最后 if(A[i] > B[j]) A[k--] = A[i--]; else A[k--] = B[j--]; } //数组A遍历完了,数组B还有,则还需要添加到数组A前面 if(i < 0){ while(j >= 0) A[k--] = B[j--]; } //数组B遍历完了,数组A前面正好有,不用再添加 } }