顺丰01. 顺丰鄂州枢纽运转中心环线检测
DFS&判环
class Solution {public boolean hasCycle(String graph) {int[] inDegree = new int[105];Arrays.fill(inDegree,-1);HashSet<Integer>[] adj = new HashSet[105];for (int i = 0; i < 105; i++) {adj[i] = new HashSet<>();}String s[] = graph.split(",");for (String str : s) {String[] split = str.split("->");int start = Integer.parseInt(split[0]);int end = Integer.parseInt(split[1]);// 填充入度信息if(inDegree[end] == -1){inDegree[end] = 1;}else{inDegree[end]++;}if(inDegree[start] == -1){inDegree[start] = 0;}// 填充边信息adj[start].add(end);}Queue<Integer> queue = new LinkedList<>();// 将入度为0的点放入队列// 计算节点数量int num = 0;for (int i = 0; i < inDegree.length; i++) {if(inDegree[i] == 0){queue.add(i);}if(inDegree[i] != -1){num++;}}//记录出队的节点数量int cnt = 0;while (!queue.isEmpty()){Integer poll = queue.poll();cnt++;for (Integer successor : adj[poll]) {inDegree[successor]--;if(inDegree[successor] == 0){queue.add(successor);}}}// cnt = num 无环 cnt != num 有环return cnt == num ? false : true; }}
顺丰02. 小哥派件装载问题
0-1背包
class Solution {public int minRemainingSpace(int[] N, int V) {int n = N.length;int[] dp = new int[V + 1];for (int j = V; j >= N[0] ; j--) {dp[j] = N[0];}for (int i = 1; i < n; i++) {for (int j = V; j >= N[i]; j--) {dp[j] = Math.max(dp[j], dp[j - N[i]] + N[i]);}}return V - dp[V];}}
顺丰03.求最长递增子串
class Solution {public int findMaxCI(int[] nums) {int max = 0;int cnt = 0;for (int i = 1; i < nums.length; i++) {if(nums[i] > nums[i-1]){cnt++;max = Math.max(cnt, max);}else{cnt = 0;}}return max + 1;}}
顺丰05. 慧眼神瞳
并查集
int[] p;public int find(int x){if(x == p[x]){return x;}return p[x] = find(p[x]);}public void union(int x, int y){if(find(x) == find(y)){return;}p[find(x)] = find(y);}public boolean isCompliance(int[][] distance, int n) {p = new int[distance.length + 1];for (int i = 1; i <= distance.length; i++) {p[i] = i;}for (int i = 0; i < distance.length; i++) {for (int j = 0; j < distance[0].length; j++) {int curCamera = i+1; // 当前摄像头编号int otherCamera = j + 1;// 相连摄像头编号if(curCamera == otherCamera){continue;}if(distance[i][j] <= 2){union(curCamera, otherCamera);}}}HashSet<Integer> set = new HashSet<>();for (int i : p) {set.add(find(i));}return set.size() - 1 <= n; // 因为 0 一直存在并查集中所以需要 -1}
