笔试、面试问题 秋招招聘汇总+避雷公司8.07更新+简历指导(已指导百人)
【2023秋招&提前批】互联网招聘信息最新汇总8月8日更新
23届联想面经分享: 秋招上岸
蔚来技术岗最全面经汇总
蔚来提前批 大数据 一面二面 7.24
【通关版】招银网络科技最详面经汇总!
衫川机器人
归纳 建树、建图之类 并查集 + Kruskal 此处是List<int[]>,使用了点-点-权重的建图方式,每一次只需要找到权重最小的,而且不在联通图中的即可
数节点染色计算总体权重 【2022-08-10】ZOOM秋招笔试两道编程题
建树 + dfs
此处使用邻接表的形式,节点node中存了该节点在数组中的编号,然后权重
树的 层序遍历,编码解码需要会 生活在树上 【2022-08-13】美团秋招笔试四道编程题
这一题直接dfs做就行
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 59 60 61 62 63 64 65 66 67 import java.util.*;public class LivingInTree { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); int [] nums = new int [n]; for (int i = 0 ; i < n; i++) { nums[i] = scanner.nextInt(); } dfs(nums, n, nums[0 ], 1 ); System.out.println(ans); } static int ans = 0 ; public static void dfs (int [] nums, int n, int sum, int k) { if (k * 2 + 1 > n) { ans = Math.max(ans, sum); return ; } if (k * 2 <= n) { dfs(nums, n, sum + nums[k * 2 - 1 ], k * 2 ); } if (k * 2 + 1 <= n) { dfs(nums, n, sum + nums[k * 2 ], k * 2 + 1 ); } } } public class Main { public static void main (String args[]) { Scanner cin = new Scanner (System.in); int n = Integer.parseInt(cin.nextLine()); String[] _nums = cin.nextLine().split(" " ); int [] nums = new int [n + 1 ]; for (int i = 1 ; i <= n; i++) nums[i] = Integer.parseInt(_nums[i - 1 ]); int ans = 0 ; Queue<Integer> q = new ArrayDeque <>(); q.offer(1 ); while (!q.isEmpty()) { int t = q.poll(); ans = Math.max(ans, nums[t]); if (2 * t <= n){ nums[2 * t] += nums[t]; q.offer(2 * t); } if (2 * t + 1 <= n) { nums[2 * t + 1 ] += nums[t]; q.offer(2 * t + 1 ); } } System.out.println(ans); } }
蔚来笔试题目
leetcode上面是直接给出根节点的,而这个的话,需要自己根据这个来建立一棵树,当然也是简单的。
首先数组 存上所有的节点,然后根据第三行建立连接就行了。此处根据第三行当然也可以变成数组+链表存储二叉树,但是这样肯定没有第一种方法来的方便。
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 59 60 61 62 63 64 import java.util.Scanner;public class TreeMaxSum { static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this .val = val; } } public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); TreeNode[] treeNodes = new TreeNode [n]; TreeNode root = null ; for (int i = 0 ; i < n; i++) { treeNodes[i] = new TreeNode (scanner.nextInt()); } for (int i = 0 ; i < n; i++) { int parentIndex = scanner.nextInt(); if (parentIndex == 0 ) { root = treeNodes[i]; } else { if (treeNodes[parentIndex-1 ].left == null ) { treeNodes[parentIndex-1 ].left = treeNodes[i]; } else { treeNodes[parentIndex-1 ].right = treeNodes[i]; } } } dfs(root); System.out.println(ans); } static int ans = Integer.MIN_VALUE; public static int dfs (TreeNode node) { if (node == null ) { return 0 ; } int leftGain = Math.max(dfs(node.left), 0 ); int rightGain = Math.max(dfs(node.right), 0 ); ans = Math.max(leftGain + rightGain + node.val, ans); return Math.max(leftGain + node.val, rightGain + node.val); } }
题目 0723科大讯飞 五个球队一次两两比赛,然后五个队伍的分数从高到底排序,去重后看看有多少种,然后判断题目给出的一个数据是否是在里面的。
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 import java.util.*;import java.util.stream.Collectors;public class TemplateLianBiao { public static Deque<int []> queue = new ArrayDeque <>(); public static void main (String[] args) { Scanner in = new Scanner (System.in); int a = in.nextInt(); int [] scores = new int [5 ]; for (int i = 0 ; i < 5 ; i++) { scores[i] = in.nextInt(); } Set<List<Integer>> set = new HashSet <>(); queue.offerLast(new int []{0 , 0 , 0 , 0 , 0 }); for (int i = 0 ; i < 5 ; i++) { for (int j = i+1 ; j < 5 ; j++) { int size = queue.size(); for (int k = 0 ; k < size; k++) { int [] temp = queue.pollFirst(); temp[i] += 3 ; temp[j] += 0 ; queue.offerLast(temp.clone()); temp[i] -= 3 ; temp[j] -= 0 ; temp[i] += 1 ; temp[j] += 1 ; queue.offerLast(temp.clone()); temp[i] -= 1 ; temp[j] -= 1 ; temp[i] += 0 ; temp[j] += 3 ; queue.offerLast(temp.clone()); } } } while (!queue.isEmpty()) { int [] temp = queue.pollFirst(); Arrays.sort(temp); for (int i = 0 ; i < 2 ; i++) { int temoInt = temp[i]; temp[i] = temp[4 -i]; temp[4 -i] = temoInt; } set.add(Arrays.asList(temp[0 ], temp[1 ], temp[2 ], temp[3 ], temp[4 ])); } System.out.print(a == set.size() ? "yes" : "no" ); System.out.print(set.contains(Arrays.asList(scores[0 ], scores[1 ], scores[2 ], scores[3 ], scores[4 ])) ? " yes" : " no" ); } }
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); String[] strs = scanner.nextLine().split("\\],\\[" ); strs[0 ] = strs[0 ].substring(2 , strs[0 ].length()); strs[n-1 ] = strs[n-1 ].substring(0 , strs[n-1 ].length()-2 ); int [][] g = new int [n][n]; for (int i = 0 ; i < n; i++) { g[i] = Arrays.stream(strs[i].split("," )).mapToInt(Integer::valueOf).toArray(); } for (int i = 0 ; i < n; i++) { System.out.println(Arrays.toString(g[i])); } for (int i = 0 ; i < n; i++) { if (g[i][0 ] == 0 ) { boolean [][] visited = new boolean [n][n]; visited[i][0 ] = true ; List<int []> list = new ArrayList <>(); list.add(new int []{i, 0 }); dfs(g, new int []{i, 0 }, list, visited); } if (g[n-1 ][0 ] == 0 ) { boolean [][] visited = new boolean [n][n]; visited[n-1 ][0 ] = true ; List<int []> list = new ArrayList <>(); list.add(new int []{n-1 , 0 }); dfs(g, new int []{n-1 , 0 }, list, visited); } } for (int i = 1 ; i < n; i++) { if (g[0 ][i] == 0 ) { boolean [][] visited = new boolean [n][n]; visited[0 ][i] = true ; List<int []> list = new ArrayList <>(); list.add(new int []{0 , i}); dfs(g, new int []{0 , i}, list, visited); } if (g[n-1 ][i] == 0 ) { boolean [][] visited = new boolean [n][n]; visited[n-1 ][i] = true ; List<int []> list = new ArrayList <>(); list.add(new int []{n-1 , i}); dfs(g, new int []{n-1 , i}, list, new boolean [n][n]); } } System.out.print("[" ); for (int i = 0 ; i < minPath.size()-1 ; i++) { int [] temp = minPath.get(i); System.out.print("(" + temp[0 ] + "," + temp[1 ] + ")," ); } System.out.print("(" + minPath.get(minPath.size()-1 )[0 ] + "," + minPath.get(minPath.size()-1 )[1 ] + ")" + "]" ); } static int n = 4 ; static int minPathCount = Integer.MAX_VALUE; static List<int []> minPath; static int [][] dir = new int [][]{{1 , 0 }, {-1 , 0 }, {0 , 1 }, {0 , -1 }}; public static void dfs (int [][] g, int [] curIndex, List<int []> path, boolean [][] visited) { int x = curIndex[0 ], y = curIndex[1 ]; if (g[x][y] == 8 ) { if (minPathCount > path.size()) { minPathCount = path.size(); minPath = new ArrayList <>(path); } return ; } if (path.size() > minPathCount) { return ; } for (int i = 0 ; i < n; i++) { int newX = x + dir[i][0 ], newY = y + dir[i][1 ]; if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY] && g[newX][newY] != 1 ) { visited[newX][newY] = true ; path.add(new int []{newX, newY}); dfs(g, new int []{newX, newY}, path, visited); visited[newX][newY] = false ; path.remove(path.size() - 1 ); } } } }
0810ZOOM 【2022-08-10】ZOOM秋招笔试两道编程题
数节点染色计算总体权重 题目
给你一棵树,树上每个节点要么是红色要么是黑色,根节点为1。每个节点的权重值为根节点到该节点路径上红色节点个数和蓝色节点个数的差的绝对值。求所有节点权重值之和。
输入 第一行输入n个节点 第二行为每个节点的颜色 接下来n-1行为a b节点之间有一条线
5 RBBRB 1 5 2 5 1 3 5 4
思路 考虑建树
但是,如果使用树节点,然后内部维护一个子节点的链表,这样的话建树有难度,因为①里面只给出了节点需要,根据序号找到该节点就稍微麻烦点;其次就是题目说的②ab之间有连线,也没说哪个是父亲节点。
如果只有问题①,那感觉好解决的,使用map,将序号和节点映射即可。
注意,这个题目建图,因为不知道这棵树的父亲节点是谁,是个无向图,然后dfs的时候考虑一下父亲节点不dfs就好了*,下面的小红书一对一,携程rgb,顺丰圣诞树都可以参考一下这个建树
所以本题目考虑,存图的方式,邻接矩阵:
1 题解用的是,节点node,然后node.next链接邻居节点,一开始插入的时候使用头插入(本节点的下一个插入)。(当作无向图的话,父亲节点也会被记录进去,所以等等dfs的时候需要有一个visit标记是否是父节点被访问过,或者说是否是该路径上的节点;没有尝试如果使用,节点中使用链表维护子节点的方法是不需要visited的 )
2 当然,我觉得使用数组+链表邻接矩阵的方法也是可以的
1和2的区别是1数组里面每一个第一个都是本节点,其余是相邻节xs点,而2里面数组里面的都是邻居节点
注意节点里面至少要有一个参数存放该节点是数组graph中的哪一个
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 import java.util.List;import java.util.Scanner;class ListNode { long val; ListNode next; public ListNode (long val, ListNode next) { this .val = val; this .next = next; } } public class TechGuide { public static void main (String[] args) { Scanner sc = new Scanner (System.in); int root = 0 ; int n = sc.nextInt(); System.out.println(n); int color[] = new int [n]; ListNode[] Graph = new ListNode [n]; for (int i = 0 ; i < n; i++) { Graph[i] = new ListNode (0 ,null ); } sc.nextLine(); String str = sc.nextLine(); System.out.println(str); for (int i = 0 ; i < n; i++) { if (str.charAt(i)=='R' ){ color[i] = 1 ; } } for (int i = 0 ; i < n-1 ; i++) { int u = sc.nextInt()-1 ; int v = sc.nextInt()-1 ; insert(u,v,Graph); } int visited[] = new int [n]; dfs(root,visited,0 ,0 ,color,Graph); long ans = 0 ; for (int i = 0 ; i < n; i++) { ans+=Graph[i].val; } System.out.println(ans); } public static void insert (int u,int v,ListNode[] G) { ListNode vNode = new ListNode (v,G[u].next); G[u].next = vNode; ListNode uNode = new ListNode (u,G[v].next); G[v].next = uNode; } public static void dfs (int root,int [] visited,int red,int blue,int color[],ListNode[] G) { visited[root] = 1 ; if (color[root]==1 ) red++; else blue++; G[root].val = Math.abs(red-blue); ListNode p = G[root].next; while (p!=null ){ if (visited[(int )p.val]!=1 ){ dfs((int )p.val,visited,red,blue,color,G); } p = p.next; } visited[root] = 0 ; } } package org.jcwang.zoom;import java.util.*;public class Main2 { private static class ListNode { long num; boolean isRed; public ListNode (long num, boolean isRed) { this .num = num; this .isRed = isRed; } } public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); List<ListNode>[] graph = new ArrayList [n]; for (int i = 0 ; i < n; i++) { graph[i] = new ArrayList <>(); } boolean [] color = new boolean [n]; String str = scanner.next(); for (int i = 0 ; i < n; i++) { color[i] = str.charAt(i) == 'R' ; } for (int i = 0 ; i < n-1 ; i++) { int a = scanner.nextInt() - 1 ; int b = scanner.nextInt() - 1 ; graph[a].add(new ListNode (b, color[b])); graph[b].add(new ListNode (a, color[a])); } boolean [] visited = new boolean [n]; System.out.println("访问顺序:" + 0 ); dfs(graph, new ListNode (0 , color[0 ]), 0 , 0 , visited); System.out.println(ans); } static int ans = 0 ; public static void dfs (List<ListNode>[] graph, ListNode curNode, int red, int blue, boolean [] visited) { visited[(int )curNode.num] = true ; if (curNode.isRed) { red += 1 ; } else { blue += 1 ; } ans += Math.abs(red - blue); for (ListNode listNode: graph[(int )curNode.num]) { if (!visited[(int )listNode.num]) { System.out.println("访问顺序:" + listNode.num); dfs(graph, listNode, red, blue, visited); } } visited[(int )curNode.num] = false ; } }
股票推荐 并查集
ZOOM 8月10号笔试
题目
完成股票推荐系统设计,每个用户可能关注几个公司,比如A,B,C,如果有另一个用户只关注了A,那么就会给他推荐B,C。这时候如果来了一个用户关注C,D,那么后来关注C的用户,都会推荐A,B,关注A的用户都会推荐BCD。在有上面的关系后,求用户查询的时候,会给它推荐的公司的个数。
(感觉,应该是后来关注c的,会推荐 ABC)
输入 第一行输入q表示操作次数 接下来输入一次操作 共有两种操作 1.注册 格式为 1 name n 表示有一个name的人关注了n个股票 第二行输入n个字符串表示这n个股票 n个字符串不相同 2.查询 格式为 输入2 name 表示查询系统会给此人推荐多少股票 保证至少有一次查询 例
5 1 Alice 2 Zoom Apple 2 Bob 2 Alice 1 Bob 2 Apple MicroSoft 2 Bob
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 package org.jcwang.zoom;import java.util.*;public class GuPiao { public static void main (String[] args) { Solution solution = new GuPiao ().new Solution (); solution.tuijian(); } class Solution { int N = 500001 ; int [] parent = new int [N]; int [] rank = new int [N]; int size[] = new int [N]; int find (int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } boolean query (int a, int b) { return (parent[find(a)] == parent[find(b)]); } void union (int a, int b) { int rootA = find(a); int rootB = find(b); if (rank[rootA] > rank[rootB]) { int temp = rootA; rootA = rootB; rootB = temp; } parent[rootB] = rootA; size[rootA] += size[rootB]; if (rank[rootA] == rank[rootB]) { rank[rootA] += 1 ; } } int index = 0 ; void tuijian () { for (int i = 0 ; i < N; i++) { parent[i] = i; rank[i] = 0 ; size[i] = 1 ; } Map<String, Integer> nameStockIndexMap = new HashMap <>(); Map<String, Integer> stockStockIndexMap = new HashMap <>(); Map<String, Integer> nameStockNumMap = new HashMap <>(); Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); while (n-- != 0 ) { int op = scanner.nextInt(); switch (op) { case 1 : String name = scanner.next(); int stockNum = scanner.nextInt(); int firstStock = -1 ; for (int i = 0 ; i < stockNum; i++) { String stockName = scanner.next(); int curStockIndex = -1 ; if (stockStockIndexMap.containsKey(stockName)) { curStockIndex = stockStockIndexMap.get(stockName); } else { curStockIndex = index++; } stockStockIndexMap.put(stockName, curStockIndex); nameStockIndexMap.put(name, curStockIndex); nameStockNumMap.put(name, stockNum); if (i == 0 ) { firstStock = curStockIndex; } else { if (!query(curStockIndex, firstStock)) { union(curStockIndex, firstStock); } } } break ; case 2 : String name2 = scanner.next(); if (!nameStockIndexMap.containsKey(name2)) { System.out.println("error" ); } else { System.out.println(size[find(nameStockIndexMap.get(name2))] - nameStockNumMap.get(name2)); } break ; default : break ; } } } } }
0811兴业数金 序列化的内容包括以下几个方面: 属性,包括基本数据类型、数组以及其他对象的引用;
类名;
不能被序列化的内容有: 方法;
有static修饰的属性;
有transient修饰的属性;
Mybatis是这样防止sql注入的
你真的懂mysql中order by吗
JDK1.8和1.7下的HashMap的区别
扑克 可以用queue模拟,而不是用数组,加标记。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class Main { public static void main (String args[]) { Scanner cin = new Scanner (System.in); int n = Integer.parseInt(cin.nextLine()); int [] card = Arrays.stream(cin.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); int [] origin = new int [n]; Deque<Integer> d = new ArrayDeque <>(); for (int i = 0 ; i < n; i++) d.offerLast(n - i - 1 ); for (int i = 0 ; i < n; i++) { d.offerFirst(d.pollLast()); d.offerFirst(d.pollLast()); origin[d.pollLast()] = card[i]; } for (int i = 0 ; i < n; i++) { System.out.printf("%d " , origin[i]); } } }
合法三元组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Main { public static void main (String args[]) { Scanner cin = new Scanner (System.in); int n = Integer.parseInt(cin.nextLine()); int [] nums = Arrays.stream(cin.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); long count = 0 ; Map<Integer, Integer> mp = new HashMap <>(); mp.put(nums[n - 1 ], 1 ); for (int i = n - 2 ; i >= 1 ; i--) { for (int j = i - 1 ; j >= 0 ; j--) { count += mp.getOrDefault(3 * nums[i] - nums[j], 0 ); } mp.put(nums[i], mp.getOrDefault(nums[i], 0 ) + 1 ); } System.out.println(count); } }

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 #include <bits/stdc++.h> using namespace std; using LL = long long ;int main () { freopen("test.txt" , "r" , stdin); ios::sync_with_stdio(false ); int n, m; cin >> n >> m; vector<int > a (n) , b(m); for (int i = 0 ; i < n; ++i) { cin >> a[i]; } for (int i = 0 ; i < m; ++i) { cin >> b[i]; } vector<vector<int >> dp (n + 1 , vector<int >(m + 1 , 0 ) ); for (int i = 1 ; i < n + 1 ; ++i) { dp[i][0 ] = dp[i - 1 ][0 ] + abs(a[i - 1 ]); } for (int i = 1 ; i < m + 1 ; ++i) { dp[0 ][i] = dp[0 ][i - 1 ] + abs(b[i - 1 ]); } for (int i = 1 ; i < n + 1 ; ++i) { for (int j = 1 ; j < m + 1 ; ++j) { if (a[i - 1 ] == b[i - 1 ]) dp[i][j] = dp[i - 1 ][j - 1 ]; else dp[i][j] = min(abs(a[i-1 ] - b[j-1 ]) + dp[i - 1 ][j - 1 ], min(dp[i - 1 ][j] + abs(a[i - 1 ]), dp[i][j - 1 ] + abs(b[j - 1 ]))); } } cout << dp[n][m]; return 0 ; }
0820网易互联网 【2022-08-20】网易秋招笔试四道编程题
两个正整数操作 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 import java.util.*;public class BeiShuZijiChongxinzuo { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); String A = scanner.next(), B = scanner.next(); Map<Integer, Integer> mapA = new HashMap <>(); Map<Integer, Integer> mapB = new HashMap <>(); dfs(mapA, A, 0 , 0 , 0 ); dfs(mapB, B, 0 , 0 , 0 ); int ans = Integer.MAX_VALUE; for (Integer a : mapA.keySet()) { for (Integer b : mapB.keySet()) { if (a % b == 0 || b % a == 0 ) { ans = Math.min(ans, mapA.get(a) + mapB.get(b)); } } } System.out.println(ans == Integer.MAX_VALUE ? -1 : ans); } public static void dfs (Map<Integer, Integer> map, String str, int curIndex, int val, int opCount) { if (curIndex == str.length()) { if (val != 0 ) { map.put(val, str.length() - opCount); } return ; } dfs(map, str, curIndex + 1 , val, opCount + 1 ); val = val * 10 + (str.charAt(curIndex) - '0' ); dfs(map, str, curIndex + 1 , val, opCount); val = (val - (str.charAt(curIndex) - '0' )) / 10 ; } }
拟合:三元组ai>aj, ai=ak 【2022-08-20】网易秋招笔试四道编程题
由于a的值太大,所以考虑离散化
两个数组分别存放左边开始,右边开始的对应值的个数。如l[i]表示在0~当前下标中,i出现的个数。
然后用树状数组 维护相同数字的个数的乘积。
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 59 60 61 62 63 64 65 66 67 import java.util.*;import java.util.stream.Collectors;public class SanYuanZu { static int N = 1 ; static int [] tr; static int lowbit (int x) { return x & (-x); } static void update (int x, int value) { for (int i = x; i < N; i += lowbit(i)) { tr[i] += value; } } static int query (int x) { int ans = 0 ; for (int i = x; i > 0 ; i -= lowbit(x)) { ans += tr[i]; } return ans; } public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int [] nums = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toCollection(() -> new TreeSet <>((a, b) -> b - a))); Map<Integer, Integer> map = new HashMap <>(); for (Integer num : set) { map.put(num, N++); } nums = Arrays.stream(nums).map(map::get).toArray(); int [] l = new int [N+10 ], r = new int [N + 10 ]; tr = new int [N + 10 ]; for (int num : nums) { r[num] += 1 ; } int ans = 0 ; for (int num : nums) { ans += query(num-1 ); update(num, -l[num] * r[num]); l[num] += 1 ; r[num] -= 1 ; update(num, l[num] * r[num]); } System.out.println(ans); } }
注意: 个人想法:
针对这个题目,有点想法,是用树状数组,那么肯定需要有类似于前缀和的思想,或者说求的个数,也是需要有区间性质的,就跟上面一样。
而不是说比如下面这一题:(见0904滴滴)
0825荣耀 【2022-08-25】荣耀秋招笔试三道编程题
会议最长时间
简书:解答
不是想象的 排序 + 贪心
是 排序 + 24小的dp,注意我对这个dp写的一些注解
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 import java.util.*;public class ConferenceTime { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int T = Integer.parseInt(scanner.nextLine()); while (T-- != 0 ) { int n = Integer.parseInt(scanner.nextLine()); int [][] times = new int [n][2 ]; for (int i = 0 ; i < n; i++) { times[i] = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); } Arrays.sort(times, (time1, time2) -> time1[0 ] - time2[0 ]); int [] dp = new int [24 ]; for (int i = 0 ; i < 1 ; i++) { int start = times[i][0 ], end = times[i][1 ]; for (int j = end; j < 24 ; j++) { dp[j] = Math.max(dp[start] + end - start, dp[j]); } } Arrays.stream(dp).forEach(num -> System.out.print(num + " " )); System.out.println(dp[23 ]); } } } import java.util.*;public class ConferenceTime { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int T = Integer.parseInt(scanner.nextLine()); while (T-- != 0 ) { int n = Integer.parseInt(scanner.nextLine()); int [][] times = new int [n][2 ]; for (int i = 0 ; i < n; i++) { times[i] = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); } Arrays.sort(times, (time1, time2) -> time1[0 ] - time2[0 ]); int [][] dp = new int [times.length + 1 ][24 ]; for (int i = 1 ; i <= times.length; i++) { int start = times[i-1 ][0 ], end = times[i-1 ][1 ]; for (int j = 0 ; j < 24 ; j++) { if (j < end) { dp[i][j] = dp[i-1 ][j]; } else { dp[i][j] = Math.max(dp[i-1 ][start] + end - start, dp[i-1 ][j]); } } } Arrays.stream(dp[times.length]).forEach(num -> System.out.print(num + " " )); System.out.println(dp[times.length][23 ]); } } }
两个背包问题
背包问题的很不错的变种
非常注意,不是贪心。
此处,居然是重量为一半,的01背包问题,然后看此时最多的重量是多少,然后用总的sum 减去 一半情况最多时候的dp重量
注意,如果单纯用二维dp,会有10%过不去,需要改成一维dp 的滚动数组。这个一维的dp,由于需要依赖上一次的前面,所以反着dp。
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 public class CangKu { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int M = Integer.parseInt(scanner.nextLine()); int [] nums = Arrays.stream(scanner.nextLine().split(" " )) .mapToInt(Integer::valueOf) .toArray(); int n = nums.length; int m = Arrays.stream(nums).sum() / 2 ; int [] dp = new int [m + 1 ]; for (int i = 1 ; i < n + 1 ; i++) { for (int j = m; j >= 0 ; j--) { if (j < nums[i - 1 ]) { dp[j] = dp[j]; } else { dp[j] = Math.max(dp[j], dp[j - nums[i-1 ]] + nums[i - 1 ]); } } } System.out.println(Arrays.stream(nums).sum() - dp[m]); } }
0825美的 第一题是模拟题,好好读题,细心点就行
同一直线上,最多的点 宫水三叶:优化(枚举直线 + 哈希表统计)
斜率的话,朴素的,可以(x2 - x1) * (y3 - y2) == (x3 - x2) * (y2 - y1)
如果是像下面这样的,可以将斜率用字符串存起来(为了保证斜率的精度问题),首先得求出最大公约数
然后是枚举遍历,每一次从一个点出发,然后用map村上斜率的个数,取最多的,最后记得加上自己这个点。
每次循环都是考虑以这个点为出发点的斜率。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int maxPoints (int [][] ps) { int n = ps.length; int ans = 1 ; for (int i = 0 ; i < n; i++) { Map<String, Integer> map = new HashMap <>(); int max = 0 ; for (int j = i + 1 ; j < n; j++) { int x1 = ps[i][0 ], y1 = ps[i][1 ], x2 = ps[j][0 ], y2 = ps[j][1 ]; int a = x1 - x2, b = y1 - y2; int k = gcd(a, b); String key = (a / k) + "_" + (b / k); map.put(key, map.getOrDefault(key, 0 ) + 1 ); max = Math.max(max, map.get(key)); } ans = Math.max(ans, max + 1 ); } return ans; } int gcd (int a, int b) { return b = = 0 ? a : gcd(b, a % b); } }
0827完美世界 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 public static class ShowMeBug1 { public int lastGarbageSize (int [] garbages) { int n = garbages.length; int sum = 0 ; for (int g: garbages) { sum += g; } int m = sum / 2 ; boolean [][] dp = new boolean [n + 1 ][m + 1 ]; dp[0 ][0 ] = true ; for (int i = 1 ; i <= n; i++) { for (int j = 0 ; j <= m; j++) { if (j < garbages[i-1 ]) { dp[i][j] = dp[i-1 ][j]; } else { dp[i][j] = dp[i-1 ][j] || dp[i-1 ][j - garbages[i-1 ]]; } } } for (int j = m; j>=0 ; j--) { if (dp[n][j]) { return sum - 2 * j; } } return 0 ; } }
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 public static class ShowMeBug { public int [][] mergeCard(int [][] cards) { List<int []> ans = new ArrayList <>(); int count = 0 ; Arrays.sort(cards, (card1, card2) -> card1[0 ] - card2[0 ]); ans.add(cards[0 ]); for (int i = 1 ; i < cards.length; i++) { int b = cards[i][0 ], e = cards[i][1 ]; if (b > ans.get(count)[1 ]) { ans.add(cards[i]); count += 1 ; } else { ans.get(count)[1 ] = Math.max(e, ans.get(count)[1 ]); } } int [][] newAns = new int [ans.size()][2 ]; for (int i = 0 ; i < ans.size(); i++) { newAns[i][0 ] = ans.get(i)[0 ]; newAns[i][1 ] = ans.get(i)[1 ]; } return newAns; } }
0828小红书 一对一
注意:树 本题说了,这张无向图里面,任意两点之间有且仅有一条路径,
而且输入的时候,n-1个数字,ai代表ai到i-1有路径
那么这肯定是棵树
以下是我自己当时做出来的答案,从叶子往上面取
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 59 60 61 62 63 import java.util.*;public class Main3 { public static class TreeNode { List<TreeNode> childs; int val; TreeNode(int val) { this .val = val; childs = new ArrayList <>(); } } public static void main (String[] args) { Scanner scanner = new Scanner (System.in); n = Integer.parseInt(scanner.nextLine()); visited = new boolean [n + 1 ]; TreeNode[] nodes = new TreeNode [n + 1 ]; for (int i = 0 ; i < n + 1 ; i++) { nodes[i] = new TreeNode (i); } for (int i = 0 ; i < n-1 ; i++) { int temp = scanner.nextInt(); nodes[temp].childs.add(nodes[i+2 ]); } TreeNode root = nodes[1 ]; dfs(root); System.out.println(ans); } static int n = 0 ; static int ans = 0 ; static boolean [] visited; public static void dfs (TreeNode node) { if (!node.childs.isEmpty() && !visited[node.val]) { for (int i = 0 ; i < node.childs.size(); i++) { if (!node.childs.get(i).childs.isEmpty()) { dfs(node.childs.get(i)); } } for (int i = 0 ; i < node.childs.size(); i++) { if (!visited[node.childs.get(i).val]) { visited[node.childs.get(i).val] = true ; visited[node.val] = true ; ans += 1 ; return ; } } } } }
0827美团 挑剔
考虑最好是用模拟,但是每次模拟搬动太多了。
所以想到了用queue + set。
由于数字是不重复的,而且每次的操作,都是讲编号m放到最前面,那么双端队列最前面放一个放一个就好
里面的不删除,最后从前往后输出的时候用set判断,输出过的就不再输出。
另一种思路:也可以每一次被操作的数字记录时间戳,然后按照时间戳从大到小。当然一开始是的输入不是。
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 import java.util.*;public class Main2 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(), m = scanner.nextInt(); scanner.nextLine(); int [] indexs = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); int [] nums = IntStream.range(0 , n).map(i -> i+1 ).toArray(); Deque<Integer> queue = new ArrayDeque <>(); for (int i = 0 ; i < n; i++) { queue.offerLast(i + 1 ); } for (int i = 0 ; i < m; i++) { queue.offerFirst(indexs[i]); } Set<Integer> set = new HashSet <>(); int size = queue.size(); for (int i = 0 ; i < size; i++) { int temp = queue.pollFirst(); if (!set.contains(temp)) { System.out.print(temp + " " ); set.add(temp); } } } }
裁缝 dfs+回溯
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 59 60 61 62 63 64 65 66 67 68 import java.util.*;public class Main3 { static int n, m; static String s; static int [] kehu; static String[] kehuStrs; static int ans; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); n = scanner.nextInt(); m = scanner.nextInt(); scanner.nextLine(); s = scanner.nextLine(); kehu = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); kehuStrs = new String [m]; for (int i = 0 ; i < m; i++) { kehuStrs[i] = scanner.nextLine(); } dfsTrace(0 , 0 , new ArrayList <>()); System.out.println(ans); } public static void dfsTrace (int preIndex, int curIndex, List<String> strs) { if (strs.size() == m - 1 && curIndex <= n - 1 ) { strs.add(s.substring(preIndex)); boolean [] visited = new boolean [m]; out: for (int j = 0 ; j < m; j++) { for (int i = 0 ; i < m; i++) { if (!visited[i] && strs.get(j).equals(kehuStrs[i])) { visited[i] = true ; continue out; } } strs.remove(strs.size() - 1 ); return ; } strs.remove(strs.size() - 1 ); ans += 1 ; return ; } if (curIndex >= n - 1 ) { return ; } dfsTrace(preIndex, curIndex + 1 , strs); strs.add(s.substring(preIndex, curIndex + 1 )); dfsTrace(curIndex + 1 , curIndex + 1 , strs); strs.remove(strs.size() - 1 ); } }
下雨
掌握到感觉是有点牛的
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 59 60 61 62 63 64 65 66 67 68 import java.util.*;public class Main4 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(), b = scanner.nextInt(); scanner.nextLine(); int [] p = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); int [] t = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); if (p[0 ] > b) { System.out.println(-1 ); return ; } int left = 1 , right = Arrays.stream(t).sum(); int ans = 0 ; while (left <= right) { int mid = left + (right - left >> 1 ); if (check(mid, n, p, t, b)) { ans = mid; right = mid - 1 ; } else { left = mid + 1 ; } } System.out.println(ans); } public static boolean check (int time, int n, int [] p, int [] t, int b) { int [] dp = new int [n+2 ]; Arrays.fill(dp, Integer.MAX_VALUE); dp[n+1 ] = 0 ; for (int i = n; i >= 1 ; i--) { for (int j = n+1 ; j > i; j--) { if ((j - i) * t[i-1 ] <= time) { dp[i] = Math.min(dp[i], dp[j] + p[i-1 ]); } } } return dp[1 ] <= b; } }
0827京东 漂亮串 字符中,有两个red,其他的都是小写字母,组成不了red的,问字符串n中有多少个漂亮串。
用dp
1 2 3 抛砖引玉一个朴素易懂的DP:总的思路是做减法,用 所有长度为n的字符串数 减去 长度为n不含'red'的字符串数 和 长度为n有且仅有一个'red'的字符串数。维护一个 dp[2][N] 的二维数组, 第一个下标代表字符串中 'red'出现的次数,第二个下标代表字符串长度 于是dp[0][i] 即为 长度为 i 其中包含 0 个'red'的字符串个数(即不出现'red') 于是dp[1][i] 即为 长度为 i 其中包含 1 个'red'的字符串个数 最终结果就应该是很简单的 26^(N) - dp[0][N] - dp[1][N] 重头戏是状态转移防程:首先考虑 dp[0][i], 分 第 i 位不是'd' 和 第 i 位是'd' 两种情况考虑 如果第 i 位不是'd', 那前面 [0~i-1] 位只要不包含'red'就行,而第i位除'd'以外还有25种选择,dp[0][i-1] * 25 如果第 i 位是'd',那其前面两位不能是're', 考虑从 dp[0][i-1] 中剔除所有的 dp[0][i-3]'re'的情况,第i位只有'd'一种选择,(dp[0][i-1] - dp[0][i-3]) * 1 因此综合来看,dp[0][i] = dp[0][i-1] * 25 + (dp[0][i-1] - dp[0][i-3]) * 1 = dp[0][i-1] * 26 - dp[0][i-3] 其次考虑 dp[1][i], 也分 第 i 位不是'd' 和 第 i 位是'd' 两种情况考虑 如果第 i 位不是'd', 那前面 [0~i-1] 位需要包含一次'red',而第i位除'd'以外还有25种选择,dp[1][i-1] * 25 如果第 i 位是'd',那又有两种情况, “ 不包含'red' 的[0~i-3]+‘red’ ” 或者 “ 包含'red'的[0~i-3]+非're'+'d' ” “ 不包含'red'的[0~i-3]+‘red’ ”,非常简单,即 dp[0][i-3] * 1 “ 包含'red'的[0~i-3]+非're'+'d' ”的情况与之前类似,考虑从 dp[1][i-1] 中剔除所有的 dp[1][i-3]'re'的情况,第i位只有'd'一种选择,(dp[1][i-1] - dp[1][i-3]) * 1 因此综合来看,dp[1][i] = dp[1][i-1] * 25 + dp[0][i-3] + (dp[1][i-1] - dp[1][i-3]) * 1
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 #include <bits/stdc++.h> using namespace std;typedef long long ll;const int N = 1e6 + 10 ;const int mod = 1e9 + 7 ;ll dp[N][4 ]; void init (int n) { dp[0 ][0 ] = 1 ; for (int i = 1 ; i <= n; i ++){ dp[i][0 ] = (dp[i - 1 ][0 ] * 25 % mod + dp[i - 1 ][1 ] * 24 % mod + dp[i - 1 ][2 ] * 24 % mod) % mod; dp[i][1 ] = (dp[i - 1 ][0 ] + dp[i - 1 ][1 ] + dp[i - 1 ][2 ]) % mod; dp[i][2 ] = dp[i - 1 ][1 ]; } } int main () { int n; cin >> n; ll ans = 1 ; for (int i = 1 ; i <= n; i ++){ ans = ans * 26 % mod; } init (n); ans = (ans - (dp[n][0 ] + dp[n][1 ] + dp[n][2 ]) % mod + mod) % mod; for (int i = 1 ; i <= n - 2 ; i ++){ ll left = (dp[i - 1 ][0 ] + dp[i - 1 ][1 ] + dp[i - 1 ][2 ]) % mod; ll right = (dp[n - i - 2 ][0 ] + dp[n - i - 2 ][1 ] + dp[n - i - 2 ][2 ]) % mod; ans = (ans - left * right % mod + mod) % mod; } cout << ans << endl; return 0 ; }
0828小红书 一对一
这是我自己做的。
这一题,一看n节点,n-1条边,是树,而且是有向的,直接建树就好。 使用邻接表。
然后两两配对,需要从叶子结点根父节点配对,所以是dfs先到最底下,把叶子和父亲配对,配对完就visited标识为给true,后面就不能配对了,以此类推。
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 59 60 61 62 63 64 import java.util.*;public class Main3 { public static class TreeNode { List<TreeNode> childs; int val; TreeNode(int val) { this .val = val; childs = new ArrayList <>(); } } public static void main (String[] args) { Scanner scanner = new Scanner (System.in); n = Integer.parseInt(scanner.nextLine()); visited = new boolean [n + 1 ]; TreeNode[] nodes = new TreeNode [n + 1 ]; for (int i = 0 ; i < n + 1 ; i++) { nodes[i] = new TreeNode (i); } for (int i = 0 ; i < n-1 ; i++) { int temp = scanner.nextInt(); nodes[temp].childs.add(nodes[i+2 ]); } TreeNode root = nodes[1 ]; dfs(root); System.out.println(ans); } static int n = 0 ; static int ans = 0 ; static boolean [] visited; public static void dfs (TreeNode node) { if (!node.childs.isEmpty() && !visited[node.val]) { for (int i = 0 ; i < node.childs.size(); i++) { if (!node.childs.get(i).childs.isEmpty()) { dfs(node.childs.get(i)); } } for (int i = 0 ; i < node.childs.size(); i++) { if (!visited[node.childs.get(i).val]) { visited[node.childs.get(i).val] = true ; visited[node.val] = true ; ans += 1 ; return ; } } } } }
0830携程 rgb染色 首先建图(虽然此处n个节点,n-1条边,联通图,但是题目给的是无向图,所以不知道是哪里指向哪里的,所以还是建图,后面dfs的时候,在参数里面指定父节点,然后遍历子节点的时候取出父节点就好了)。
注意,数量问题,可以考虑每个节点挂以当前节点为根的总数据(dfs实现),下面圣诞树dp,也有类似的想法。
下面的代码是建树的,后面来不及改成图了。
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 import java.util.*;public class Main3 { static int ans = 0 ; public static class TreeNode { List<TreeNode> childs; int [] colors = new int [3 ]; TreeNode(char color) { childs = new ArrayList <>(); if (color == 'r' ) { colors[0 ] = 1 ; } else if (color == 'g' ) { colors[1 ] = 1 ; } else { colors[2 ] = 1 ; } } } public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); scanner.nextLine(); String colors = scanner.nextLine(); int [] inDe = new int [n]; TreeNode[] nodes = new TreeNode [n]; for (int i = 0 ; i < n; i++) { nodes[i] = new TreeNode (colors.charAt(i)); } for (int i = 0 ; i < n - 1 ; i++) { int u = scanner.nextInt() - 1 , v = scanner.nextInt() - 1 ; if (inDe[v] > 0 ) { int temp = u; u = v; v = temp; } nodes[u].childs.add(nodes[v]); inDe[v] += 1 ; } TreeNode root = nodes[0 ]; for (int i = 0 ; i < n; i++) { if (inDe[i] == 0 ) { root = nodes[i]; } } dfs(root); judge(root, root); System.out.println(ans); } public static void dfs (TreeNode node) { if (node != null ) { for (TreeNode child : node.childs) { dfs(child); } for (int i = 0 ; i < node.childs.size(); i++) { for (int j = 0 ; j < 3 ; j++) { node.colors[j] += node.childs.get(i).colors[j]; } } } } public static void judge (TreeNode node, TreeNode root) { if (node != null ) { int [] allColors = root.colors; for (TreeNode child : node.childs) { int [] colors2 = child.colors; boolean flag = true ; for (int i = 0 ; i < 3 ; i++) { if (colors2[i] < 1 || allColors[i] - colors2[i] < 1 ) { flag = false ; break ; } } ans = flag ? ans + 1 : ans; judge(child, root); } } } }
平滑值 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 import java.util.*;public class Main4 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = Integer.parseInt(scanner.nextLine()); int [] nums = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); int maxDist = 0 ; int pos = -1 ; for (int i = 0 ; i < n - 1 ; i++) { if (Math.abs(nums[i + 1 ] - nums[i]) >= maxDist) { pos = i; maxDist = Math.abs(nums[i + 1 ] - nums[i]); } } if (pos == 0 ) { nums[pos] = nums[pos + 1 ]; } else if (pos == n - 2 ) { nums[pos + 1 ] = nums[pos]; } else { nums[pos] = (nums[pos - 1 ] + nums[pos + 1 ]) / 2 ; } maxDist = 0 ; for (int i = 0 ; i < n - 1 ; i++) { if (Math.abs(nums[i + 1 ] - nums[i]) > maxDist) { maxDist = Math.abs(nums[i + 1 ] - nums[i]); } } System.out.println(maxDist); } }
0831顺丰 猜数列游戏 每一个位置,二分二分查找
如果遍历1~n,每个取log2,相加,会超时
所以考虑数字范围,比如2^i ~ 2^(i+1)-1取i+1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.*;public class Main1 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = Integer.parseInt(scanner.nextLine()); if (n == 1 ) { System.out.println(1 ); return ; } long ans = 0 ; long bn = (long ) (Math.log(n) / Math.log(2 )); for (int i = 1 ; i < bn; i++) { ans += (i + 1 ) * ((long )Math.pow(2 , i+1 ) - (long )Math.pow(2 , i)); } ans += (n - (long )Math.pow(2 , bn) + 1 ) * (bn + 1 ); System.out.println(ans + 1 ); } }
圣诞树 CodeForces 274 B.Zero Tree(树形dp)
注意,这是一个无向图,但是题目说是,一定要包含节点1的子图,所以其实可以看作树,以1为根节点
这个题目其实就是给的树的结构,所以其实应该可以建树的。(下面的代码使用了邻接矩阵)。
但是有的题目如果给出n个节点,n-1条边保证联通图,但是这个时候其实不能建树,得建图。建图了之后,保证类似树的遍历方法,跟下面一样,传参数的时候传个父节点,判断下父节点不dfs就行了。
很好的一个例子是小红书的一对一,员工n个,员工关系n-1,保证联通。因为无向图,所以只能建树其实,而且树节点未知,考虑入度为0。还有下面网易的那一题。
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 import java.util.*;public class Main2 { static List<Long>[] g; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = Integer.parseInt(scanner.nextLine()); int [] parents = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); yuanwangs = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); Main2.n = n; inc = new long [n + 1 ]; dec = new long [n + 1 ]; g = new ArrayList [n+1 ]; for (int i = 0 ; i <= n; i++) { g[i] = new ArrayList <>(); } for (int i = 2 ; i <= n; i++) { g[i].add((long )parents[i-2 ]); g[parents[i-2 ]].add((long )i); } shengdanshuDfs(1 , 0 ); System.out.println(inc[1 ] + dec[1 ]); } static int n; static long [] inc, dec; static int [] yuanwangs; public static void shengdanshuDfs (long u, long fa) { for (int i = 0 ; i < g[(int )u].size(); i++) { long v = g[(int )u].get(i); if (v == fa) { continue ; } shengdanshuDfs(v, u); inc[(int )u] = Math.max(inc[(int )u], inc[(int )v]); dec[(int )u] = Math.max(dec[(int )u], dec[(int )v]); } yuanwangs[(int )u-1 ] += inc[(int )u] - dec[(int )u]; if (yuanwangs[(int )u-1 ] > 0 ) { dec[(int )u] += yuanwangs[(int )u-1 ]; } else { inc[(int )u] -= yuanwangs[(int )u-1 ]; } } }
0831华为
字符串压缩替换 虽然是O(n),但是还是只有95%过了。
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 59 60 61 62 63 64 65 66 67 68 69 70 import java.util.*;public class Main1 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); String senStr = scanner.nextLine(); String[] list = scanner.nextLine().toLowerCase().split(" " ); Map<String, Integer> map = new HashMap <>(); for (int i = 0 ; i < list.length; i++) { map.put(list[i], i); } int left = 0 , right = -1 ; StringBuilder ans = new StringBuilder (); char c; int len = senStr.length(); while (right < senStr.length()) { left = right + 1 ; while (left < len && (senStr.charAt(left) == ',' || senStr.charAt(left) == '.' || senStr.charAt(left) == ' ' )) { ans.append(senStr.charAt(left)); left += 1 ; } if (left >= len) { break ; } if (senStr.charAt(left) == '\"' ) { ans.append(senStr.charAt(left)); left += 1 ; while (senStr.charAt(left) != '\"' ) { ans.append(senStr.charAt(left)); left += 1 ; } ans.append(senStr.charAt(left)); right = left; continue ; } right = left; c = senStr.charAt(right); while (right < len && c != ',' && c != '.' && c != '\"' && c != ' ' ) { right += 1 ; if (right < len) { c = senStr.charAt(right); } } String tempStr = senStr.substring(left, right); if (map.containsKey(tempStr.toLowerCase())) { ans.append(map.get(tempStr.toLowerCase())); } else { ans.append(tempStr); } if (right < len) { ans.append(senStr.charAt(right)); } } System.out.println(ans.toString()); } }
走迷宫(带有陷阱炸弹强)
注意下面的减枝,普通的减curTime>ans只能过45%,然后减枝改成当前时间+最快能到达>ans,就过了
减枝一般两种 第一种是记忆化搜索,第二种是就上面用的当前的加未来能到达的 > 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 import java.util.*;public class Main2 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(), m = scanner.nextInt(); Main2.n = n; Main2.m = m; scanner.nextLine(); int [][] matrix = new int [n][m]; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { int val = scanner.nextInt(); matrix[i][j] = val; if (val == 2 ) { start[0 ] = i; start[1 ] = j; } else if (val == 3 ) { end[0 ] = i; end[1 ] = j; } } } dfsTrace(matrix, new boolean [n][m], 0 , start); System.out.println(ans); } static int n, m; static int ans = Integer.MAX_VALUE; static int [] start = new int [2 ], end = new int [2 ]; static int [][] dirs = new int [][]{{1 , 0 }, {-1 , 0 }, {0 , 1 }, {0 , -1 }}; public static void dfsTrace (int [][] matrix, boolean [][] visited, int curTime, int [] curLoc) { int x = curLoc[0 ], y = curLoc[1 ]; if (x == end[0 ] && y == end[1 ]) { ans = Math.min(ans, curTime); return ; } if ((Math.abs(x - end[0 ]) + Math.abs(y - end[1 ]) + curTime >= ans)) { return ; } visited[x][y] = true ; curTime += 1 ; if (matrix[x][y] == 4 ) { curTime += 2 ; } else if (matrix[x][y] == 6 ) { for (int i = 0 ; i < 4 ; i++) { int newX = x + dirs[i][0 ], newY = y + dirs[i][1 ]; if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 1 ) { matrix[newX][newY] = 9 ; } } } for (int i = 0 ; i < 4 ; i++) { int newX = x + dirs[i][0 ], newY = y + dirs[i][1 ]; if (newX >= 0 && newX < n && newY >= 0 && newY < m && !visited[newX][newY] && (matrix[newX][newY] == 0 || matrix[newX][newY] == 4 || matrix[newX][newY] == 9 || matrix[newX][newY] == 6 || matrix[newX][newY] == 3 )) { dfsTrace(matrix, visited, curTime, new int []{newX, newY}); } } if (matrix[x][y] == 6 ) { for (int i = 0 ; i < 4 ; i++) { int newX = x + dirs[i][0 ], newY = y + dirs[i][1 ]; if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 9 ) { matrix[newX][newY] = 1 ; } } } visited[x][y] = false ; } }
充电桩问题
动态规划,过了80%,注意,ans会是小数,然后答案是正数的话输出得整数。
然后没过的20%可能是,输入的waittimes有可能是double???
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 59 60 61 62 63 64 65 66 67 68 import java.util.*;public class Main3 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int D = scanner.nextInt(); int N = scanner.nextInt(); int [] distances = new int [N + 2 ]; int [] times = new int [N + 2 ]; for (int i = 1 ; i <= N; i++) { distances[i] = scanner.nextInt(); times[i] = scanner.nextInt(); } double [][] dp = new double [N + 2 ][1001 ]; for (int i = 0 ; i < N + 2 ; i++) { Arrays.fill(dp[i], 0x3f3f3f3f ); } dp[0 ][1000 ] = 0 ; distances[N + 1 ] = D; for (int i = 1 ; i <= N + 1 ; i++) { int cost = times[i] + 1 ; int dst = distances[i] - distances[i - 1 ]; if (dst > 1000 ) { System.out.println(-1 ); return ; } for (int j = 0 ; j <= 1000 - dst; j++) { if (j + dst > 1000 ) { dp[i][j] = 0x3f3f3f3f ; } else { dp[i][j] = Math.min(dp[i-1 ][j+dst] + dst * 1.0 / 100 , dp[i][j]); dp[i][1000 ] = Math.min(dp[i][1000 ], dp[i-1 ][j+dst] + dst * 1.0 / 100 + cost); } } } double ans = 0x3f3f3f3f ; for (int i = 0 ; i < 1001 ; i++) { ans = Math.min(ans, dp[N+1 ][i]); } if (ans == 0x3f3f3f3f ) { System.out.println(-1 ); }else if (ans == (long )ans) { System.out.println((long )ans); } else { System.out.println(ans); } } }
0903美团笔试 0903搜狐畅游 0904飞哥网易互联网 树的权值因数和
这里面,可以看出,说是两个节点之间有关联,但是是无向图,所以需要用邻接表建图,题目说了节点1是父节点,就不用用度判断父节点了。
再说一下,下面这个可能时间会超时。未验证
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 import java.util.*;public class Main4 { public static class Node { long val; int bianhao; long count; Node(long val, int bianhao) { this .val = val; this .bianhao = bianhao; count = 0 ; } } public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = Integer.parseInt(scanner.nextLine()); int [] nums = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); Node[] nodes = new Node [n + 1 ]; List<Node>[] g = new ArrayList [n + 1 ]; for (int i = 1 ; i < n + 1 ; i++) { g[i] = new ArrayList <>(); nodes[i] = new Node (nums[i-1 ], i); } for (int i = 0 ; i < n - 1 ; i++) { int u = scanner.nextInt(); int v = scanner.nextInt(); g[u].add(nodes[v]); g[v].add(nodes[u]); } dfs(g, nodes[1 ],0 ); System.out.println(nodes[1 ].count); } public static void dfs (List<Node>[] g, Node node, int father) { for (Node child: g[node.bianhao]) { if (child.bianhao == father) { continue ; } dfs(g, child, node.bianhao); } Set<Long> set = new HashSet <>(); boolean one = false ; for (Node child: g[node.bianhao]) { if (child.bianhao == father) { continue ; } set.add(child.val); if (child.val == 1 ) { one = true ; } node.count = (node.count + child.count) % ((long )10e9 + 7 ); } node.count = (node.count * 2 + getYinZis(node.val)) % ((long )10e9 + 7 ); set.add(node.val); if (node.val == 1 ) { one = true ; } node.count -= one ? 1 : 0 ; if (node.bianhao == 1 ) { node.count -= (g[node.bianhao].size() + 1 - set.size()); } else { node.count -= (g[node.bianhao].size() - set.size()); } node.count = (node.count) % ((long )10e9 + 7 ); } public static long getYinZis (long num) { long ans = 0 ; for (long i = 1 ; i * i <= num; i++) { if (num % i == 0 ) { if (i * i == num) { ans += 1 ; } else { ans += 2 ; } } } return ans % ((long )10e9 + 7 ); } }
数组每次减去k,找最大的最小
直接使用优先队列,每次减最大会超时,考虑二分取答案。
以下C++ 91%:
注意下面的l需要为-10e15
0904滴滴 莫队算法 (Mo’s Algorithm)
以下是我的代码,91%。感觉可以将LR排序,然后另一个同维护个数即可。
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 import java.util.*;public class Main2 { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int T = Integer.parseInt(scanner.nextLine()); int [] L = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); int [] R = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); int [] t = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); int minL = Arrays.stream(L).min().getAsInt(); int maxR = Arrays.stream(R).max().getAsInt(); int n = maxR - minL + 1 ; int [] meiliVal = new int [n]; for (int i = 0 ; i < n; i++) { int num = minL + i; int ans = 0 ; while (num != 0 ) { int temp = num % 10 ; ans ^= temp; num /= 10 ; } meiliVal[i] = ans; } for (int i = 0 ; i < T; i++) { int ans = 0 ; for (int j = L[i]; j <= R[i]; j++) { if (meiliVal[j - minL] == t[i]) { ans += 1 ; } } System.out.println(ans); } } }
0908 腾讯音乐 二叉树中序和前序
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 import java.util.*;public class Main2TechGuide { private static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this .val = val; } } public static void main (String[] args) { ArrayList<Integer> preOrder = new ArrayList <>(); ArrayList<Integer> inOrder = new ArrayList <>(); preOrder.add(1 ); preOrder.add(1 ); preOrder.add(2 ); inOrder.add(1 ); inOrder.add(2 ); inOrder.add(1 ); int n = inOrder.size(); List<TreeNode> ans = new Solution ().getBinaryTrees(preOrder, inOrder); for (TreeNode an : ans) { cengxuBianli(an); } } static TreeNode emptyNode = new TreeNode (-1 ); public static void cengxuBianli (TreeNode root) { Deque<TreeNode> queue = new ArrayDeque <>(); queue.add(root); while (!queue.isEmpty()) { int n = queue.size(); for (int i = 0 ; i <n; i++) {TreeNode node = queue.pollFirst(); System.out.print(node == emptyNode ? "#" : node.val); if (node.left == null && node.right == null ) { continue ; } if (node.left == null ) { queue.offerLast(emptyNode); } else { queue.offerLast(node.left); } if (node.right == null ) { queue.offerLast(emptyNode); } else { queue.offerLast(node.right); } } } System.out.println(); } static class Solution { public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) { return buildTree(preOrder, 0 , preOrder.size() - 1 , inOrder, 0 , inOrder.size() - 1 ); } ArrayList<TreeNode> buildTree (ArrayList<Integer> preOrder, int preStart, int preEnd, ArrayList<Integer> inOrder, int inStart, int inEnd) { ArrayList<TreeNode> res = new ArrayList <>(); if (preStart > preEnd || inStart > inEnd) { res.add(null ); return res; } int rootVal = preOrder.get(preStart); ArrayList<Integer> indexs = new ArrayList <>(); for (int i = inStart; i <= inEnd; i++) { if (inOrder.get(i) == rootVal) { indexs.add(i); } } for (Integer index : indexs) { ArrayList<TreeNode> lefts = buildTree(preOrder, preStart + 1 , preStart + index - inStart, inOrder, inStart, index - 1 ); ArrayList<TreeNode> rights = buildTree(preOrder, preStart + index - inStart + 1 , preEnd, inOrder, index + 1 , inEnd); for (TreeNode left : lefts) { for (TreeNode right : rights) { TreeNode root = new TreeNode (rootVal); root.left = left; root.right = right; res.add(root); } } } 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 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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 import java.util.*;public class Main2 { private static class TreeNode implements Cloneable { int val; TreeNode left; TreeNode right; TreeNode(int val) { this .val = val; } @Override public TreeNode clone () { TreeNode node = null ; try { node = (TreeNode) super .clone(); if (this .left != null ) { node.left = this .left.clone(); } if (this .right != null ) { node.right = this .right.clone(); } } catch (CloneNotSupportedException e) { e.printStackTrace(); } return node; } } public static TreeNode copy (TreeNode node) { TreeNode cpNode = new TreeNode (node.val); if (node.left != null ) { cpNode.left = copy(node.left); } if (node.right != null ) { cpNode.right = copy(node.right); } return cpNode; } public static void main (String[] args) { List<Integer> preOrder = new ArrayList <>(); List<Integer> inOrder = new ArrayList <>(); preOrder.add(1 ); preOrder.add(1 ); preOrder.add(2 ); inOrder.add(1 ); inOrder.add(2 ); inOrder.add(1 ); int n = inOrder.size(); List<TreeNode> ans = dfs(preOrder, inOrder, 0 , n-1 , 0 , n-1 ); for (TreeNode an : ans) { cengxuBianli(an); } } static TreeNode emptyNode = new TreeNode (-1 ); public static void cengxuBianli (TreeNode root) { Deque<TreeNode> queue = new ArrayDeque <>(); queue.add(root); while (!queue.isEmpty()) { int n = queue.size(); for (int i = 0 ; i <n; i++) { TreeNode node = queue.pollFirst(); System.out.print(node == emptyNode ? "#" : node.val); if (node.left == null && node.right == null ) { continue ; } if (node.left == null ) { queue.offerLast(emptyNode); } else { queue.offerLast(node.left); } if (node.right == null ) { queue.offerLast(emptyNode); } else { queue.offerLast(node.right); } } } System.out.println(); } public static List<TreeNode> dfs (List<Integer> preOrder, List<Integer> inOrder, int pre_l, int pre_r, int in_l, int in_r) { if (pre_l > pre_r && in_l > in_r) { List<TreeNode> ans = new ArrayList <>(); ans.add(emptyNode); return ans; } List<TreeNode> ans = new ArrayList <>(); for (int i = in_l; i <= in_r; i++) { if (inOrder.get(i).equals(preOrder.get(pre_l))) { int num = i - in_l; List<TreeNode> node1 = dfs(preOrder, inOrder, pre_l + 1 , pre_l + num, in_l, i - 1 ); List<TreeNode> node2 = dfs(preOrder, inOrder, pre_l + num + 1 , pre_r, i + 1 , in_r); for (int x = 0 ; x < node1.size(); x++) { for (int y = 0 ; y < node2.size(); y++) { TreeNode pnew = new TreeNode (preOrder.get(pre_l)); pnew.left = node1.get(x) == emptyNode ? null : node1.get(x); pnew.right = node2.get(y) == emptyNode ? null : node2.get(y);; ans.add(pnew); } } } } 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 public int getTreeSum (TreeNode tree) { return (int ) (traverse(tree) % ((Math.pow(10 , 9 ) + 7 ))); } long traverse (TreeNode root) { if (root == null ) return 0 ; long leftVal = traverse(root.left); long rightVal = traverse(root.right); return 1 + Math.max(leftVal, rightVal) * 2 ; } } class TreeNode { int val = 0 ; TreeNode left = null ; TreeNode right = null ; public TreeNode (int val) { this .val = val; } }
0914小米 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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 import java.util.*;public class Main1XiaoMi { static class ListNode <T> { public T data; public ListNode next; } static class Solution { public ListNode<Integer> reverseBetween (ListNode<Integer> head, int left, int right) { ListNode ans = head; if (left == right) { return head; } ListNode preLeftNode = null , preRight = null , cur = ans; for (int i = 0 ; i < left - 2 ; i++) { cur = cur.next; } preLeftNode = left == 1 ? null : cur; cur = left == 1 ? cur : cur.next; ListNode leftNode = cur; ListNode tempNext = cur.next; for (int i = left; i < right; i++) { ListNode temp = tempNext.next; tempNext.next = cur; cur = tempNext; tempNext = temp; } if (preLeftNode == null ) { ans = cur; } else { preLeftNode.next = cur; } leftNode.next = tempNext; return head; } } public static void main (String[] args) { Scanner in = new Scanner (System.in); ListNode<Integer> res = null ; int head_size = 0 ; head_size = in.nextInt(); ListNode<Integer> head = null , head_curr = null ; for (int head_i = 0 ; head_i < head_size; head_i++) { int head_item = in.nextInt(); ListNode<Integer> head_temp = new ListNode <Integer>(); head_temp.data = head_item; head_temp.next = null ; if (head == null ) { head = head_curr = head_temp; } else { head_curr.next = head_temp; head_curr = head_temp; } } in.nextLine(); int left; left = Integer.parseInt(in.nextLine().trim()); int right; right = Integer.parseInt(in.nextLine().trim()); res = new Solution ().reverseBetween(head, left, right); while (res != null ) { System.out.print(String.valueOf(res.data) + " " ); res = res.next; } System.out.println(); } }
题解 | #二叉搜索树与双向链表#
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 import java.io.*;import java.util.*;import java.text.*;import java.math.*;import java.util.regex.*;public class Main10 { private static class Node { public int data; public Node left; public Node right; public Node (int data) { this .data = data; } public Node () { } public Node (int data, Node left, Node right) { this .data = data; this .left = left; this .right = right; } } private static class Solution { Node start = null , pre = null ; public Node Convert (Node pRootOfTree) { dfs(pRootOfTree); return start; } public void dfs (Node node) { if (node == null ) { return ; } dfs(node.left); if (pre == null ) { start = node; }else { pre.right = node; } node.left = pre; pre = node; dfs(node.right); } } public static void main (String[] args) { Scanner in = new Scanner (System.in); Node res = null ; List<Node> list = new ArrayList <>(); while (in.hasNextInt()) { int item = in.nextInt(); if (item == -1 ) { list.add(null ); } else { list.add(new Node (item)); } } int len = list.size(); int i = 0 ; while (i <= (len - 2 ) / 2 ) { if (2 * i + 1 < len && list.get(i) != null ) { list.get(i).left = list.get(2 * i + 1 ); } if (2 * i + 2 < len && list.get(i) != null ) { list.get(i).right = list.get(2 * i + 2 ); } i++; } res = new Solution ().Convert(list.get(0 )); if (res != null ) { while (res.right != null && res.data != -1 ) { System.out.print(String.valueOf(res.data) + " " ); res = res.right; } System.out.print(res.data + " " ); while (res.left != null && res.data != -1 ) { System.out.print(String.valueOf(res.data) + " " ); res = res.left; } System.out.print(res.data); } System.out.println(); } }
0915奇安信 蚂蚁走网格,吃食物 0915荣耀 输出环的问题
0918雷火 走迷宫啊
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 import java.util.*;public class Main4 { static int A, B, C, D; static int grid = 5 ; static int maxCeng = 10 ; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); A = scanner.nextInt(); B = scanner.nextInt(); int n = scanner.nextInt(); int m = scanner.nextInt(); int [][][][] g = new int [maxCeng + 1 ][grid + 1 ][grid + 1 ][3 ]; for (int i = 0 ; i < n; i++) { g[scanner.nextInt()][scanner.nextInt()][scanner.nextInt()][2 ] = scanner.nextInt(); } for (int i = 0 ; i < m; i++) { int row = scanner.nextInt(), x = scanner.nextInt(), y = scanner.nextInt(); g[row][x][y][0 ] = scanner.nextInt(); g[row][x][y][1 ] = scanner.nextInt(); g[row][x][y][2 ] = scanner.nextInt(); } C = scanner.nextInt(); D = scanner.nextInt(); for (int r = 1 ; r <= grid; r++) { for (int c = 1 ; c <= grid; c++) { boolean [][][] booleans = new boolean [maxCeng + 2 ][grid+1 ][grid+1 ]; booleans[1 ][r][c] = true ; int [] counts = new int [maxCeng + 2 ]; Arrays.fill(counts, 1 ); path.add(new int []{1 , r, c}); dfs(g, new int []{r, c}, A, 0 , booleans, counts, 1 ); path.remove(path.size() - 1 ); } } System.out.println(ans); } static int [][] dir = new int [][]{{1 , 0 }, {-1 , 0 }, {0 , 1 }, {0 , -1 }}; static boolean chance = true ; static int ans = 0 ; static int index = 0 ; static List<int []> path = new ArrayList <>(); public static void dfs (int [][][][] g, int [] cur, int remainA, int totalCoin, boolean [][][] visited, int [] visitedCount, int ceng) { if (ceng > maxCeng) { return ; } int x = cur[0 ], y = cur[1 ]; int monA = g[ceng][x][y][0 ]; int monB = g[ceng][x][y][1 ]; int coin = g[ceng][x][y][2 ]; int status = 0 ; int num = B == 0 ? 0 : (int )Math.ceil(monA * 1.0 / B); if (remainA > monB * num) { status = 1 ; } else if (chance && totalCoin >= D && remainA + A / 2 > monB * num) { chance = false ; status = 2 ; } if (status == 0 ) { return ; } ans = Math.max(ans, totalCoin + coin - (status == 2 ? D : 0 )); if (visitedCount[ceng] == grid * grid) { ceng += 1 ; for (int r = 1 ; r <= grid; r++) { for (int c = 1 ; c <= grid; c++) { path.add(new int []{ceng, r, c}); visited[ceng][r][c] = true ; dfs(g, new int []{r, c}, remainA - monB * num + (status == 2 ? A / 2 : 0 ), totalCoin + coin - (status == 2 ? D : 0 ) + C, visited, visitedCount, ceng); path.remove(path.size() - 1 ); } } ceng -= 1 ; } for (int i = 0 ; i < 4 ; i++) { int newX = dir[i][0 ] + x, newY = dir[i][1 ] + y; if (newX >= 1 && newX <= grid && newY >= 1 && newY <= grid && !visited[ceng][newX][newY]) { visited[ceng][newX][newY] = true ; visitedCount[ceng] += 1 ; path.add(new int []{ceng, newX, newY}); dfs(g, new int []{newX, newY}, remainA - monB * num + (status == 2 ? A / 2 : 0 ), totalCoin + coin - (status == 2 ? D : 0 ), visited, visitedCount, ceng); visitedCount[ceng] -= 1 ; visited[ceng][newX][newY] = false ; path.remove(path.size()-1 ); } } if (status == 2 ) { chance = true ; } } }
随便放的几个 美团,合法的三元组
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 import java.util.*;public class ValidThreeTuple { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = Integer.parseInt(scanner.nextLine()); int [] nums = Arrays.stream(scanner.nextLine().split(" " )).mapToInt(Integer::valueOf).toArray(); Map<Integer, Integer> map = new HashMap <>(); map.put(nums[0 ], 1 ); long ans = 0L ; for (int j = 1 ; j < n; j++) { for (int k = j+1 ; k < n; k++) { int sum = 3 * nums[j] - nums[k]; ans += map.getOrDefault(sum, 0 ); } map.put(nums[j], map.getOrDefault(nums[j], 0 ) + 1 ); } System.out.println(ans); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int findPairs (int [] nums, int k) { Set<Integer> visited = new HashSet <Integer>(); Set<Integer> res = new HashSet <Integer>(); for (int num : nums) { if (visited.contains(num - k)) { res.add(num - k); } if (visited.contains(num + k)) { res.add(num); } visited.add(num); } return res.size(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int findPairs (int [] nums, int k) { Set<Integer> visited = new HashSet <Integer>(); Set<Integer> res = new HashSet <Integer>(); for (int num : nums) { if (visited.contains(num - k)) { res.add(num - k); } if (visited.contains(num + k)) { res.add(num); } visited.add(num); } return res.size(); } }
特别注意treemap的ans比较中的问题,-1和1是等于0的,但是他们是两个不同的元素,需要区分开来
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 class Solution { public boolean canReorderDoubled (int [] arr) { Map<Integer, Integer> map = new TreeMap <>((a,b)->Math.abs(a)==Math.abs(b) ? a-b : Math.abs(a)-Math.abs(b)); for (int num : arr) { map.put(num, map.getOrDefault(num, 0 ) + 1 ); } if (map.getOrDefault(0 , 0 ) % 2 != 0 ) { return false ; } map.remove(0 ); for (Integer key : map.keySet()) { int value = map.getOrDefault(key, 0 ); int value2 = map.getOrDefault(key * 2 , 0 ); if (value2 < value) { return false ; } if (value2 != 0 ) { map.put(key * 2 , value2 - value); } } return true ; } }