之前一直看重面试中的算法，好像有些不太重视日常的的算法能力积累，所以从2024.7.14我要重拾学习算法的初心，每日不多，在日常常见算法巩固的同时每天再把leetcode的每日一题做了即可，在此记录一下。坚持就是胜利
不定期更新。
24.07.14. 保持城市天际线 链接
public int maxIncreaseKeepingSkyline (int [][] grid) { int n = grid.length; int [] colmax = new int [n]; int [] rowmax = new int [n]; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < n; j++) { rowmax[i] = Math.max(rowmax[i], grid[i][j]); colmax[j] = Math.max(colmax[j], grid[i][j]); } } int ans = 0 ; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < n; j++) { ans+=Math.min(rowmax[i],colmax[j])-grid[i][j]; } } return ans; }
24.07.15. 账户合并 链接
class Solution { public static int MAXN=10001 ; public static int [] father=new int [MAXN]; public static int emailsCount; public static void build () { for (int i=0 ;i<=emailsCount;i++){ father[i]=i; } } public static int find (int i) { if (father[i]!=i){ father[i]=find(father[i]); } return father[i]; } public static boolean isSameSet (int x, int y) { return find(x) == find(y); } public static void union (int x, int y) { father[find(x)] = find(y); } public List<List<String>> accountsMerge (List<List<String>> accounts) { Map<String,Integer> emailToIndex=new HashMap <String,Integer>(); Map<String,String> emailToName=new HashMap <String,String>(); emailsCount=0 ; for (List<String> account:accounts){ String name=account.get(0 ); int size=account.size(); for (int i=1 ;i<size;i++){ String email=account.get(i); if (!emailToIndex.containsKey(email)){ emailToIndex.put(email,emailsCount++); emailToName.put(email,name); } } } build(); for (List<String> account:accounts){ String firstEmail=account.get(1 ); int firstIndex=emailToIndex.get(firstEmail); int size=account.size(); for (int i=2 ;i<size;i++){ String nextEmail=account.get(i); int nextIndex=emailToIndex.get(nextEmail); union(firstIndex,nextIndex); } } Map<Integer, List<String>> indexToEmails = new HashMap <Integer, List<String>>(); for (String email : emailToIndex.keySet()) { int index = find(emailToIndex.get(email)); List<String> account = indexToEmails.getOrDefault(index, new ArrayList <String>()); account.add(email); indexToEmails.put(index, account); } List<List<String>> merged = new ArrayList <List<String>>(); for (List<String> emails : indexToEmails.values()) { Collections.sort(emails); String name = emailToName.get(emails.get(0 )); List<String> account = new ArrayList <String>(); account.add(name); account.addAll(emails); merged.add(account); } return merged; } }
24.07.16. 找到两个数组中的公共元素 链接
public int [] findIntersectionValues(int [] nums1, int [] nums2) { HashSet<Integer> s1 = new HashSet <>(); for (int x : nums1) { s1.add(x); } HashSet<Integer> s2 = new HashSet <>(); for (int x : nums2) { s2.add(x); } int [] res = new int [2 ]; for (int x : nums1) { if (s2.contains(x)) { res[0 ]++; } } for (int x : nums2) { if (s1.contains(x)) { res[1 ]++; } } return res; }
24.07.17.关闭分部的可行集合数目 链接
public int numberOfSets (int n, int maxDistance, int [][] roads) { int [][] g = new int [n][n]; for (int [] row : g) { Arrays.fill(row, Integer.MAX_VALUE / 2 ); } for (int [] e : roads) { int x = e[0 ]; int y = e[1 ]; int wt = e[2 ]; g[x][y] = Math.min(g[x][y], wt); g[y][x] = Math.min(g[y][x], wt); } int ans = 0 ; int [][] f = new int [n][n]; next: for (int s = 0 ; s < (1 << n); s++) { for (int i = 0 ; i < n; i++) { if ((s >> i & 1 ) == 1 ) { System.arraycopy(g[i], 0 , f[i], 0 , n); } } for (int k = 0 ; k < n; k++) { if ((s >> k & 1 ) == 0 ) continue ; for (int i = 0 ; i < n; i++) { if ((s >> i & 1 ) == 0 ) continue ; for (int j = 0 ; j < n; j++) { f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]); } } } for (int i = 0 ; i < n; i++) { if ((s >> i & 1 ) == 0 ) continue ; for (int j = 0 ; j < i; j++) { if ((s >> j & 1 ) == 1 && f[i][j] > maxDistance) { continue next; } } } ans++; } return ans; }
24.07.18.访问消失节点的最少时间 链接
public int [] minimumTime(int n, int [][] edges, int [] disappear) { List<int []>[] g = new ArrayList [n]; Arrays.setAll(g, i -> new ArrayList <>()); for (int [] e : edges) { int x = e[0 ]; int y = e[1 ]; int wt = e[2 ]; g[x].add(new int []{y, wt}); g[y].add(new int []{x, wt}); } int [] dis = new int [n]; Arrays.fill(dis, -1 ); dis[0 ] = 0 ; PriorityQueue<int []> pq = new PriorityQueue <>((a, b) -> (a[0 ] - b[0 ])); pq.offer(new int []{0 , 0 }); while (!pq.isEmpty()){ int [] p=pq.poll(); int dx=p[0 ]; int x=p[1 ]; if (dx>dis[x]){ continue ; } for (int [] e : g[x]) { int y = e[0 ]; int newDis = dx + e[1 ]; if (newDis < disappear[y] && (dis[y] < 0 || newDis < dis[y])) { dis[y] = newDis; pq.offer(new int []{newDis, y}); } } } return dis; }
24.07.19.得到更多分数的最少关卡数目 链接
public int minimumLevels (int [] possible) { int n = possible.length; int tot = 0 ; for (int x : possible) { tot += x == 1 ? 1 : -1 ; } int pre=0 ; for (int i=0 ;i<n-1 ;i++){ pre+=possible[i]==1 ?1 :-1 ; if (2 *pre>tot){ return i+1 ; } } return -1 ; }
24.07.20.将石头分散到网格图的最少移动次数 链接
public int minimumMoves (int [][] grid) { return dfs(grid, 0 , 0 ); } private int dfs (int [][] grid, int x, int y) { if (x >= 3 ) { return 0 ; } if (y >= 3 ) { return dfs(grid, x + 1 , 0 ); } if (grid[x][y] != 0 ) { return dfs(grid, x, y + 1 ); } int res = Integer.MAX_VALUE; for (int i = 0 ; i < 3 ; i++) { for (int j = 0 ; j < 3 ; j++) { if (i == x && j == y) { continue ; } if (grid[i][j] <= 1 ) { continue ; } grid[i][j] -= 1 ; res = Math.min(res, dfs(grid, x, y + 1 ) + Math.abs(i - x) + Math.abs(j - y)); grid[i][j] += 1 ; } } return res; }
24.07.21.删除一次得到子数组最大和 链接
public int maximumSum (int [] arr) { int n=arr.length; int [][] dp=new int [n][2 ]; dp[0 ][0 ]=arr[0 ]; dp[0 ][1 ]=0 ; int ans=arr[0 ]; for (int i=1 ;i<n;i++){ dp[i][0 ]=Math.max(dp[i-1 ][0 ],0 )+arr[i]; dp[i][1 ]=Math.max(dp[i-1 ][1 ]+arr[i],dp[i-1 ][0 ]); ans = Math.max(ans,Math.max(dp[i][0 ],dp[i][1 ])); } return ans; }
24.07.22.引爆最多的炸弹 链接
public int maximumDetonation (int [][] bombs) { int n=bombs.length; Map<Integer,List<Integer>> edges=new HashMap <>(); for (int i=0 ;i<n;i++){ for (int j=0 ;j<n;j++){ if (i!=j&&isConnected(bombs,i,j)){ edges.putIfAbsent(i,new ArrayList <Integer>()); edges.get(i).add(j); } } } int res=0 ; for (int i=0 ;i<n;i++){ boolean [] visited =new boolean [n]; int cnt=1 ; int [] queue=new int [n]; int l=0 ,r=0 ; queue[r++]=i; visited[i]=true ; while (l<r){ int cdix = queue[l++]; for (int ndix:edges.getOrDefault(cdix,new ArrayList <>())){ if (visited[ndix]){ continue ; } ++cnt; queue[r++]=ndix; visited[ndix]=true ; } } res=Math.max(cnt,res); } return res; } public boolean isConnected (int [][] bombs, int u, int v) { long dx = bombs[u][0 ] - bombs[v][0 ]; long dy = bombs[u][1 ] - bombs[v][1 ]; return (long ) bombs[u][2 ] * bombs[u][2 ] >= dx * dx + dy * dy; }
24.07.23.求出所有子序列的能量和 链接
private Map<Long, Integer> f = new HashMap <>(); private final int mod = (int ) 1e9 + 7 ; private int [] nums; public int sumOfPowers (int [] nums, int k) { Arrays.sort(nums); this .nums = nums; return dfs(0 , nums.length, k, Integer.MAX_VALUE); } private int dfs (int i, int j, int k, int mi) { if (i >= nums.length) { return k == 0 ? mi : 0 ; } if (nums.length - i < k) { return 0 ; } long key = (1L * mi) << 18 | (i << 12 ) | (j << 6 ) | k; if (f.containsKey(key)) { return f.get(key); } int ans = dfs(i + 1 , j, k, mi); if (j == nums.length) { ans += dfs(i + 1 , i, k - 1 , mi); } else { ans += dfs(i + 1 , i, k - 1 , Math.min(mi, nums[i] - nums[j])); } ans %= mod; f.put(key, ans); return ans; }
24.07.24.重新放置石块 链接
public List<Integer> relocateMarbles (int [] nums, int [] moveFrom, int [] moveTo) { List<Integer> ans = new ArrayList <Integer>(); Map<Integer, Boolean> mp = new HashMap <Integer, Boolean>(); for (int i = 0 ; i < nums.length; i++) { mp.put(nums[i], true ); } for (int i = 0 ; i < moveFrom.length; i++) { mp.remove(moveFrom[i]); mp.put(moveTo[i], true ); } for (Map.Entry<Integer, Boolean> entry : mp.entrySet()) { ans.add(entry.getKey()); } Collections.sort(ans); return ans; }
24.07.25.生成特殊数字的最少操作 链接
public int minimumOperations (String num) { int n = num.length(); boolean find0 = false , find5 = false ; for (int i = n - 1 ; i >= 0 ; --i) { if (num.charAt(i) == '0' || num.charAt(i) == '5' ) { if (find0) { return n - i - 2 ; } if (num.charAt(i) == '0' ) { find0 = true ; } else { find5 = true ; } } else if (num.charAt(i) == '2' || num.charAt(i) == '7' ) { if (find5) { return n - i - 2 ; } } } if (find0) { return n - 1 ; } return n; }
24.07.26.找出分区值 链接
public int findValueOfPartition (int [] nums) { Arrays.sort(nums); int res = Integer.MAX_VALUE; for (int i = 1 ; i < nums.length; i++) { res = Math.min(res, nums[i] - nums[i - 1 ]); } return res; }
24.07.27.满足距离约束且字典序最小的字符串 链接
public String getSmallestString (String s, int k) { char [] ans = s.toCharArray(); for (int i = 0 ; i < s.length(); ++i) { int dis = Math.min(s.charAt(i) - 'a' , 'z' - s.charAt(i) + 1 ); if (dis <= k) { ans[i] = 'a' ; k -= dis; } else { ans[i] -= k; break ; } } return new String (ans); }
24.07.28.掉落的方块 链接
public List<Integer> fallingSquares (int [][] positions) { int n = positions.length; List<Integer> heights = new ArrayList <Integer>(); for (int i = 0 ; i < n; i++) { int left1 = positions[i][0 ], right1 = positions[i][0 ] + positions[i][1 ] - 1 ; int height = positions[i][1 ]; for (int j = 0 ; j < i; j++) { int left2 = positions[j][0 ], right2 = positions[j][0 ] + positions[j][1 ] - 1 ; if (right1 >= left2 && right2 >= left1) { height = Math.max(height, heights.get(j) + positions[i][1 ]); } } heights.add(height); } for (int i = 1 ; i < n; i++) { heights.set(i, Math.max(heights.get(i), heights.get(i - 1 ))); } return heights; }
24.07.29.棒球比赛 链接
public int calPoints (String[] operations) { Stack<String> stack=new Stack <>(); for (int i = 0 ; i < operations.length; i++) { if (operations[i].equals("D" )){ stack.push(String.valueOf(Integer.parseInt(stack.peek())*2 )); }else if (operations[i].equals("C" )){ stack.pop(); } else if (operations[i].equals("+" )) { String pop1 = stack.pop(); String pop2=stack.pop(); stack.push(pop2); stack.push(pop1); stack.push(String.valueOf(Integer.parseInt(pop1)+Integer.parseInt(pop2))); }else { stack.push(operations[i]); } } int count=0 ; for (String s : stack) { count+=Integer.parseInt(s); } return count; }
24.07.30.双模幂运算 链接
public List<Integer> getGoodIndices (int [][] variables, int target) { List<Integer> ans=new ArrayList <>(); for (int i=0 ;i<variables.length;i++){ int [] v=variables[i]; if (pow(pow(v[0 ],v[1 ],10 ),v[2 ],v[3 ])==target){ ans.add(i); } } return ans; } public int pow (int x,int n,int mod) { int res=1 ; while (n>0 ){ if (n%2 >0 ){ res=res*x%mod; } x=x*x%mod; n/=2 ; } return res; }
24.07.31.覆盖所有点的最少矩形数目 链接
public int minRectanglesToCoverPoints (int [][] points, int w) { Arrays.sort(points,(a,b)->a[0 ]-b[0 ]); int ans=0 ; int x2=-1 ; for (int [] p:points){ if (p[0 ]>x2){ ans++; x2=p[0 ]+w; } } return ans; }
24.08.01.心算挑战 链接
public int maxmiumScore (int [] cards, int cnt) { Arrays.sort(cards); int s=0 ; int n=cards.length; for (int i=n-cnt;i<n;i++){ s+=cards[i]; } if (s%2 ==0 ){ return s; } int x=cards[n-cnt]; int ans= replaceSum(cards,cnt,s,x); for (int i=n-cnt+1 ;i<n;i++){ if (cards[i]%2 !=x%2 ){ ans = Math.max(ans, replaceSum(cards, cnt, s, cards[i])); break ; } } return ans; } private int replaceSum (int [] cards, int cnt, int s, int x) { for (int i = cards.length - cnt - 1 ; i >= 0 ; i--) { if (cards[i] % 2 != x % 2 ) { return s - x + cards[i]; } } return 0 ; }
24.08.02.直角三角形 链接
public long numberOfRightTriangles (int [][] grid) { int n=grid[0 ].length; int [] colSum = new int [n]; Arrays.fill(colSum, -1 ); for (int [] row : grid) { for (int j = 0 ; j < n; j++) { colSum[j] += row[j]; } } long ans=0 ; for (int [] row:grid){ int rowSum=-1 ; for (int x:row){ rowSum+=x; } for (int j=0 ;j<row.length;j++){ if (row[j]==1 ){ ans+=rowSum*colSum[j]; } } } return ans; }
24.08.03.正方形中的最多点数 链接
public int maxPointsInsideSquare (int [][] points, String s) { int [] min1 = new int [26 ]; Arrays.fill(min1, 1000000001 ); int min2 = 1000000001 , n = s.length(); for (int i = 0 ; i < n; ++i) { int x = points[i][0 ], y = points[i][1 ], j = s.charAt(i) - 'a' ; int d = Math.max(Math.abs(x), Math.abs(y)); if (d < min1[j]) { min2 = Math.min(min2, min1[j]); min1[j] = d; } else if (d < min2) { min2 = d; } } int res = 0 ; for (int d : min1) { if (d < min2) { ++res; } } return res; }
24.08.04.另一棵树的子树 链接
public boolean isSubtree (TreeNode s, TreeNode t) { if (t == null ) return true ; if (s == null ) return false ; return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t); } public boolean isSameTree (TreeNode s, TreeNode t) { if (s == null && t == null ) return true ; if (s == null || t == null ) return false ; if (s.val != t.val) return false ; return isSameTree(s.left, t.left) && isSameTree(s.right, t.right); }
24.08.05.不含连续1的非负整数 链接
char s[];int dp[][];public int findIntegers (int n) { s = Integer.toBinaryString(n).toCharArray(); var m = s.length; dp = new int [m][2 ]; for (var i = 0 ; i < m; i++) Arrays.fill(dp[i], -1 ); return f(0 , false , true ); } int f (int i, boolean pre1, boolean isLimit) { if (i == s.length) return 1 ; if (!isLimit && dp[i][pre1 ? 1 : 0 ] >= 0 ) return dp[i][pre1 ? 1 : 0 ]; var up = isLimit ? s[i] - '0' : 1 ; var res = f(i + 1 , false , isLimit && up == 0 ); if (!pre1 && up == 1 ) res += f(i + 1 , true , isLimit); if (!isLimit) dp[i][pre1 ? 1 : 0 ] = res; return res; }
24.08.06.找出所有稳定的二进制数组 I public int numberOfStableArrays (int zero, int one, int limit) { final long MOD = 1000000007 ; long [][][] dp = new long [zero + 1 ][one + 1 ][2 ]; for (int i = 0 ; i <= Math.min(zero, limit); i++) { dp[i][0 ][0 ] = 1 ; } for (int j = 0 ; j <= Math.min(one, limit); j++) { dp[0 ][j][1 ] = 1 ; } for (int i = 1 ; i <= zero; i++) { for (int j = 1 ; j <= one; j++) { if (i > limit) { dp[i][j][0 ] = dp[i - 1 ][j][0 ] + dp[i - 1 ][j][1 ] - dp[i - limit - 1 ][j][1 ]; } else { dp[i][j][0 ] = dp[i - 1 ][j][0 ] + dp[i - 1 ][j][1 ]; } dp[i][j][0 ] = (dp[i][j][0 ] % MOD + MOD) % MOD; if (j > limit) { dp[i][j][1 ] = dp[i][j - 1 ][1 ] + dp[i][j - 1 ][0 ] - dp[i][j - limit - 1 ][0 ]; } else { dp[i][j][1 ] = dp[i][j - 1 ][1 ] + dp[i][j - 1 ][0 ]; } dp[i][j][1 ] = (dp[i][j][1 ] % MOD + MOD) % MOD; } } return (int ) ((dp[zero][one][0 ] + dp[zero][one][1 ]) % MOD); }
24.08.07.找出所有稳定的二进制数组 II static final int MOD = 1000000007 ; int [][][] memo; int limit; public int numberOfStableArrays (int zero, int one, int limit) { this .memo = new int [zero + 1 ][one + 1 ][2 ]; for (int i = 0 ; i <= zero; i++) { for (int j = 0 ; j <= one; j++) { Arrays.fill(memo[i][j], -1 ); } } this .limit = limit; return (dp(zero, one, 0 ) + dp(zero, one, 1 )) % MOD; } public int dp (int zero, int one, int lastBit) { if (zero == 0 ) { return (lastBit == 0 || one > limit) ? 0 : 1 ; } else if (one == 0 ) { return (lastBit == 1 || zero > limit) ? 0 : 1 ; } if (memo[zero][one][lastBit] == -1 ) { int res = 0 ; if (lastBit == 0 ) { res = (dp(zero - 1 , one, 0 ) + dp(zero - 1 , one, 1 ))% MOD; if (zero > limit) { res = (res - dp(zero - limit - 1 , one, 1 ) + MOD) % MOD; } } else { res = (dp(zero, one - 1 , 0 ) + dp(zero, one - 1 , 1 )) % MOD; if (one > limit) { res = (res - dp(zero, one - limit - 1 , 0 ) + MOD) % MOD; } } memo[zero][one][lastBit] = res % MOD; } return memo[zero][one][lastBit]; }
24.08.08.找出与数组相加的整数 I 24.08.09.找出与数组相加的整数 II 链接
public int minimumAddedInteger (int [] nums1, int [] nums2) { int m=nums1.length,n=nums2.length; Arrays.sort(nums1); Arrays.sort(nums2); for (int i:new int []{2 ,1 ,0 }){ int left=i+1 ,right=1 ; while (left<m&&right<n){ if (nums1[left]-nums2[right]==nums1[i] - nums2[0 ]){ ++right; } ++left; } if (right==n){ return nums2[0 ]-nums1[i]; } } return 0 ; }
24.08.10.找到Alice和Bob可以相遇的建筑 链接
class Solution { int [] zd; public int [] leftmostBuildingQueries(int [] heights, int [][] queries) { int n = heights.length; zd = new int [n * 4 ]; build(1 , n, 1 , heights); int m = queries.length; int [] ans = new int [m]; for (int i = 0 ; i < m; i++) { int a = queries[i][0 ]; int b = queries[i][1 ]; if (a > b) { int temp = a; a = b; b = temp; } if (a == b || heights[a] < heights[b]) { ans[i] = b; continue ; } ans[i] = query(b + 1 , heights[a], 1 , n, 1 ) - 1 ; } return ans; } public void build (int l, int r, int rt, int [] heights) { if (l == r) { zd[rt] = heights[l - 1 ]; return ; } int mid = (l + r) >> 1 ; build(l, mid, rt << 1 , heights); build(mid + 1 , r, rt << 1 | 1 , heights); zd[rt] = Math.max(zd[rt << 1 ], zd[rt << 1 | 1 ]); } public int query (int pos, int val, int l, int r, int rt) { if (val >= zd[rt]) { return 0 ; } if (l == r) { return l; } int mid = (l + r) >> 1 ; if (pos <= mid) { int res = query(pos, val, l, mid, rt << 1 ); if (res != 0 ) { return res; } } return query(pos, val, mid + 1 , r, rt << 1 | 1 ); } }
24.08.11.不相交的线 链接
public int maxUncrossedLines (int [] nums1, int [] nums2) { int n=nums1.length; int m=nums2.length; int [][] dp=new int [n+1 ][m+1 ]; for (int i=1 ;i<=n;i++){ for (int j=1 ;j<=m;j++){ if (nums1[i-1 ]==nums2[j-1 ]){ dp[i][j]=dp[i-1 ][j-1 ]+1 ; }else { dp[i][j]=Math.max(dp[i-1 ][j],dp[i][j-1 ]); } } } return dp[n][m]; }
24.08.12.实现一个魔法字典 链接
class MagicDictionary { int N = 100 * 100 , M = 26 , idx = 0 ; int [][] tr = new int [N][M]; boolean [] isEnd = new boolean [N * M]; void add (String s) { int p = 0 ; for (int i = 0 ; i < s.length(); i++) { int u = s.charAt(i) - 'a' ; if (tr[p][u] == 0 ) tr[p][u] = ++idx; p = tr[p][u]; } isEnd[p] = true ; } boolean query (String s, int idx, int p, int limit) { if (limit < 0 ) return false ; if (idx == s.length()) return isEnd[p] && limit == 0 ; int u = s.charAt(idx) - 'a' ; for (int i = 0 ; i < 26 ; i++) { if (tr[p][i] == 0 ) continue ; if (query(s, idx + 1 , tr[p][i], i == u ? limit : limit - 1 )) return true ; } return false ; } public void buildDict (String[] ss) { for (String s : ss) add(s); } public boolean search (String s) { return query(s, 0 , 0 , 1 ); } }
24.08.13.特殊数组I 链接
public boolean isArraySpecial (int [] nums) { if (nums.length==1 ){ return true ; } for (int i=1 ;i<nums.length;i++){ if ((nums[i]+nums[i-1 ])%2 ==0 ){ return false ; } } return true ; }
