byu_rself

LC.P797[所有可能的路径] 方法一：DFS1234567891011121314151617181920212223242526class Solution { int[][] graph; int n; List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); public List<List<Integer>> allPathsSourceTarget(int[][] graph) { this.graph = graph; this.n = graph.length; path.add(0); dfs(0); return ans; } private void dfs(int i) { if (i == n - 1) ...

LC.P1163[按字典序排在最后的子串] 方法一：双指针1234567891011121314151617181920class Solution { public String lastSubstring(String s) { int n = s.length(); int i = 0, j = 1, k = 0; while (j + k < n) { int d = s.charAt(i + k) - s.charAt(j + k); if (d == 0) { ++k; } else if (d < 0) { i = i + k + 1; k = 0; if (i >= j) j = i + 1; } else { ...

LC.P815[公交路线] 方法一：BFS12345678910111213141516171819202122232425262728293031323334353637class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) return 0; int n = routes.length; Map<Integer, Set<Integer>> map = new HashMap<>(); // 某个车站可以进入的路线 Deque<Integer> queue = new ArrayDeque<>(); Map<Integer, Integer> stepMap = new HashMap<>(); for (int i = ...

LC.P1105[填充书架] 方法一：动态规划(超时)12345678910111213141516171819202122class Solution { int[][] books; int shelfWidth; public int minHeightShelves(int[][] books, int shelfWidth) { this.books = books; this.shelfWidth = shelfWidth; return dfs(books.length - 1); } private int dfs(int i) { if (i < 0) return 0; int ans = Integer.MAX_VALUE, maxHeight = 0, width = 0; for (int j = i; j >= 0; --j) { width += books[j ...

LC.P1027[最长等差数列] 方法一：动态规划定义$f[i][j]$表示以$nums[i]$结尾且公差为$j$的等差数列的最大长度。初始时$f[i][j] = 1$，表示每个元素自身都是一个长度为$1$的等差数列。 由于公差可能为负数，且最大差值为 500 ，因此，可以将统一将公差加上 500，这样公差的范围就变成了 $[0 , 1000]$ 如果初始时 $f[i][j] = 0$，那么我们需要在最后返回答案时加上 $1$。 1234567891011121314class Solution { public int longestArithSeqLength(int[] nums) { int n = nums.length, ans = 0; int[][] f = new int[n][1001]; // f[i][j]表示以nums[i]结尾且公差为j的等差数列的最大长度 for (int i = 0; i < n; ++i) { for (in ...

RPC学习笔记与项目实战Guide哥RPC学习笔记 RPC简介什么是RPC？RPC（Remote Procedure Call） 即远程过程调用，通过名字我们就能看出 RPC 关注的是远程调用而非本地调用。 为什么要 RPC ？ 因为，两个不同的服务器上的服务提供的方法不在一个内存空间，所以，需要通过网络编程才能传递方法调用所需要的参数。并且，方法调用的结果也需要通过网络编程来接收。但是，如果我们自己手动网络编程来实现这个调用过程的话工作量是非常大的，因为，我们需要考虑底层传输方式（TCP 还是 UDP）、序列化方式等等方面。 RPC 能帮助我们做什么呢？ 简单来说，通过 RPC 可以帮助我们调用远程计算机上某个服务的方法，这个过程就像调用本地方法一样简单。并且，我们不需要了解底层网络编程的具体细节。 举个例子：两个不同的服务 A、B 部署在两台不同的机器上，服务 A 如果想要调用服务 B 中的某个方法的话就可以通过 RPC 来做。 一言蔽之：RPC 的出现就是为了让你调用远程方法像调用本地方法一样简单。 RPC原理RPC的核心功能由以下5个部分实现： 客户端（服务消费端）：调用远 ...

LC.P854[相似度为 K 的字符串] 方法一：BFS123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution { public int kSimilarity(String s1, String s2) { Deque<String> queue = new ArrayDeque<>(); Set<String> visited = new HashSet<>(); queue.offer(s1); visited.add(s1); int ans = 0; while (true) { for (int i = queue.size(); i > 0; --i) { String s = queue.poll(); ...

LC.P1723[完成所有工作的最短时间] 方法一：回溯+剪枝(超时)1234567891011121314151617181920212223242526272829303132class Solution { int[] jobs; int n, k; int[] sum; int ans = Integer.MAX_VALUE; public int minimumTimeRequired(int[] jobs, int k) { this.jobs = jobs; this.k = k; this.n = jobs.length; sum = new int[n]; dfs(0, 0); return ans; } /** * @param cur 当前处理到的工作 * @param max 当前的最大工作时间 */ private void dfs(int cur, int max)  ...

LC.P2413[最小偶倍数] 方法一：模拟12345class Solution { public int smallestEvenMultiple(int n) { return n % 2 == 0 ? n : 2 * n; }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$ 方法二：位运算12345class Solution { public int smallestEvenMultiple(int n) { return n << (n & 1); }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$

LC.P77[组合] 思路：回溯 + 剪枝 方法一：枚举下一个数选哪个123456789101112131415161718192021222324class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); int k; public List<List<Integer>> combine(int n, int k) { this.k = k; dfs(n); return ans; } private void dfs(int i) { int d = k - path.size(); // 还要选d个数 if (d == 0) { ans.add(new ArrayList<& ...