这些大厂笔试题你都见识(被无情鞭挞)过了吗？—— 小红书篇

爱被打了一巴掌 2023-09-28 23:50 4阅读 0赞

**题目链接：**

> 截取部分：  
> [小红书2019\_1][2019_1]  
> [小红书2019\_2][2019_2]

--------------------

### 一.求表达式 f(n)结果末尾0的个数 ###

**题目描述：**

> **输入一个自然数n，求表达式 f(n) = 1!2!3!..n! 的结果末尾有几个连续的0？**

**输入描述：**

> **自然数n**

**输出描述：**

> **f(n)末尾连续的0的个数**

**示例1：**

> **输入：  
> 11  
> 输出：  
> 9**

**个人总结：**

> **规律题。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            if (n < 0) {
        
                System.out.println(0);
                return;
            }
            //dp[i] 表示 1!*2!...*i!的末尾连续0个数
            int[] dp = new int[n + 1];
            int cnt = 0;
            for (int i = 5; i <= n; i++) {
        
                int tmp = i;
                while (tmp % 5 == 0) {
        
                    cnt++;
                    tmp /= 5;
                }
                dp[i] = dp[i - 1] + cnt;
            }
            System.out.println(dp[n]);
        }
    }

--------------------

### 二.每K个一组反转链表 ###

**题目描述：**

> **给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。  
> 说明：  
> 1.你需要自行定义链表结构，将输入的数据保存到你的链表中；  
> 2.你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换；  
> 3.你的算法只能使用常数的额外空间。**

**输入描述：**

> **第一行输入是链表的值  
> 第二行输入是K的值，K是大于或等于1的整数  
> 输入形式为：  
> 1 2 3 4 5  
> 2**

**输出描述：**

> **当 k = 2 时，应当输出:  
> 2 1 4 3 5  
> 当 k = 3 时，应当输出:  
> 3 2 1 4 5  
> 当k=6时，应当输出：  
> 1 2 3 4 5**

**示例1：**

> **输入：  
> 1 2 3 4 5  
> 2  
> 输出：  
> 2 1 4 3 5**

**个人总结：**

> **根据题意要求，先定义链表结点，因为没有说输入多少个数，用数组收集不太方便，所以我们选择使用String类型收集，收集好之后创建链表，然后按照题目要求写k个一组反转链表就行了，处理细节比较多，详细可以看代码。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            int k = sc.nextInt();
            //构造链表
            ListNode head = createList(s);
            //k个一组翻转链表
            head = reverseK(head, k);
            ListNode cur = head;
            while (cur != null) {
        
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
        }
    
        public static ListNode reverseK(ListNode head, int k) {
        
            //定义一个虚拟头节点
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode tail = dummyHead;
            ListNode start = head;
            ListNode end = head;
            int cnt = 1;
            while (end != null) {
        
                if (cnt != k) {
        
                    cnt++;
                    end = end.next;
                } else {
        
                    //记录一下下次遍历的新头节点
                    ListNode newHead = end.next;
                    tail.next = reverse(start, end);
                    //更新尾
                    tail = start;
                    //更新区间
                    start = newHead;
                    end = newHead;
                    cnt = 1;
                }
            }
            if (start != tail) {
        
                tail.next = start;
            }
            return dummyHead.next;
        }
    
        public static ListNode reverse(ListNode start, ListNode end) {
        
            end.next = null;
            ListNode cur = start;
            ListNode pre = null;
            while (cur != null) {
        
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    
        public static ListNode createList(String s) {
        
            ListNode head = new ListNode(-1);
            ListNode tail = head;
            for (int i = 0; i < s.length(); i++) {
        
                char c = s.charAt(i);
                if (c != ' ') {
        
                    tail.next = new ListNode(c - '0');
                    tail = tail.next;
                }
            }
            return head.next;
        }
    }
    
    class ListNode {
        
        int val;
        ListNode next;
    
        public ListNode(int val) {
        
            this.val = val;
            this.next = null;
        }
    }

--------------------

### 三.字符串压缩算法 ###

**题目描述：**

> **输入一串字符，请编写一个字符串压缩程序，将字符串中连续出现的重复字母进行压缩，并输出压缩后的字符串。  
> 例如：  
> aac 压缩为 1ac  
> xxxxyyyyyyzbbb 压缩为 3x5yz2b**

**输入描述：**

> **任意长度字符串**

**输出描述：**

> **压缩后的字符串**

**示例1：**

> **输入例子：  
> xxxxyyyyyyzbbb  
> 输出例子：  
> 3x5yz2b**

**个人思路：**

> **模拟一下**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] agrs) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            StringBuilder sb = new StringBuilder();
            int cnt = 0;
            int n = s.length();
            for (int i = 0; i < n; i++) {
        
                char c = s.charAt(i);
                while (i < n && s.charAt(i) == c) {
        
                    i++;
                    cnt++;
                }
                if (cnt == 1) {
        
                    sb.append(c);
                } else {
        
                    sb.append(cnt - 1).append(c);
                }
                //这步比较关键
                i--;
                cnt = 0;
            }
            System.out.println(sb);
        }
    }

[2019_1]: https://www.nowcoder.com/exam/test/64203200/detail?pid=16546827
[2019_2]: https://www.nowcoder.com/exam/test/64373419/detail?pid=16546833