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，输入的大小
• ……