校招算法笔面试 | 校招笔面试真题-扎金花

import java.util.*;public class Main { // 将字符串转换为牌值数组 static List<Integer> parseCards(String s) { List<Integer> cards = new ArrayList<>(); for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(c >= \'2\' && c <= \'9\') { cards.add(c - \'0\'); } else if(c == \'1\') { if(i + 1 < s.length() && s.charAt(i + 1) == \'0\') {  cards.add(10);  i++; } else {  return new ArrayList<>(); // 非法输入 } } else if(c == \'J\') cards.add(11); else if(c == \'Q\') cards.add(12); else if(c == \'K\') cards.add(13); else if(c == \'A\') cards.add(14); else return new ArrayList<>(); // 非法输入 } Collections.sort(cards); return cards; } static class CardType { int type; int pair; int other; CardType(int type, int pair, int other) { this.type = type; this.pair = pair; this.other = other; } } static CardType getType(List<Integer> cards) { if(cards.get(0).equals(cards.get(1)) && cards.get(1).equals(cards.get(2))) { return new CardType(4, cards.get(0), 0); } if(cards.get(2) - cards.get(1) == 1 && cards.get(1) - cards.get(0) == 1) { return new CardType(3, cards.get(0), 0); } if(cards.get(0).equals(cards.get(1))) { return new CardType(2, cards.get(0), cards.get(2)); } if(cards.get(1).equals(cards.get(2))) { return new CardType(2, cards.get(1), cards.get(0)); } return new CardType(1, 0, 0); } static int compare(List<Integer> a, List<Integer> b) { if(a.isEmpty() || b.isEmpty()) return -2; CardType typeA = getType(a); CardType typeB = getType(b); if(typeA.type != typeB.type) { return typeA.type > typeB.type ? 1 : -1; } if(typeA.type == 4 || typeA.type == 3) { if(a.get(0) > b.get(0)) return 1; if(a.get(0) < b.get(0)) return -1; return 0; } if(typeA.type == 2) { if(typeA.pair != typeB.pair) return typeA.pair > typeB.pair ? 1 : -1; if(typeA.other != typeB.other) return typeA.other > typeB.other ? 1 : -1; return 0; } for(int i = 2; i >= 0; i--) { if(!a.get(i).equals(b.get(i))) { return a.get(i) > b.get(i) ? 1 : -1; } } return 0; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { String s1 = sc.next(); String s2 = sc.next(); List<Integer> cards1 = parseCards(s1); List<Integer> cards2 = parseCards(s2); System.out.println(compare(cards1, cards2)); } }}

def parse_cards(s): cards = [] i = 0 while i < len(s): if \'2\' <= s[i] <= \'9\': cards.append(int(s[i])) elif s[i] == \'1\': if i + 1 < len(s) and s[i + 1] == \'0\': cards.append(10) i += 1 else: return [] # 非法输入 elif s[i] == \'J\': cards.append(11) elif s[i] == \'Q\': cards.append(12) elif s[i] == \'K\': cards.append(13) elif s[i] == \'A\': cards.append(14) else: return [] # 非法输入 i += 1 return sorted(cards)def get_type(cards): if cards[0] == cards[1] == cards[2]: return (4, (cards[0], 0)) if cards[2] - cards[1] == 1 and cards[1] - cards[0] == 1: return (3, (cards[0], 0)) if cards[0] == cards[1]: return (2, (cards[0], cards[2])) if cards[1] == cards[2]: return (2, (cards[1], cards[0])) return (1, (0, 0))def compare(a, b): if not a or not b: return -2 # 非法输入 type_a = get_type(a) type_b = get_type(b) if type_a[0] != type_b[0]: return 1 if type_a[0] > type_b[0] else -1 if type_a[0] in (3, 4): if a[0] > b[0]: return 1 if a[0] < b[0]: return -1 return 0 if type_a[0] == 2: if type_a[1][0] != type_b[1][0]: return 1 if type_a[1][0] > type_b[1][0] else -1 if type_a[1][1] != type_b[1][1]: return 1 if type_a[1][1] > type_b[1][1] else -1 return 0 # 普通牌从大到小比较 for i in range(2, -1, -1): if a[i] != b[i]: return 1 if a[i] > b[i] else -1 return 0while True: try: s1, s2 = input().split() cards1 = parse_cards(s1) cards2 = parse_cards(s2) print(compare(cards1, cards2)) except EOFError: break

算法及复杂度

• 算法：排序 + 模拟
• 时间复杂度：$\mathcal{O}(1)$ - 每次比较只需处理固定数量的牌
• 空间复杂度：$\mathcal{O}(1)$ - 只需要存储固定数量的牌

题目链接

解题思路

这是一个字符串处理和验证问题。具体要求：

1. 验证手机号是否合法，需要满足：
   • 长度为11位数字
   • 前三位为指定的运营商号段
2. 根据号段判断运营商：
   • 电信：133,153,180,181,189
   • 联通：130,131,155,185,186
   • 移动：135,136,150,182,188
3. 输出对应运营商名称，非法号码输出-1

代码

#include #include #include using namespace std;class PhoneValidator {private: // 运营商号段集合 unordered_set<string> telecom {\"133\", \"153\", \"180\", \"181\", \"189\"}; unordered_set<string> unicom {\"130\", \"131\", \"155\", \"185\", \"186\"}; unordered_set<string> mobile {\"135\", \"136\", \"150\", \"182\", \"188\"}; public: string validate(string phone) { // 检查长度 if (phone.length() != 11) { return \"-1\"; } // 获取前三位 string prefix = phone.substr(0, 3); // 判断运营商 if (telecom.count(prefix)) { return \"China Telecom\"; } if (unicom.count(prefix)) { return \"China Unicom\"; } if (mobile.count(prefix)) { return \"China Mobile Communications\"; } return \"-1\"; }};int main() { int t; cin >> t; PhoneValidator validator; while (t--) { string phone; cin >> phone; cout << validator.validate(phone) << endl; } return 0;}

import java.util.*;public class Main { // 运营商号段集合 private static final Set<String> telecom = new HashSet<>(Arrays.asList( \"133\", \"153\", \"180\", \"181\", \"189\")); private static final Set<String> unicom = new HashSet<>(Arrays.asList( \"130\", \"131\", \"155\", \"185\", \"186\")); private static final Set<String> mobile = new HashSet<>(Arrays.asList( \"135\", \"136\", \"150\", \"182\", \"188\")); public static String validate(String phone) { // 检查长度 if (phone.length() != 11) { return \"-1\"; } // 获取前三位 String prefix = phone.substring(0, 3); // 判断运营商 if (telecom.contains(prefix)) { return \"China Telecom\"; } if (unicom.contains(prefix)) { return \"China Unicom\"; } if (mobile.contains(prefix)) { return \"China Mobile Communications\"; } return \"-1\"; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while (t-- > 0) { String phone = sc.next(); System.out.println(validate(phone)); } }}

def validate_phone(phone: str) -> str: # 运营商号段集合 telecom = {\'133\', \'153\', \'180\', \'181\', \'189\'} unicom = {\'130\', \'131\', \'155\', \'185\', \'186\'} mobile = {\'135\', \'136\', \'150\', \'182\', \'188\'} # 检查长度 if len(phone) != 11: return \"-1\" # 获取前三位 prefix = phone[:3] # 判断运营商 if prefix in telecom: return \"China Telecom\" if prefix in unicom: return \"China Unicom\" if prefix in mobile: return \"China Mobile Communications\" return \"-1\"def main(): t = int(input()) for _ in range(t): phone = input().strip() print(validate_phone(phone))if __name__ == \"__main__\": main()

算法及复杂度

• 算法：字符串处理 + 集合查找
• 时间复杂度：$\mathcal{O}(T)$ - $T$ 为测试用例数量，每次验证为 $\mathcal{O}(1)$
• 空间复杂度：$\mathcal{O}(1)$ - 只需要存储固定的号段集合

题目链接

解题思路

这是一个贪心算法问题。需要找到能保证配对成功的最少手套数量，需要考虑单边缺失和双边都有的情况。

关键点：

1. 区分单边缺失和双边都有的情况
2. 记录每边手套的总数和最小值
3. 贪心选择较少的一边
4. 考虑配对成功的必要条件

算法步骤：

1. 处理单边缺失的手套
2. 统计双边都有时的手套数量
3. 计算最优选择策略
4. 确保能够配对成功

代码

class Gloves {public: int findMinimum(int n, vector<int> left, vector<int> right) { int leftSum = 0, leftMin = INT_MAX; int rightSum = 0, rightMin = INT_MAX; int ret = 0; // 遍历所有颜色的手套 for(int i = 0; i < n; ++i) { if(left[i] == 0 || right[i] == 0) { // 单边缺失的情况，必须全部拿走 ret += left[i] + right[i]; } else { // 双边都有的情况，更新总数和最小值 leftMin = min(leftMin, left[i]); rightMin = min(rightMin, right[i]); leftSum += left[i]; rightSum += right[i]; } } // 选择较少的一边，并确保能配对成功 ret += min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1; return ret; }};

public class Gloves { public int findMinimum(int n, int[] left, int[] right) { int leftSum = 0, leftMin = Integer.MAX_VALUE; int rightSum = 0, rightMin = Integer.MAX_VALUE; int ret = 0; // 遍历所有颜色的手套 for(int i = 0; i < n; i++) { if(left[i] == 0 || right[i] == 0) { // 单边缺失的情况，必须全部拿走 ret += left[i] + right[i]; } else { // 双边都有的情况，更新总数和最小值 leftMin = Math.min(leftMin, left[i]); rightMin = Math.min(rightMin, right[i]); leftSum += left[i]; rightSum += right[i]; } } // 选择较少的一边，并确保能配对成功 ret += Math.min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1; return ret; }}

# -*- coding:utf-8 -*-class Gloves: def findMinimum(self, n, left, right): leftSum, leftMin = 0, float(\'inf\') rightSum, rightMin = 0, float(\'inf\') ret = 0 # 遍历所有颜色的手套 for i in range(n): if left[i] == 0 or right[i] == 0: # 单边缺失的情况，必须全部拿走 ret += left[i] + right[i] else: # 双边都有的情况，更新总数和最小值 leftMin = min(leftMin, left[i]) rightMin = min(rightMin, right[i]) leftSum += left[i] rightSum += right[i] # 选择较少的一边，并确保能配对成功 ret += min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1 return ret

算法及复杂度

• 算法：贪心算法
• 时间复杂度：$\mathcal{O}(n)$，只需遍历一次数组
• 空间复杂度：$\mathcal{O}(1)$，只需要常数级额外空间