Leetcode 热门百题斩(第二天)

介绍

针对leetcode的热门一百题，解决大多数实习生面试的基本算法题。通过我自己的思路和多种方法，供大家参考。 

1.两数之和（题号：1)

方法一 

最先想到的就是两个for去遍历匹配。

class Solution {public int[] twoSum(int[] nums, int target) {for(int i = 0; i < nums.length; i++)for(int j = i + 1; j < nums.length; j++) {if(nums[i] + nums[j] == target) {return new int[] {i, j};}}return null;}
}

效率低下。

尝试其他方法。

 方法二

 使用Hash表进行匹配。也是先进行一次遍历，任何直接使用containKey匹配符合条件的值。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> numMap = new HashMap<>();//在为map赋值的时候顺便进行判断//判断当前map中是否存在其他key2可以得到当前key1相加等于targetfor(int i = 0; i < nums.length; i++) {if(numMap.containsKey(target - nums[i])) {//存在直接返回数据即可，此时是没有包含本身值 + 本身值是否=targetreturn new int[] {i, numMap.get(target - nums[i])};}numMap.put(nums[i], i);}return new int[2];}
}

效率马上就高了。

2. 字符异位词分组（题号：49）

方法一(暴力法，超时)

创建标记数组（标记数组是否被使用）,通过二次遍历，将符合添加的数据存储到一个list中，最终返回数据。 

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//创建一个标记数组int[] sign = new int[strs.length];List<List<String>> result = new LinkedList<>();//遍历列表并将重排序后相同的字符串存放在一个list中for(int i = 0; i < strs.length; i++) {//直接跳过if(sign[i] == 1) {continue;}//创建异位listList<String> tempList = new LinkedList<>();tempList.add(strs[i]);//对当前的字符串进行重排序char[] firstArray = strs[i].toCharArray();//直接对引用数组进行排序Arrays.sort(firstArray);String firstSortTemp = new String(firstArray);//将当前字符串标记为已使用(0为未使用,1为已使用)sign[i] = 1;for(int j = i + 1; j < strs.length; j++) {//对后续的字符串进行重排序if(sign[j] == 1) {//直接跳过continue;}char[] secondArray = strs[j].toCharArray();Arrays.sort(secondArray);String secondSortTemp = new String(secondArray);if(firstSortTemp.equals(secondSortTemp)) {//符合条件放入list中tempList.add(strs[j]);//标记为已使用sign[j] = 1;}}result.add(tempList);}return result;}
}

超时。

 方法二（使用hash表进行匹配）

使用hash表，对每个字符串重新排序，key存储排序后的字符串，value存储的就是符合异位的字符串的集合,最终返回values的集合。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//使用hash表进行匹配，key存储排序后的字符串,vlaue存储的就是异位字符串的list //(有点类似插入排序， 将对应的字符串存储到对应的键值对上)Map<String, List<String>> resultMap = new HashMap<>();for(int i = 0; i < strs.length; i++) {char[] tempStr = strs[i].toCharArray();Arrays.sort(tempStr);//排序好的字符串String sortTemp = new String(tempStr);List<String> tempList = resultMap.getOrDefault(sortTemp, new LinkedList<String>());//插入自己,并修改对应listtempList.add(strs[i]);resultMap.put(sortTemp, tempList);}//直接返回value集合return new LinkedList<List<String>>(resultMap.values());}
}

通过。

3.最长连续序列（题号：128）

最开始的时候题目要求将时间复杂度控制在O(N)，就没有想到使用双重循环（主要是怕超时）。

主要的思路就是使用set去重，然后遍历，从每个连续序列的排头进行遍历判断，求出最长的序列长度。（要注意的就是，去除多余循环的次数，防超时）

class Solution {public int longestConsecutive(int[] nums) {//使用HashSet去重Set<Integer> set = new HashSet<Integer>();for(int i = 0; i < nums.length; i++) {set.add(nums[i]);}int maxSize = 0;for(int i = 0; i < nums.length; i++) {//判断当前数值是否为排头，如果是排头就将长度设置为1，反之直接跳过int currentSize = 0;int tempNum = nums[i];//判断是否存在前值，如果存在直接跳过，防止超时if(!set.contains(tempNum - 1)) {//不存在，就说明是排头currentSize = 1;//循环判断后续长度while(set.contains(tempNum + 1)) {currentSize++;tempNum++;}maxSize = Math.max(currentSize, maxSize);}}return maxSize;}
}

 执行通过。

4.移动零（题号：283）

第一时间想到的是使用双指针进行数值的移动，当时涉及到大量的移动操作，效率非常低下，因此直接新建一个数组进行操作。

class Solution {public void moveZeroes(int[] nums) {int[] result = new int[nums.length];int point = 0;for(int i = 0; i < nums.length; i++) if(nums[i] != 0) result[point++] = nums[i];for(int i = 0; i < nums.length; i++) nums[i] = result[i];}
}

 运行通过。