算法解题报告 2020 - 张天宇的博客

人生短短两三年，转眼又到夏天，轮到我上战场了，本篇主要用于笔试面试中编程复盘。

1. 回文素数

题目大意

现有一个正整数，希望去掉这个数中的某一个数字之后可以得到一个回文素数。

现在给两个数，在 [1, 1000000] 之间的满足上述条件的个数。

例如 110 120，他们之间的110、111、112、113、114、115、116、117、118、119去掉最后一位都是11回文素数。120 去掉哪一位都不行。

解题思路

当场暴力，27% 的样例，应该是数据量太大了，计算耗时。

下面题解的代码来源牛客，打表判断素数，然后每次取值计算回文就可以了。

代码

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() {
        // 打表，备忘录，全部初始化给 false
        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) {
        // 123456 要扣掉 4 即 i = 2的时候，pow = 100，12356 = (56 = 123456 % 100) + (12300 = 123456 / 1000 * 100)
        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，否则肯定在第七个后面。

代码

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以内。

输入一串数字，表示每次顾客支付的金额。

输入：5,5,5,10
输出：true,4
输入：10,10
输出：false,1
输入：3,5
输出：false,1// 因为3不够，直接拜拜

解题思路

这道题在现场做题的时候，卡了很久，说越界，我就怎么也找不到越界。后来快交卷时候才发现，数字用，分割的。

开始想现在有多少的零钱就可以了，每次买就更新。但实际上，很有可能钱足够但是没法找零，例如手中有20整钱但是没法找给别人15。

主要还是模拟找零。

代码

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。

输入：
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。

代码

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作为桶容器，按照对向输出添加。从两边往中间靠拢，相遇后离开。

按照要求输出

代码

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作为每一列的桶容器
        ArrayList<Character>[] arrayLists = new ArrayList[n];
        for (int k = 0; k < n; k++) {
            arrayLists[k] = new ArrayList<>();
        }
        int i = 0;
        // 靠拢标准，true表示靠拢
        boolean flag = true;
        // 桶索引
        int l = 0, r = n - 1;
        while (i < str.length()) {
            // 两边相遇，加到桶里，同时置靠拢标志false
            if (l == r) {
                arrayLists[l].add(str.charAt(i++));
                l--;
                r++;
                flag = false;
                continue;
            }
            // 当l=0，表示l已经归位，需要重新靠拢
            if (l == 0) {
                flag = true;
            }
            // 靠拢，因为涉及i++，所以第一行语句执行完，需要判断边界。
            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位于中间的时候，比较一下两个谁最近就好了。

代码

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。

解题思路

暴力搜索。

代码

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);
    }

    /**
     * @description 回溯法，从数组中选出两个数，把运算结果加到数组中
     */
    private boolean solve(List<Double> numbers) {
        if (numbers.size() == 1) {//数组中只剩下一个数的时候判断结果
            return Math.abs(numbers.get(0) - 24) < 1e-6;//看是否与24相等
        }
        //从numbers中取出两个数，把结果放入数组中
        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;//如果没有找到结果，返回false
    }

    /**
     * @description 返回两个数计算得到的结果集
     */
    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 函数解决括号匹配。

代码

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)){
                // 下面要取，先判断一下是不是空，非空直接返回false，防止空指针。
                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，请问他最少会收到多少枚硬币。

解题思路

贪心，因为没限制硬币个数，先找最大硬币，找到不够为止。

代码

int n = sc.nextInt();
int cnum1,cnum2,cnum3,cnum4;
cnum1=(1024-n)/64;                          //64元硬币的数量
cnum2=((1024-n)%64)/16;                     //16元硬币的数量
cnum3=((1024-n)%16)/4;                 //4元硬币的数量
cnum4=(1024-n)-(cnum1*64+cnum2*16+cnum3*4); //1元硬币的数量
System.out.println(cnum1+cnum2+cnum3+cnum4);

10. 连续子区间和

题目大意

小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。

1 2	第一行两个整数c x（0 < c <= 1000000, 0 <= x <= 100000000) 第二行有c个正整数（每个正整数小于等于100)。

输入
3 6
2 4 7
输出
4
2 = 2
4 = 4
7 = 7
2 + 4 = 6
4 + 7 = 11
2 + 4 + 7 = 13

解题思路

滑动窗口。

代码

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 指针指向自己。
不为空，分情况讨论：
1. 要插入的结点值在两个有序结点值[a, b]之间，那么只要满足 a <= insertVal <= b 即可。
2. 由于是循环有序的链表，结点值不会一直上升，到某一个结点的时候，是最大值，但是下一个结点就是最小值了。其大于等于最大值，或者小于等于最小值。例如123450，插入6或者-1时候。
找到插入的位置插入即可。

代码

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;
        }
        // 以下操作未验证，因LeetCode这道题加锁了。
        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 中。

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();
    }
}

两个队列实现栈，弹出元素的时候，把队列中的元素放到另一个队列中，删除最后一个元素。

两个队列始终保持只有一个队列是有数据的。

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值的节点，如：

     8
    / \
   6   12
  /   /   \
2    11    14
         
key = 8 返回11
key = 1 返回2
key = 16 返回NULL

解题思路

代码

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 的解法。

代码

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 来实时记录当前的每个节点的个数，然后更新实时最大值。

代码

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"));
    }
}
// d

来源

1 2020京东秋招编程2
3-5 华为未来星秋招
6 牛客
7-9 哔哩哔哩2020秋招
10-11面经

1. 回文素数

题目大意

解题思路

代码

2. 求数字在数组中第一次出现的位置

题目大意

解题思路

代码

3. 咖啡店买咖啡

题目大意

解题思路

代码

4. 固定步长走迷宫

题目大意

解题思路

代码

5. 按照要求输出

题目大意

解题思路

代码

6. 最近斐波那契数

题目描述

解题思路

代码

7. 24 点

题目大意

解题思路

代码

8. 括号匹配

题目大意

解题思路

代码

9. 找零钱

题目描述

解题思路

代码

10. 连续子区间和

题目大意

解题思路

代码

11. 循环有序的链表插入

题目大意

解题思路

代码

12. 队列和栈的相互实现

题目大意

解题思路

代码

13. 二叉搜索树搜索

题目大意

解题思路

代码

14. 第 k 个全排列

题目大意

解题思路

代码

15. 字符串查找

题目大意

解题思路

代码

来源

标签