小米2020秋招笔试真题

1、请判断一个链表是否为回文链表

【题目描述】请判断一个链表是否为回文链表

输入: 1->2->2->1 输出: True

输入

数组

输出

True 或者 False

输入样例 

1 2 2 1

输出样例 

True

【解题思路】

链表题。

【参考代码】 

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None&nbs***bsp;head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        fast = slow = q = head
        while fast.next and fast.next.next:#这里快指针的判读条件跟判断环形有一点不同
            fast = fast.next.next
            slow = slow.next
        def reverse_list(head):
            if head is None:
                return head
            cur = head
            pre = None
            nxt = cur.next
            while nxt:
                cur.next = pre
                pre = cur
                cur = nxt
                nxt = nxt.next
            cur.next = pre
            return cur
        p = reverse_list(slow.next)
        while p.next:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return p.val == q.val
 
 
def list2Node(array):
    if not array:
        return None
    head = None
    cur = None
 
    for num in array:
        if not head:
            head = ListNode(num)
            cur = head
        else:
            cur.next = ListNode(num)
            cur = cur.next
    return head
 
 
s = input()
a = []
if s != "":
    for x in s.split():
        a.append(int(x))
head = list2Node(a)
print(Solution().isPalindrome(head))

2、吃薯片

【题目描述】现在有一盒薯片，小米和大米两个人想要吃薯片。每次只能从薯片盒两端拿出一片薯片吃掉，每次拿取薯片吃掉可以获得快乐值a[i], i代表薯片在盒子中的位置。小米先拿，然后大米再从剩余薯片的两端再次取出一片薯片吃掉,……，依次类推直至薯片盒空掉。最终快乐值最大的人获胜。给定一个表示薯片快乐值的数组，预测小米是否会成为赢家（两人快乐值相同时小米赢），假设小米和大米都足够聪明。

输入描述

数组a代表薯片盒内薯片的快乐值

输出描述

Yes/No

Yes 代表小米是快乐值最大的

No 代表小米不是快乐值最大的那个

输入样例 

1 4 2

输出样例 

No

【解题思路】

动态规划维护每个人每轮的最优决策所得到的的值。

【参考代码】 

import java.io.*;
import java.io.File;
import java.util.*;
 
public class Main {
 
    public static boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        dp[n - 1][n - 1] = nums[n - 1];
 
        for (int left = n - 2; left >= 0; left--) {
 
            for (int right = left; right < n; right++) {
 
                if (left == right) {
 
                    dp[left][right] = nums[left];
 
                } else {
 
                    dp[left][right] = Math.max(nums[left] - dp[left + 1][right], nums[right] - dp[left][right - 1]);
 
                }
 
            }
 
        }
 
        return dp[0][nums.length - 1] >= 0;
 
    }
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] token = str.split(" ");
        int[] a = new int[token.length];
        for (int i = 0; i < token.length; i++) {
            a[i] = Integer.valueOf(token[i]);
        }
        boolean ans = PredictTheWinner(a);
        if (ans == true) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

3、玩游戏

【题目描述】《2048》是一款热门的数字游戏。游戏中，每个方块上的数字都有2的幂，数字方块会根据指令整体进行上下左右移动，如果两个数字相同的方块在移动中碰撞，他们就会合成一个新的方块。例如下图为4*4格子的游戏，0表示格子为空，图a为移动前格子中的数字，图b为图a左移后的结果:

问，给定n*n的矩阵M，输出进行左移操作后的矩阵结果。

【解题思路】

将矩阵保存到二维数组，遍历每行相邻元素相等，即累加到前一位，后一位置0，之后将非零元素前移即可。

【参考代码】

import java.util.Scanner;
 
public class Main {
    /*
     * 请完成下面这个函数，实现题目要求的功能 当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^ 开始写代码
     ******************************/