🔥🔥广发银行笔试
笔试共三部分，第三部分两道算法题，一道进制转换，一道字符串相关。
🍭银行的算法题还算是常规，努努力的话就 AC 了，在此记录一下~
1. 进制转换
给定一个十进制整数 num，和一个进制 system，system 的范围在 2 ~ 36，将 num 转换为指定的进制 system，可用字符 [09] 与 [az] 表示。
示例：
num = 13, system = 12
输出：11
思路：
十进制转二进制可以用取余法，转任意进制同样可以套用二进制的方法。
参考代码（Java）：
public class Solution {
public String convert(int num, int system) {
if (num == 0) return "0";
if (system == 10) return Integer.toString(num);
StringBuilder sb = new StringBuilder();
while (num != 0) {
int a = num % system;
if (a < 10) {
sb.insert(0, Integer.toString(a));
} else {
sb.insert(0, (char) (a - 10 + 'a'));
}
num /= system;
}
return sb.toString();
}
}2. 字符串分割
题目描述：
给定一个字符串 s 与字符串字典数组 dic，请问字符串 s 能否分割成一个或多个字典中的字符串？
示例 1：
s = "helloworld", dic = ["hello", "world"]
输出：true
说明：helloworld 可以分成 hello 与 world。
示例 2：
s = "applepenapple", dic = ["apple", "pen"]
输出：true
说明：helloword 可以分成两个 apple 与一个 pen。
示例 3：
s = "catsandog", dic = ["cats", "sand", "dog"]
输出：false
说明：catsandog 无法用字典中的字符串分割。
思路：
直接想到的方法是遍历字典，然后把字符串中出现的子串替换成空串，最后看一下字符串 s 能不能全被替换掉，也就是 s 最终是空串。
很快写出第一版代码：
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串 需要拆分的字符串
* @param wordDict string字符串一维数组 拆分单词字典
* @return bool布尔型
*/
public boolean wordSplit (String s, String[] wordDict) {
// write code here
StringBuilder sb = new StringBuilder(s);
for (String str : wordDict) {
int idx = sb.indexOf(str);
if (ide != -1)
sb.replace(idx, idx + str.length(), "");
}
return sb.length() == 0;
}
}但是只能通过 66.7% 的样例，因为分割的方式（顺序）不止一种，直接遍历只是其中一种可能的分割方式，所以得利用 DFS 深度优先搜索暴力枚举每一种分割的方式，于是有了下面的代码：
参考代码（Java）：
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串 需要拆分的字符串
* @param wordDict string字符串一维数组 拆分单词字典
* @return bool布尔型
*/
public boolean wordSplit (String s, String[] wordDict) {
// write code here
return dfs(s, wordDict);
}
private boolean dfs(String s, String[] wordDict) {
if (s.length() == 0)
return true;
for (String str : wordDict) {
int idx = s.indexOf(str);
if (idx != -1) {
StringBuilder sb = new StringBuilder(s);
sb.replace(idx, idx + str.length(), "");
if (dfs(sb.toString(), wordDict))
return true;
}
}
return false;
}
}这下终于 AC 了。
🎈鄙人不才，上面的算法题也许并不是最优解，欢迎各位大佬提出宝贵意见。
🎈艰难求职 ing，祝愿跟我一样这个时间还在坚持求职的小伙伴们都能找到满意的工作吧~
