三数之和
卡了俩月的双指针,微笑
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int len = nums.length; if(nums == null || len <3){ return res; } Arrays.sort(nums); for(int i = 0; i<len;i++){ if(nums[i]>0){ break; } if(i > 0 && nums[i] == nums[i-1]) continue; int l = i +1; int r = len-1; while(l<r){ int sum = nums[i] + nums[l] + nums[r]; if(sum==0){ res.add(Arrays.asList(nums[i], nums[l], nums[r])); while(l < r && nums[l] == nums[l+1]) { l++; } while(l< r && nums[r] == nums[r-1]){ r--; } l++; r--; }else if(sum < 0){ l++; }else if(sum > 0){ r--; } } } return res; } }
|
无重复的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
这道题很巧妙的使用了滑动窗口
其中保持end端不断的前进,start通过动态的查找进行判断最长的字串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int ans = 0; Map<Character,Integer> map = new HashMap<>(); for(int end = 0,start = 0; end<n ; end++){ char alpha = s.charAt(end); if(map.containsKey(alpha)){ start = Math.max(map.get(alpha),start); } ans = Math.max(ans,end-start+1); map.put(s.charAt(end),end+1); } return ans; } }
|
找到字符串中所有的异位词
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| import java.util.ArrayList; import java.util.Arrays; import java.util.List;
class Solution { public List<Integer> findAnagrams(String s, String p) { if (s.isEmpty() || p.isEmpty() || p.length() > s.length()) { return new ArrayList<>(); }
int sLen = s.length(); int pLen = p.length();
int[] arr = new int[128]; for (int i = 0; i < pLen; i++) { arr[p.charAt(i)]++; }
List<Integer> resultList = new ArrayList<>(); int[] matchArr = new int[128]; for (int i = 0; i < sLen; i++) { matchArr[s.charAt(i)]++;
if (i >= pLen - 1) { if (Arrays.equals(arr, matchArr)) { resultList.add((i + 1) - pLen); } matchArr[s.charAt((i + 1) - pLen)]--; } }
return resultList; } }
|
轮转数组
注意System.arraycopy()方法的用法。
1 2 3 4 5 6 7 8 9 10 11
| class Solution { public void rotate(int[] nums, int k) { int []ans = new int[nums.length]; for(int i=0;i<nums.length;i++){ int temp = 0; temp=(i+k)%nums.length; ans[(i + k) % nums.length] = nums[i]; } System.arraycopy(ans,0,nums,0,nums.length); } }
|
除自身以外的整数积
使用从左边遍历一遍,从右边遍历一遍,然后进行求积
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] l = new int[n]; int[] r = new int[n]; int[] res = new int [n]; l[0]=1; r[n-1]=1; res[0]=1; for(int i = 1;i<n;i++){ l[i]=l[i-1]*nums[i-1]; } for(int i = n-2;i>=0;i--){ r[i]=r[i+1]*nums[i+1]; } for(int i = 0;i<n;i++){ res[i]=r[i]*l[i]; } return res; } }
|
矩阵置零
通过设置两个标记位数组,第一遍遍历进行设置,第二遍遍历进行置零
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean [] row = new boolean[m]; boolean [] col = new boolean[n]; for(int i = 0; i<m; i++){ for(int j=0; j<n; j++){ if(matrix[i][j]==0){ row[i]=true; col[j]=true; } } } for(int i = 0; i<m; i++){ for(int j=0; j<n; j++){ if(row[i]==true||col[j]==true){ matrix[i][j]=0; } } } } }
|