Java | Python | C++ 机试/手撕技巧
前言
机试如果掌握一定的技巧能够大大减小代码量
或者是面试C++，机试用Python有时候也能节约时间
（数据量一般但处理逻辑麻烦）
避免重复造轮子
如有错误，评论补充
建议点赞
不定时更新
栈、队列、哈希表的实现(基础，防止忘记)
Python
栈：
stack = [] # 创建一个空栈 stack.append(1) # 入栈 stack.pop() # 出栈
队列
from collections import deque queue = deque() # 创建一个空队列 queue.append(1) # 入队 queue.popleft() # 出队
哈希表
hash_map = {} # 创建一个空哈希表
hash_map['key1'] = 'value1' # 添加键值对
hash_map['key1'] # 查询键值对，'value1'
hash_map.pop('key1') # 删除键值对，'value1'
Java:
栈
Stack<Integer> stack = new Stack<Integer>(); // 创建一个空栈 stack.push(1); // 入栈 stack.pop(); // 出栈，
队列
Queue<Integer> queue = new LinkedList<Integer>(); // 创建一个空队列 queue.offer(1); // 入队 queue.poll(); // 出队，1
哈希表
Map<String, String> hash_map = new HashMap<String, String>(); // 创建一个空哈希表
hash_map.put("key1", "value1"); // 添加键值对
hash_map.get("key1"); // 查询键值对，"value1"
hash_map.remove("key1"); // 删除键值对，"value1"
C++:
栈：
stack<int> s; // 创建一个空栈 s.push(1); // 入栈 s.pop(); // 出栈
队列：
queue<int> q; // 创建一个空队列 q.push(1); // 入队 q.pop(); // 出队
哈希表：
unordered_map<string, string> hash_map; // 创建一个空哈希表
hash_map["key1"] = "value1"; // 添加键值对
hash_map["key1"]; // 查询键值对，"value1"
hash_map.erase("key1"); // 删除键值对，返回1
四舍五入输出
Python
#round(1.45, 1) 输出1.4, 底层是“四舍六入五成双”” round(1.45+1e-3, 1) #输出1.5正确
Java
System.out.printf("%.1f", 1.45); //输出1.5 无误
C++
//cout << setprecision(2) << 1.45; （#include <iomanip> 输出1.4错误、
//round() 不支持保留小数
//printf("%3.1f",1.45); 输出1.4错误
//printf("%.1f",1.45); 完全错误，格式不能省略整体的长度(即3位)
printf_s("%.1f",1.45); // 输出1.5 正确
将数组中符合条件的数修改
如把＞n的数改为k
python
my_list = [1, 2, 3, 4, 5, 6] n = 3 k = 10 new_list = [k if x > n else x for x in my_list] #都没有原地修改 #new_list = list(map(lambda x: k if x > n else x, vec)) print(new_list) # [1, 2, 3, 10, 10, 10]
java
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> my_list = new ArrayList<>();
my_list.add(1);
my_list.add(2);
my_list.add(3);
my_list.add(4);
my_list.add(5);
my_list.add(6);
int n = 3;
int k = 10;
List<Integer> new_list = my_list.stream()
.map(x -> x > n ? k : x)
.collect(Collectors.toList());
System.out.println(new_list); // [1, 2, 3, 10, 10, 10]
}
}
C++
for(auto& num : vec){ //&引用原地修改
if(num > n) num = k;
待补充……
附录
- python实现动归或者剪枝难以100%的情况下，可以使用Java替代（一般Java和Python的时空限制为同一档，C/C++自成一档）
- 不算太稀疏的int/char型的map使用数组替换（一般可以new int[1000000]）
- 递归调用的时候使用尾递归，并且先判断再进入避免heap爆炸
- C++的报错信息可能会没有Python和Java的信息明显（具体哪行错误）
- 考试结束前5分钟一定要全部提交一遍，避免同时考试的人太多卡死
- 无需像牛客这种考虑多个用例输入（除非有明显报错）
- 输出题目中的用例(基本没用)
- 一般树、链表等非库内数据结构的题，不会是ACM模式
- 贪心、DFS、动态规划为重要考点，但一般都可以用DFS先暴力拿点分再优化剪枝（需熟悉递归写法，visited数组）
- 最好不要把机试题原封不动的分享出来，因为做题前都会有大前提……
- 手撕代码一般不允许本地ide调试，在线运行的话多用print
- 如果输出为单个数字，可以试着print某些和题目有关联的数字，比如0，输入的大小
- ……
