字节跳动
1. 代码校正
package ZJTD; import java.util.*; /** * @author zzm * @data 2020/5/17 9:04 * 1. 三个同样的字母连在一起,一定是拼写错误,去掉一个的就好啦:比如 helllo -> hello 2. 两对一样的字母(AABB型)连在一起,一定是拼写错误,去掉第二对的一个字母就好啦:比如 helloo -> hello 3. 上面的规则优先“从左到右”匹配,即如果是AABBCC,虽然AABB和BBCC都是错误拼写,应该优先考虑修复AABB,结果为AABCC */ public class StrProof { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); scanner.nextLine(); for (int i = 0; i < n; i++) { String s = scanner.nextLine(); StringBuilder sb = new StringBuilder(s.length()); for (int j = 0; j < s.length(); j++) { if (helper(sb, sb.length(),s.charAt(j))) continue; sb.append(s.charAt(j)); } System.out.println(sb.toString()); } } private static boolean helper(StringBuilder s, int index,char c) { if (index < 2 || c != s.charAt(index - 1)) return false; if (c == s.charAt(index - 2)) return true; if (index >= 3 && s.charAt(index - 3) == s.charAt(index - 2)) return true; return false; } }
2. 选择三个地点,最大间距不超过 D
思路:左右指针l r(r-l>=3),确定一个区间以l 开始的最大区间,此区间总数 为 (r-l)*(r-l-1)/2, 即从 l+1 到 r 选两个出来。
package ZJTD; import java.util.*; /** * @author zzm * @data 2020/5/17 10:06 * 1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。 2. 为了相互照应,我们决定相距最远的两名特工间的距离不超过D。 */ public class LocationSelect { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int len = scanner.nextInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) nums[i] = scanner.nextInt(); scanner.close(); long res = 0; int l = 0, r = 2; while (l < n-2) { while (r < n && nums[r] - nums[l] <= len) r++; if (--r - l +1 >= 3) res += (long)(r - l) * (r - l - 1) / 2; l++; } System.out.println(res%99997867); } }
3. 麻将
- 总共有36张牌,每张牌是1~9。每个数字4张牌。
- 你手里有其中的14张牌,如果这14张牌满足如下条件,即算作和牌
- 14张牌中有2张相同数字的牌,称为雀头。
- 除去上述2张牌,剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌(例如234,567等),刻子的意思是相同数字的3个数字牌(例如111,777)
package ZJTD; import java.util.*; /** * @author zzm * @data 2020/5/17 10:40 */ public class Majiang { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int[] cards = new int[9]; for (int i = 0; i < 13; i++) cards[scanner.nextInt()-1]++; scanner.close(); int[] helpArr = new int[9]; ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 9; i++) { if (cards[i] < 4) { System.arraycopy(cards, 0, helpArr, 0, 9); helpArr[i]++; if (helper(helpArr, false, 14)) list.add(i + 1); } } if (list.isEmpty()) { System.out.println(0); return; } StringBuilder sb = new StringBuilder(); sb.append(list.get(0)); for (int i = 1; i < list.size(); i++) sb.append(" " + list.get(i)); System.out.println(sb.toString()); } private static boolean helper(int[] states, boolean hasHead, int totle) { if (totle == 0) return true; if (!hasHead) { for (int i = 0; i < 9; i++) { if (states[i] >= 2) { states[i] -= 2; if (helper(states, true, totle - 2)) return true; states[i] += 2; } } return false; } else { for (int i = 0; i < 9; i++) { if (states[i] > 0) { if (states[i] >= 3) { states[i] -= 3; if (helper(states, true, totle - 3)) return true; states[i] += 3; } if (i + 2 < 9 && states[i + 1] > 0 && states[i + 2] > 0) { states[i]--; states[i + 1]--; states[i + 2]--; if (helper(states, true, totle - 3)) return true; states[i]++; states[i + 1]++; states[i + 2]++; } } } } return false; } }
4. 找最长的相同特征
package ZJTD; import java.util.*; /** * @author zzm * @data 2020/5/21 8:22 */ public class FeatureSel { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); HashMap<String, Integer> pre = new HashMap<>(); HashMap<String, Integer> now = new HashMap<>(); int max = Integer.MIN_VALUE; for (int i = scanner.nextInt(); i > 0; i--) { for (int j = scanner.nextInt(); j > 0; j--) { for (int k = scanner.nextInt(); k > 0; k--) { String node = scanner.nextInt()+"-"+scanner.nextInt(); now.put(node, 1 + pre.getOrDefault(node, 0)); max = Math.max(now.get(node), max); } pre.clear(); pre.putAll(now); now.clear(); } System.out.println(max); } scanner.close(); } }
5. 最少的车票
小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。由于经费有限,希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销。
以下代码为深度遍历,超时,后续更改
package ZJTD; import java.util.*; /** * @author zzm * @data 2020/5/17 11:00 */ public class Tickets { static int res = Integer.MAX_VALUE; static int[][] tickets; static boolean[] used; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); tickets = new int[n][n]; used = new boolean[n]; used[0] = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { tickets[i][j] = scanner.nextInt(); } } scanner.close(); dfs(0, 1, 0); System.out.println(res); } private static void dfs(int pre, int len, int totle) { if(totle>res) return; for (int i = 1; i < used.length; i++) { if (!used[i]) { if (len == used.length - 1) { totle += tickets[pre][i] + tickets[i][0]; res = Math.min(res, totle); return; } used[i] = true; dfs(i, len + 1, totle + tickets[pre][i]); used[i] = false; } } } }
6. 找零钱
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品,请问最少他会收到多少硬币?
package ZJTD; import java.util.*; /** * @author zzm * @data 2020/5/18 19:40 */ public class ChangeMoney { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = 1024 - scanner.nextInt(); scanner.close(); int res = 0; res += n >> 6; n -= (n >> 6) << 6; res += n >> 4; n -= (n >> 4) << 4; res += n >> 2; n -= (n >> 2) << 2; res += n; System.out.println(res); } }
7. 机器人跳建筑
思路: 每一次跳跃后 E = 2E – H; 从后往前,设最终E=0, 则 每一次往前 E = (E+H +1)/2; 注意:+1 是因为最后可能剩一个而不是刚好能量用尽,即 2E-H = 1
package ZJTD; import java.util.*; /** * @author zzm * @data 2020/5/21 10:13 * 输入描述:第一行输入,表示一共有 N 组数据. * 第二个是 N 个空格分隔的整数,H1, H2, H3, ..., Hn 代表建筑物的高度 * 输出描述:输出一个单独的数表示完成游戏所需的最少单位的初始能量 * 输入例子1: * 5 * 3 4 3 2 4 * 输出例子1: * 4 */ public class RobotsJump { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] h = new int[n]; for (int i = 0; i < n; i++) h[i] = scanner.nextInt(); scanner.close(); int e = 0; for (int i = n - 1; i >= 0; i--) e = (e + h[i] + 1) / 2; System.out.println(e); } }