221 最大正方形
我的解法如下
class Solution { public int maximalSquare(char[][] matrix) { int[][] dp = new int[matrix.length][matrix[0].length]; //x,y代表xy为右上角的最大正方形的边长 int max = 0; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { int c = matrix[i][j]-48; if (i == 0 || j == 0 || c == 0 || dp[i - 1][j - 1] == 0){ dp[i][j] = c; }else { int k = dp[i - 1][j - 1]; int s = 1; for (; s <=k; s++) { if (matrix[i-s][j] != 49 || matrix[i][j-s] != 49){ break; } } dp[i][j] = s; } max = Math.max(dp[i][j],max); } } return max*max; } }
但是官方给的dp解法复杂度要低很多，思路如下
3 无重复字符串的最长子串
hash表应该也是O(n)的复杂度
public static int lengthOfLongestSubstring(String s) { if (s.length() == 0)return 0; char[] str = s.toCharArray(); Map<Character,Integer> map = new HashMap<>(); map.put(str[0],0); int start = 0; int end = 0; int max = 1; for (int i = 1; i < str.length; i++) { char k = str[i]; Integer p = map.get(k); if (p != null && p >= start){ start = p+1; } end++; max = Math.max(max,end-start+1); map.put(k,i); } return max; }
480滑动窗口中位数
这题因为数据溢出导致我错了5次。。。 用的双堆
int[] ko ; public double[] medianSlidingWindow(int[] nums, int k) { if (nums.length == 0){ return new double[]{}; } double[] result = new double[nums.length-k+1]; if (k == 1){ for (int i = 0; i < nums.length; i++) { result[i] = (double)nums[i]; } return result; } ko =nums; PriorityQueue<Integer> small = new PriorityQueue<>((k1,k2)->nums[k1]>nums[k2]?1:-1); PriorityQueue<Integer> big = new PriorityQueue<>((k1,k2)->nums[k2]>nums[k1]?1:-1); for (int i = 0; i < k; i++) { if ( (i&1) == 0){ big.offer(i); }else { small.offer(i); } } avt(big,small); result[0] = getAv(big,small,nums); int s = 0; for (int i = k; i < nums.length; i++) { small.remove(s);big.remove(s); big.offer(i); avt(big,small); s++; double av = getAv(big, small, nums); result[s] = av; } return result; } public double getAv(PriorityQueue<Integer> big ,PriorityQueue<Integer> small,int[] nums){ if (big.size() == small.size()){ long s1 = nums[big.peek()]; long s2 = nums[small.peek()]; if (s1 == s2){ return (double) s1; }else { long s = s1+s2; return (double) s/2; } }else { return (double) nums[big.peek()]; } } public void avt(PriorityQueue<Integer> big ,PriorityQueue<Integer> small){ while (big.size()-small.size()>1){ small.offer(big.poll()); } while (ko[big.peek()]>ko[small.peek()]){ Integer poll = big.poll(); Integer poll1 = small.poll(); big.offer(poll1); small.offer(poll); } }
6. Z字变换。个人感觉描述为N字变换更准确一些
public String convert(String s, int numRows) { if (numRows == 1){ return s; } StringBuilder[] sb = new StringBuilder[numRows]; for (int i = 0; i < numRows; i++) { sb[i] = new StringBuilder(); } boolean flag = true; int k = 0; for (int j = 0; j < numRows && k<s.length(); j++) { int ind = flag?j:numRows-j-1; StringBuilder tsb = sb[ind]; tsb.append(s.charAt(k++)); if (j == numRows-1){ j = 0; flag =!flag; } } String res = ""; for (StringBuilder builder : sb) { res+=builder.toString(); } return res; }
54 螺旋矩阵
public List<Integer> spiralOrder(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; List<Integer> result = new ArrayList<>(); if (matrix.length == 0){ return result; } boolean[][] visited = new boolean[m][n]; int[][] forward = {{0,1},{1,0},{0,-1},{-1,0}}; int t = 1,total = m*n,x = 0,y = 0; result.add(matrix[0][0]); visited[0][0] = true; while (t<total){ for (int i = 0; i < forward.length; i++) { int[] fow = forward[i]; while (true){ int x1 = x+fow[0],y1 = y+fow[1]; if ( x1<m && x1 >=0 && y1 >=0 && y1 <n && !visited[x1][y1]){ x = x1;y = y1; result.add(matrix[x1][y1]); visited[x1][y1] = true; t++; }else { break; } } } } return result; }
46 全排列问题
int[] tpNums; List<Integer> res; List<List<Integer>> result; Set<Integer> pre; int deep = 0; public List<List<Integer>> permute(int[] nums) { tpNums = nums; res = new ArrayList<>(); result = new ArrayList<>(); pre = new HashSet<>(); dfs(); return result; } public void dfs(){ if (deep == tpNums.length){ result.add(new ArrayList<>(res)); return; } for (int i = 0; i < tpNums.length; i++) { int k = tpNums[i]; if (!pre.contains(k)){ pre.add(k); res.add(k); deep++; dfs(); deep--; res.remove(res.size()-1); pre.remove(k); } } }
209 长度最小的子数组
public int minSubArrayLen(int target, int[] nums) { int start = 0; int total = nums[0]; int min = Integer.MAX_VALUE; if (total>=target){ return 1; } for (int i = 1; i < nums.length; i++) { int k = nums[i]; total+=k; if (total >= target){ while (total-nums[start]>=target){ total-=nums[start++]; } min = Math.min(min,i-start); } } return min == Integer.MAX_VALUE?0: min+1; }
495 提莫攻击
个人觉得AD现状 差不多都活不过两三秒
public static int findPoisonedDuration(int[] timeSeries, int duration) { if(timeSeries.length == 0){ return 0; } int pre = duration; for (int i = 1; i < timeSeries.length; i++) { int x = timeSeries[i]; int y = timeSeries[i-1]; int s = x-y > duration? pre+duration:pre+duration-(duration-(x-y)); pre = s; } return pre; }