【笔经】【bilibili】火速，刚做完就来了
选择题
知道前序中序求后序
tcp套接字哪个函数不会产生阻塞？bind
Docker架构的底层技术？不会
基本忘了，数据结构，数据库，操作系统，网络，组成原理都有吧，30道题，内容很多。
编程
1.给4个数，求是否满足24点。输入{7,2,1,10}，输出true，因为7*2+1*10=24
用dfs来写，把4个数“压缩”成3个数，依次类推，判断最后arr[0]是否是24，AC了。
public boolean Game24Points (int[] arr) {
// write code here
if(arr.length == 1 && arr[0] == 24){
return true;
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if(i == j){
continue;
}
int[] temp = new int[arr.length-1];
int k = 0, l = 0;
for (; l < arr.length; l++) {
if(l != i && l != j){
temp[k] = arr[l];
k++;
}
}
temp[k] = arr[i] + arr[j];
if(Game24Points(temp)) return true;
temp[k] = arr[i] - arr[j];
if(Game24Points(temp)) return true;
temp[k] = arr[i] * arr[j];
if(Game24Points(temp)) return true;
if(arr[j] != 0)
temp[k] = arr[i] / arr[j];
if(Game24Points(temp)) return true;
}
}
return false;
} 2.判断括号是否匹配，好像之前做过了，经常出现的一道题目 用栈来做，如果匹配就弹出，最后判断栈是否为空。过了。
public boolean IsValidExp (String s) {
// write code here
if(s == null || s.equals("")){
return true;
}
HashMap<Character,Character> m = new HashMap<Character, Character>();
Stack<Character> st = new Stack<Character>();
m.put(')','(');
m.put(']','[');
m.put('}','{');
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(!m.containsKey(c)) st.add(c);
else{
if(st.size() == 0) return false;
Character t = st.pop();
if(m.get(c) != t) return false;
}
}
return (st.empty() ? true : false);
} 3.有1,4,16,64四种面额硬币和1024元的纸币，用纸币买了N元的东西N<=1024，求最少找回多少硬币
又双叒叕是背包，考了也有6,7场了，基本每场固定背包
，100%
，100% 找出转移方程：是否花这枚硬币。
public static int GetCoinCount (int N) {
// write code here
N = 1024 - N;
int[] arr = {1, 4, 16, 64};
int[] dp = new int[N+1];
Arrays.fill(dp, N+1);
dp[0] = 0;
for (int i = 0; i <= N ; i++) {
for (int j = 0; j < 4; j++) {
if(i - arr[j] >= 0){
dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
}
}
}
return dp[N];
}