小米 9.14 笔试
小米笔试，编程题是面试的难度
考试结束后我再回来补充编程题答案哈~
t1:
/*
时间限制： 3000MS
内存限制： 589824KB
题目描述：
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
输入描述
链表节点数。 e.g: 5
依次是链表各节点。 e.g:
1
2
3
4
5
left 开始反转位置。 e.g: 2
right 结束反转位置。e.g: 3
输出描述
翻转后的链表
*/
import java.util.Scanner;
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class ListNode<T> {
public T data;
public ListNode next;
}
class Solution {
/* Write Code Here */
public ListNode<Integer> reverseBetween(ListNode<Integer> head, int left, int right) {
ListNode l1 = new ListNode();
l1.next = head;
if(left == right){
return head;
}
ListNode start = l1;
ListNode b1 = l1;
while(left !=1){
left--;
right--;
b1 = b1.next;
}
left--;right--;
start = b1.next;
//b1 start ... end b2
ListNode end = start;
while(right != 0){
right--;
end = end.next;
}
ListNode b2 = end.next;
ListNode pre = null, next = null;
b1.next = null;
end.next = null;
ListNode curStart = start;
while(start != end){
next = start.next;
start.next = pre;
pre = start;
start = next;
}
end.next = pre;
b1.next = end;
curStart.next = b2;
return head;
}
}
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
ListNode<Integer> res = null;
int head_size = 0;
head_size = in.nextInt();
ListNode<Integer> head = null, head_curr = null;
for(int head_i = 0; head_i < head_size; head_i++) {
int head_item = in.nextInt();
ListNode<Integer> head_temp = new ListNode<Integer>();
head_temp.data = head_item;
head_temp.next = null;
if (head == null) {
head = head_curr = head_temp;
} else {
head_curr.next = head_temp;
head_curr = head_temp;
}
}
if(in.hasNextLine()) {
in.nextLine();
}
int left;
left = Integer.parseInt(in.nextLine().trim());
int right;
right = Integer.parseInt(in.nextLine().trim());
res = new Solution().reverseBetween(head, left, right);
while (res != null) {
System.out.print(String.valueOf(res.data) + " ");
res = res.next;
}
System.out.println();
}
}
t2: 二叉搜索树转换双向链表 时间限制： 3000MS 内存限制： 589824KB 题目描述： 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤val≤1000 要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n) 注意: 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出双向链表，程序会根据你的返回值自动打印输出。也挺水的。处理思路是，如果左树、右树都已经处理成双向链表，怎么去组装。
找左边最后一个节点，和 当前点，和右边的点 组合即可。
注意 如果左树为空，那你返回的链表应该是从当前点开始的。（比如当前cur，如果左树不是空，那整体返回的应该是左树穿起来的那个链表：左-cur-右；如果左树是空，那你如果按照left接，会出现null的next，会报异常，应该返回 cur-右）
package xm.t02;
/*
二叉搜索树转换双向链表
时间限制： 3000MS
内存限制： 589824KB
题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤val≤1000
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
}
public Node() {
}
public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}
class Solution {
/* Write Code Here */
public Node Convert(Node pRootOfTree) {
if(pRootOfTree== null || pRootOfTree.left == null && pRootOfTree.right == null){
return pRootOfTree;
}
Node left = Convert(pRootOfTree.left);
Node right = Convert(pRootOfTree.right);
Node originL = pRootOfTree.left, originR = pRootOfTree.right;
if(left != null){
Node p1 = left;
while (p1.right != null){
p1 = p1.right;
}
p1.right = pRootOfTree;
pRootOfTree.left = p1;
}else{
left = pRootOfTree;
pRootOfTree.left = null;
}
if(right != null){
pRootOfTree.right = right;
right.left = pRootOfTree;
}
return left;
}
}
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
Node res = null;
List<Node> list = new ArrayList<>();
while (in.hasNext()) {
int item = in.nextInt();
if (item == -1) {
list.add(null);
} else {
list.add(new Node(item));
}
}
int len = list.size();
int i = 0;
while (i <= (len - 2) / 2) {
if (2 * i + 1 < len && list.get(i) != null) {
list.get(i).left = list.get(2 * i + 1);
}
if (2 * i + 2 < len && list.get(i) != null) {
list.get(i).right = list.get(2 * i + 2);
}
i++;
}
res = new Solution().Convert(list.get(0));
if (res != null) {
while (res.right != null && res.data != -1) {
System.out.print(String.valueOf(res.data) + " ");
res = res.right;
}
System.out.print(res.data + " ");
while (res.left != null && res.data != -1) {
System.out.print(String.valueOf(res.data) + " ");
res = res.left;
}
System.out.print(res.data);
}
System.out.println();
}
} 
安克创新 Anker公司福利 716人发布