人生短短两三年，转眼又到夏天，轮到我上战场了，本篇主要用于笔试面试中编程复盘。
1. 回文素数
题目大意
现有一个正整数，希望去掉这个数中的某一个数字之后可以得到一个回文素数。
现在给两个数，在 [1, 1000000] 之间的满足上述条件的个数。
例如 110 120，他们之间的110、111、112、113、114、115、116、117、118、119去掉最后一位都是11回文素数。120 去掉哪一位都不行。
解题思路
当场暴力，27% 的样例，应该是数据量太大了，计算耗时。
下面题解的代码来源牛客，打表判断素数，然后每次取值计算回文就可以了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| import java.util.Scanner;
public class Main {
final static int maxn = 1000000 + 10;
static boolean[] isp = new boolean[maxn];
static int[] pow = new int[10];
static void init() {
for (int i = 0; i < maxn; i++) {
isp[i] = true;
}
isp[0] = false;
isp[1] = false;
for (int i = 2; i < maxn; i++) {
if (isp[i] == true) {
for (int j = i + i; j < maxn; j += i) {
isp[j] = false;
}
}
}
pow[0] = 1;
for (int i = 1; i < 8; i++) {
pow[i] = pow[i - 1] * 10;
}
}
static int solve(int i, int j) {
int ans = 0;
ans += i % pow[j];
ans += i / pow[j + 1] * pow[j];
return ans;
}
static boolean isr(String num) {
boolean res = true;
int length = num.length();
for (int i = 0; i < length / 2; i++) {
if (num.charAt(i) != num.charAt(length - i - 1)) {
res = false;
break;
}
}
return res;
}
public static void main(String[] args) {
init();
int n, m;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int ans = 0;
for (int i = n; i <= m; i++) {
int length = String.valueOf(i).length();
for (int j = 0; j < length; j++) {
int buf = solve(i, j);
if (isp[buf] && isr(String.valueOf(buf))) {
ans++;
break;
}
}
}
System.out.println(ans);
sc.close();
}
}
|
2. 求数字在数组中第一次出现的位置
题目大意
给定数组 a = { 3,4,5,6,5,6,7,8,9,8}， 这个数组相邻元素之差都为1， 给定数字9， 它在数组中第一次出现的位置下标为8。
解题思路
- 蛮力法，直接for，复杂度为O(n)。
- 跳跃搜索法，首先用数组中第一个元素3和9比较，差值为6，由于相邻两个元素的差值为1，因此9在数组中出现的最早的位置必定为1+6=第七个位置，下标为6。如果数组是递增的，那么数组第七个元素为9，否则肯定在第七个后面。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public int findIndex(int[] a, int val) {
if (a == null || a.length == 0) return -1;
int len = a.length;
int index = 0;
while (index < len) {
if (a[index] == val) {
return index;
} else {
index += Math.abs(val - a[index]);
}
}
return -1;
}
}
|
3. 咖啡店买咖啡
题目大意
每杯咖啡 5 元，每位客户只买一杯咖啡，支付面额为5，10，20，购物之后根据面额给客户找零。开始备用零钱为0。
按照客户购买顺序，返回是否可以正确找零钱以及当前客户顺序号。
如果能正确找零，就返回最后一个客户的顺序号，如果不能找零，返回当前客户的顺序号。客户编号从1开始。
约束，顾客数量限制在100以内。
输入一串数字，表示每次顾客支付的金额。
1
2
3
4
5
6
| 输入：5,5,5,10
输出：true,4
输入：10,10
输出：false,1
输入：3,5
输出：false,1// 因为3不够，直接拜拜
|
解题思路
这道题在现场做题的时候，卡了很久，说越界，我就怎么也找不到越界。后来快交卷时候才发现，数字用，分割的。
开始想现在有多少的零钱就可以了，每次买就更新。但实际上，很有可能钱足够但是没法找零，例如手中有20整钱但是没法找给别人15。
主要还是模拟找零。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| public class Coffe {
private static int five = 0;
private static int ten = 0;
private static int twenty = 0;
public static boolean buy(int givenMoney) {
switch (givenMoney) {
case 5:
five++;
return true;
case 10:
if (five > 0) {
ten++;
five--;
return true;
} else {
return false;
}
case 20:
if (five > 0 && ten > 0) {
five--;
ten--;
twenty++;
return true;
} else {
return false;
}
default:
return false;
}
}
public static void solve(List<Integer> lists) {
for (int i = 0; i < lists.size(); i++) {
if (!buy(lists.get(i))) {
System.out.println("false," + (++i));
return;
}
}
System.out.println("true," + (lists.size()));
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] strs = sc.nextLine().split(",");
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < strs.length; i++) {
arrayList.add(Integer.parseInt(strs[i]));
}
solve(arrayList);
}
}
|
4. 固定步长走迷宫
题目大意
小明要通过一个未完工的矩形路面，只有部分地区铺设了地板砖，判断能否按照固定步长N通过该区域。
输入，第一行为步长S，S>0。
第二行为区域矩阵的行数 M 和列数 N，0 < M,N <= 100。
第三行开始为 M*N 的矩阵，0表示没有地砖，无法下脚，1表示可以落脚。小明从左上角出发，要到右下角，这两个角保证为1。
可以输出1，不可以输出0。
1
2
3
4
5
6
7
8
9
| 输入：
2
3 5
1 0 1 0 0
0 1 1 0 1
0 0 1 0 1
输出：
1
小明可以沿着(0,0)(0,2)(2,2)(2,4)
|
解题思路
这道题其实是一道深搜题目，就是把步长变为了指定的。同时因为瓷砖有些不能过，所以给一个备忘录，记录谁被访问了，谁没有瓷砖不能访问，这里使用了原数组置为2表示访问过了。
找的时候就要找，没访问过的还要有瓷砖的，即1的。当找到右下角的瓷砖的话，就更新找到的flag。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| import java.util.Scanner;
public class Main {
private static int s, m, n;
private static int[][] grid;
public static void dfs(int i, int j) {
if (i >= m || j >= n || grid[i][j] == 2) {
return;
}
grid[i][j] = 2;
if (j + s < n && grid[i][j + s] == 1) {
dfs(i, j + s);
}
if (i + s < m && grid[i + s][j] == 1) {
dfs(i + s, j);
}
if (j >= s && grid[i][j - s] == 1) {
dfs(i, j - s);
}
if (i >= s && grid[i - s][j] == 1) {
dfs(i - s, j);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
s = sc.nextInt();
m = sc.nextInt();
n = sc.nextInt();
grid = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = sc.nextInt();
}
}
dfs(0, 0);
System.out.println(grid[m - 1][n - 1] == 2?1:0);
}
}
|
5. 按照要求输出
题目大意
给定一个字符串以及一个奇数数字表示奇数列，按照从左到右从上到下的顺序排成指定的列数。例如，EVERYTHINGGOESWELL，指定列数为3的情况下，排列为：
然后按列读取拼接字符串，ERHGEEETNOWLVYIGSL。
解题思路
全模拟，使用arraylist作为桶容器，按照对向输出添加。从两边往中间靠拢，相遇后离开。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| import java.util.ArrayList;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String strs[] = str.split(",");
str = strs[0];
int n = Integer.parseInt(strs[1]);
ArrayList<Character>[] arrayLists = new ArrayList[n];
for (int k = 0; k < n; k++) {
arrayLists[k] = new ArrayList<>();
}
int i = 0;
boolean flag = true;
int l = 0, r = n - 1;
while (i < str.length()) {
if (l == r) {
arrayLists[l].add(str.charAt(i++));
l--;
r++;
flag = false;
continue;
}
if (l == 0) {
flag = true;
}
if (flag) {
arrayLists[l++].add(str.charAt(i++));
if (i == str.length()) break;
arrayLists[r--].add(str.charAt(i++));
} else {
arrayLists[l--].add(str.charAt(i++));
if (i == str.length()) break;
arrayLists[r++].add(str.charAt(i++));
}
}
StringBuilder sb = new StringBuilder();
for (int k = 0; k < arrayLists.length; k++) {
for (int j = 0; j < arrayLists[k].size(); j++) {
sb.append(arrayLists[k].get(j));
}
}
System.out.println(sb.toString());
}
}
|
6. 最近斐波那契数
题目描述
找出给定数字最近的斐波那契数。
解题思路
常数空间解斐波那契数的时候，会存放两个值，一个小f1一个大f2，找到n位于中间的时候，比较一下两个谁最近就好了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class Main {
public static void main(String[] args) {
int n = 8;
int f1 = 1;
int f2 = 1;
while (n >= f2) {
int tmp = f1;
f1 = f2;
f2 = f2 + tmp;
}
System.out.println((Math.min(n - f1, f2 - n) == n - f1)? f1: f2);
}
}
|
7. 24 点
题目大意
LeetCode 679，有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
解题思路
暴力搜索。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
public boolean judgePoint24(int[] nums) {
List<Double> numbers = new ArrayList<Double>();
for (int num : nums) {
numbers.add((double) num);
}
return solve(numbers);
}
private boolean solve(List<Double> numbers) {
if (numbers.size() == 1) {
return Math.abs(numbers.get(0) - 24) < 1e-6;
}
for (int i = 0; i < numbers.size(); i++) {
for (int j = 0; j < numbers.size(); j++) {
if (i != j) {
List<Double> nums = new ArrayList<Double>();
for (int k = 0; k < numbers.size(); k++) {
if (k != i && k != j) {
nums.add(numbers.get(k));
}
}
Set<Double> doubles = calculate(numbers.get(i), numbers.get(j));
for (Double aDouble : doubles) {
nums.add(aDouble);
if (solve(nums)) {
return true;
}
nums.remove(nums.size() - 1);
}
}
}
}
return false;
}
private Set<Double> calculate(double a, double b) {
Set<Double> res = new HashSet<Double>();
res.add(a - b);
res.add(b - a);
res.add(a + b);
res.add(a * b);
if (a != 0) {
res.add(b / a);
}
if (b != 0) {
res.add(a / b);
}
return res;
}
}
|
8. 括号匹配
题目大意
判断字符串中的括号是不是符合成对出现的规律。
解题思路
直接用栈判断就可以了，利用 HashMap 的 containsKey 和 value 函数解决括号匹配。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<>();
map.put('{','}');
map.put('(',')');
map.put('[',']');
Stack<Character> stack = new Stack<>();
for (int i = 0; i< s.length(); i++){
char sa = s.charAt(i);
if (map.containsKey(sa)){
stack.push(sa);
continue;
}
if (map.containsValue(sa)){
if (stack.isEmpty()) return false;
char tmp = stack.peek();
if (map.get(tmp) == sa){
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
}
|
9. 找零钱
题目描述
面值1元、4元、16元、64元共计四种硬币，以及面值1024元的纸币，现在A使用1024的纸币购买了一件价值为N的商品，0<N<=1024，请问他最少会收到多少枚硬币。
解题思路
贪心，因为没限制硬币个数，先找最大硬币，找到不够为止。
代码
1
2
3
4
5
6
7
| int n = sc.nextInt();
int cnum1,cnum2,cnum3,cnum4;
cnum1=(1024-n)/64;
cnum2=((1024-n)%64)/16;
cnum3=((1024-n)%16)/4;
cnum4=(1024-n)-(cnum1*64+cnum2*16+cnum3*4);
System.out.println(cnum1+cnum2+cnum3+cnum4);
|
10. 连续子区间和
题目大意
小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。
1
2
| 第一行两个整数c x（0 < c <= 1000000, 0 <= x <= 100000000)
第二行有c个正整数（每个正整数小于等于100)。
|
1
2
3
4
5
6
7
8
9
10
11
| 输入
3 6
2 4 7
输出
4
2 = 2
4 = 4
7 = 7
2 + 4 = 6
4 + 7 = 11
2 + 4 + 7 = 13
|
解题思路
滑动窗口。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| import java.util.Scanner;
class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int c = sc.nextInt();
int x = sc.nextInt();
int[] arr = new int[c];
for (int i = 0; i < c; i++) {
arr[i] = sc.nextInt();
}
System.out.println(solu(arr, x));
}
public static long solu(int[] arr, int x) {
long resu = 0;
int start = 0;
int end = 0;
int sum = arr[start];
while (start < arr.length) {
if (sum >= x) {
resu += (arr.length - end);
sum -= arr[start++];
} else {
end++;
if (end >= arr.length) {
break;
}
sum += arr[end];
}
}
return resu;
}
}
|
11. 循环有序的链表插入
题目大意
在循环有序的链表中插入结点，要求插入结点后，链表仍保持有序且循环。链表为空的时候，插入节点要生成一个新的循环链表。
解题思路
-
链表为空，新建一个节点，将 next 指针指向自己。
-
不为空，分情况讨论：
- 要插入的结点值在两个有序结点值[a, b]之间，那么只要满足 a <= insertVal <= b 即可。
- 由于是循环有序的链表，结点值不会一直上升，到某一个结点的时候，是最大值，但是下一个结点就是最小值了。其大于等于最大值，或者小于等于最小值。例如123450，插入6或者-1时候。
找到插入的位置插入即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
Node* insert(Node* head, int insertVal) {
if (!head) {
head = new Node(insertVal, NULL);
head->next = head;
return head;
}
Node *pre = head, *cur = pre->next;
while (cur != head) {
if (pre->val <= insertVal && cur->val >= insertVal) break;
if (pre->val > cur->val && (pre->val <= insertVal || cur->val >= insertVal)) break;
pre = cur;
cur = cur->next;
}
Node node = new Node(insertVal);
node->next = cur->next;
cur->next = node->next;
node->next = pre->next;
pre->next = node->next;
return head;
}
};
|
12. 队列和栈的相互实现
题目大意
两个栈实现队列，两个队列实现栈。
解题思路
美团面试的题目，写过两个栈实现一个队列，写两个队列实现栈脑子没转过来。
代码
两个栈实现队列，开始时候，每次添加队尾元素到 stack1 中去。
如果需要弹出队头元素，则将 stack1 中的元素弹出并 push 到 stack2 中，再将 stack2 的栈顶元素弹出，即弹出来队头的元素。
如果 stack2 中非空，再在队尾添加元素的时候仍然添加到 stack1 中，再从 stack2 中弹出队头元素。
如果 stack2 为空，弹出队头元素才需要将 stack1 中的元素转移到 stack2 中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.size() == 0) {
while (stack1.size() > 0) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
|
两个队列实现栈，弹出元素的时候，把队列中的元素放到另一个队列中，删除最后一个元素。
两个队列始终保持只有一个队列是有数据的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
public boolean push(int node) {
if (!queue1.isEmpty()) {
return queue1.offer(node);
} else {
return queue2.offer(node);
}
}
public int pop() {
if (queue1.isEmpty() && queue2.isEmpty()) {
throw new RuntimeException("栈为空");
}
if (!queue1.isEmpty() && queue2.isEmpty()) {
while (queue1.size() != 1) {
queue2.offer(queue1.poll());
}
return queue1.poll();
} else {
while (queue2.size() != 1) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
}
|
13. 二叉搜索树搜索
题目大意
在二叉搜索树中找最小的大于某个key值的节点，如：
1
2
3
4
5
6
7
8
9
| 8
/ \
6 12
/ / \
2 11 14
key = 8 返回11
key = 1 返回2
key = 16 返回NULL
|
解题思路
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public TreeNode FindCeiling(TreeNode root, int key) {
TreeNode ceiling = null;
TreeNode cur = root;
while (cur != null) {
if (cur.val <= key) {
cur = cur.right;
} else {
ceiling = cur;
cur = cur.left;
}
}
return ceiling;
}
public TreeNode FindCeilingD(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val <= key) {
return FindCeilingD(root.right, key);
} else {
TreeNode ceiling = FindCeilingD(root.left, key);
return ceiling != null ? ceiling : null;
}
}
}
|
14. 第 k 个全排列
题目大意
输出以 1 开始的 n 个正整数 (1,2,…,n) 的第 k 个排列。
解题思路
套用求下一个排列的算法，增加次数判断，下一个排列可以看 leetcode 31 的解法。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public static void nextPermutation(int[] nums, int count, int target) {
int n = nums.length;
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = n - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1, n - 1);
count++;
if (count == target - 1) {
return;
} else {
nextPermutation(nums, count, target);
}
}
public static void swap(int[] nums, int left, int right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
public static void reverse(int[] nums, int left, int right) {
while (left < right) {
swap(nums, left++, right--);
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
nextPermutation(nums, 0, 5);
for (int num : nums) {
System.out.print(num);
}
}
}
|
15. 字符串查找
题目大意
找出一个字符串中出现次数最多的字符，如果有多个出现次数相同的字符，那就找出最先出现的字符。
解题思路
最开始的思路是先遍历了三次，第一次记录次数，第二次找最大值，第三次返回字符。
这道题可以用 map 来实时记录当前的每个节点的个数，然后更新实时最大值。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| import java.util.HashMap;
import java.util.Map;
class Solution {
public static char serachMaxChar(String str) {
int max = 0;
char resu = str.charAt(0);
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);
if (map.get(str.charAt(i)) > max) {
max = map.get(str.charAt(i));
resu = str.charAt(i);
}
}
return resu;
}
public static void main(String[] args) {
System.out.println(serachMaxChar("a1a2a3bbbcccdddeeefffddda23112211"));
}
}
|
来源
- 1 2020京东秋招编程2
- 3-5 华为未来星秋招
- 6 牛客
- 7-9 哔哩哔哩2020秋招
- 10-11面经
