2023暑假实习美团效率部门面试题分享

1.给一个链表，翻转指定区间的数，其他不变，要求原位翻转；

【1,2,3,4,5】2,3

【1,3,2,4,5】

平时喜欢新建一个结果对象，没有怎么写过原位翻转，慌了；

重点：定位m,n,翻转，原来的剩下的不翻转的拼接回去，这个很关键；

当时换了while里没有i++,末尾的也没拼回去。下来又做了，如下：

import java.util.*;
class  ListNode{
    int  val;
    ListNode next;
    ListNode(int i){
        this.val=i;
        this.next=null;
    }
   
    @Override
    public String toString() {
        ListNode p=this;
        List<Integer> res=new ArrayList<>();
        while(p!=null){
            res.add(p.val);
            p=p.next;
        }
        return res.toString();
    }
}
public class Main2 {
    
    private static ListNode reverse(ListNode root,int m,int n){
        ListNode dummy=new ListNode(-1);
        dummy.next=root;
        ListNode pre=dummy;
        ListNode p=root;
        int i=1;
        while(i!=m){
            pre=pre.next;
            p=p.next;
            i++;
        }
        ListNode tail=p;
        while(i<=n){
            ListNode temp=p;
            p=p.next;
            temp.next=pre.next;
            pre.next=temp;
            i++;
        }
        tail.next=p;//拼接回去
        return dummy.next;

    }
    public static ListNode getListNdoe(int[] arr){
        int i=1;
        ListNode temp=new ListNode(arr[0]);
        ListNode p=temp;
        while(i<arr.length){
            p.next=new ListNode(arr[i]);
            p=p.next;
            i++;
        }
        return temp;
    }
    public static void main(String[] args) {
        ListNode root=getListNdoe(new int[]{1,2,3,4,5});
        System.out.println(root.toString());
        ListNode res=reverse(root,1,4);
        System.out.println(res.toString());
    }
}

2.路径求和，求树从根到叶子结点的每一条路径说组成的数的和

1

2 3

12+13=25

当时是回溯里忘了return；开始时没判空。也没加root值。修改如下：

import java.util.*;
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val=val;
        this.left=null;
        this.right=null;
    }
    @Override
    public String toString() {
        // TODO Auto-generated method stub
        if(this==null){
            return "null";
        }
        return String.valueOf(this.val)+this.left.toString()+this.right.toString();
    }
}
public class Main3 {
    static int res=0;
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        root.left.left=new TreeNode(4);
        if(root==null){
            System.out.println(0);
            return;
        }
        StringBuffer sb=new StringBuffer();
        sb.append(String.valueOf(root.val));//开始添加
        trace(root,sb);
        System.out.println(res);
    }
    private static void trace(TreeNode root,StringBuffer sb){
        if(root.left==null && root.right==null){
            res+=Integer.valueOf(sb.toString());
            return;//回溯返回忘了
        }
        List<TreeNode> temp=new ArrayList<>();
        if(root.left!=null){
            temp.add(root.left);
        }
        if(root.right!=null){
            temp.add(root.right);
        }
        for(TreeNode t:temp){
            sb.append(String.valueOf(t.val));
            trace(t, sb);
            sb.deleteCharAt(sb.length()-1);
        }

    }
    
}

 其他的都项目场景题

紧张了，while里i++都忘了。return也没写，同一个文件只有一个piblic class也忘了，题还是简单的