南昌大学计算机考研机试练习题

南昌大学计专机试练习题（一）

• 1.合并两个有序的单链表
• 2.删除排序链表的重复元素
• 3.环形链表
• 4.链表的中间结点
• 5.两数相加
• 6.删除链表的倒数第N个结点
• 7.合并K个排序列表
• 8.子数组的最大累加和
• 9.子数组的最大累乘积
• 10.子集

1.合并两个有序的单链表

题目描述：给定两个有序单链表的头结点head1和head2，请合并两个有序链表，合并后的链表依然有序，并返回合并后链表的头结点。如0->2->3->7->null，1->3->5->7->9->null。合并后:0->1->2->3->3->5->7->7->9->null
思路：双指针遍历，取结点值较小者链接到新的单链表后面，剩余的接上。而合并三个有序的单链表，只需调用两次合并方法即可。
扩展：如果是无序的呢？可以先将他们排成有序链表再合并

public static Node merge(Node node1, Node node2) {  // 合并两个有序链表if (node1 == null || node2 == null) return node1 == null ? node2 : node1;Node head = node1.data > node2.data ? node2 : node1;Node m = node1.data > node2.data ? node1 : node2;Node n = node1.data > node2.data ? node2.next : node1.next;Node p = head;while (p.next != null) {if (m.data > n.data) {p.next = n;n = n.next;p = p.next;}else {p.next = m;m = m.next;p = p.next;}}p.next = m == null ? n : m;  // 剩余的接上return head;
}
public static Node merge3(Node node1, Node node2, Node node3) {  // 合并三个有序链表return merge(merge(node1, node2), node3);
}
static class Node{int data;Node next;Node(int data){this.data = data;}
}

2.删除排序链表的重复元素

题目描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。如1->1->2->null，输出1->2->null
思路：递归方式。“递”的过程一直到最后一个结点，“归”的过程，先将返回的指针链接到上一个结点（保证不断链），然后判断上一个结点的值和返回结点的值，相等则返回后一个结点，否则返回前一个。
非递归方式。利用两个指针，一个指向新链表的最后一个结点，另一个用作遍历指针，将与最后一个结点值不相等的结点链接上去。

public static Node deleteSameNode(Node head) {  // 递归删除重复结点if (head == null || head.next == null) return head;head.next = deleteSameNode(head.next);return head.data == head.next.data ? head.next : head;
}
public static Node deleteSameNode2(Node head) {  // 非递归删除重复结点if (head == null || head.next == null) return head;Node p = head;Node q = head.next;while(q != null) {if (q.data == p.data) q = q.next;p.next = q;p = p.next;q = q.next;}return head;
}

3.环形链表

题目描述：给定一个链表，判断链表是否有环。如3->2->0->-4，-4再指向2那个结点。输出：有环。
思路：方法一，给结点增加一个访问标志位。
方法二，快慢指针。如果存在环，快指针必定能追上慢指针。

public static boolean isCircle(Node head) {  // 结点增加访问标志判断是否有环if (head == null || head.next == null) return false;while (head != null) {if (head.visited) return true;head.visited = true;head = head.next;}return false;
}
public static boolean isCircle2(Node head) {  // 快慢指针判断是否有环，如果有环，2倍速总能追上1倍速，3,4,5...倍速一样的if (head == null || head.next == null) return false;Node slow = head;Node fast = head.next;while (slow != null && fast != null && fast.next != null) {if (slow == fast) return true;slow = slow.next;fast = fast.next.next;}return false;
}
static class Node{int data;Node next;boolean visited;Node(int data){this.data = data;visited = false;}
}

4.链表的中间结点

题目描述：给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。如1->2->3->4->5->null，返回3那个结点。
思路：快慢指针。

public static Node getMiddleNode (Node head) { // 快慢指针解法if (head == null) return head;Node slow = head;Node fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}

5.两数相加

题目描述：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个结点只能存储一位数字。如果我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。除0之外，这两个数都不会以0开头。如2->4->3->null，5->6->4->null。返回7->0->8->null
思路：方法1：对位相加，保留进位。若有多余的结点，将其与进位相加直至没有多余结点。
方法2：不对齐则补零。其实和方法1差不多，只是实现有些区别。

public static Node sum2(Node node1, Node node2) {Node headPre = new Node(-1);Node p = headPre;int data, over = 0;while (node1 != null && node2 != null) {data = (node1.data + node2.data + over) % 10;over = (node1.data + node2.data + over) / 10;p.next = new Node(data);p = p.next;node1 = node1.next;node2 = node2.next;}while(node1 != null) {data = (node1.data + over) % 10;over = (node1.data + over) / 10;p.next = new Node(data);p = p.next;node1 = node1.next;}while(node2 != null) {data = (node2.data + over) % 10;over = (node2.data + over) / 10;p.next = new Node(data);p = p.next;node2 = node2.next;}if (over != 0) p.next = new Node(over);return headPre.next;
}
public static Node sum22(Node m1, Node n1) {  // 不对齐补零  十进制相加进位只能是1，当然更广泛的进位可以如下计算。这里可以简化为1Node headPre = new Node(-1);Node p = headPre;int data, over = 0;while(m1 != null || n1 != null) {data = 0;if (m1 != null) {data += m1.data;m1 = m1.next;}if (n1 != null) {data += n1.data;n1 = n1.next;}data += over;over = data / 10;data = data % 10;p.next = new Node(data);p = p.next;}if (over > 0) p.next = new Node(over);return headPre.next;
}

6.删除链表的倒数第N个结点

题目描述：给定一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。如1->2->3->4->5->null，n=5，返回2那个结点。
思路：方法1：将链表复制到列表（或数组）里面，利用随机访问特性进行删除。
方法2：双指针解法。先将两个指针设置间隔为n，再同步遍历直至后一个指针先到达最后一个结点为止。

public static Node deleteLastXNode(Node head, int n) {Node p = head;List<Node> nodes = new ArrayList<Node>();while(p != null) {nodes.add(p);p = p.next;}if (n > nodes.size() || n <= 0) return head;if (n == nodes.size()) return head.next;Node temp = nodes.get(nodes.size() - n - 1);temp.next = temp.next.next;return head;
}
public static Node deleteLastXNode2(Node head, int n) {  // 双指针隔n解法if (n <= 0) return head;Node headPre = new Node(0);headPre.next = head;Node p = headPre;Node q = p;for (int i = 1 ; i <= n; i++) {q = q.next;if (q == null) return head;  // n大于链表长度，直接返回头结点}while (q.next != null) {p = p.next;q = q.next;}p.next = p.next.next;return headPre.next;
}

7.合并K个排序列表

题目描述：合并k个排序列表，返回合并后的排序链表。如1->4->5->null，1->3->4->null，2->6->null，返回1->1->2->3->4->4->5->6->null。
思路：利用最小堆优先队列。把链表头结点都放入队列，然后出队一个结点（保证了是队列中值最小的结点），将其链接到新链表后面，然后将该结点的下一个结点入队。重复此步骤直至队列为空。

public static Node merge(Node [] nodes) {if (nodes.length == 0) return null;PriorityQueue<Node> n = new PriorityQueue<>(nodes.length, new Comparator<Node>() {@Overridepublic int compare(Node o1, Node o2) {return o1.data - o2.data;}});for(Node node : nodes) {n.offer(node);}Node head = n.poll();n.offer(head.next);  // offer()入队Node p = head;while (n.peek() != null) {  // peek()查看队列中队首结点。p.next = n.poll();  // poll()出队首结点。p = p.next;if (p.next != null)n.offer(p.next);}return head;
}

8.子数组的最大累加和

题目描述：给定一个数组arr，返回子数组的最大累加和。如：arr=[1,-2,3,5,-2,6,-1]，所有子数组中，[3,5,-2,6]可以累加出最大的和12，故返回12。
思路：注意到如果某个子数组的累加和小于等于0，可以直接不考虑这段子数组。

public static int getMaxCumSum(int a[]) {int sum = 0, max = 0;for (int i = 0 ; i < a.length ; i++) {sum += a[i];if (sum <= 0) sum = 0;max = sum > max ? sum : max;}return max;
}

9.子数组的最大累乘积

题目描述：给定一个double类型的数组arr，其中的元素可正可负可零，返回子数组累乘积的最大乘积。例如arr=[-2.5,4,0,3,0.5,8,-1]，子数组[3,0.5,8]累乘可以获得最大的乘积12，所以返回12。
思路：考虑以arr[i]结尾的子数组（不需要考虑整个子数组具体什么样），它的最大累乘积只有三种情况：1、max * arr[i]（max是以arr[i-1]结尾的子数组的最大累乘积）；2、min * arr[i]（min是以arr[i-1]结尾的子数组的最小累乘积）；3、arr[i]
注：顺便可求最小累乘积

public static double getMaxCumProduct(double a[]) {if (a == null || a.length == 0) return 0;double res = a[0];double min = a[0];double max = a[0];for (int i = 1 ; i < a.length ; i++) {double t1 = max * a[i];double t2 = min * a[i];max = Math.max(Math.max(t1, t2), a[i]);min = Math.min(Math.min(t1, t2), a[i]);res = Math.max(res, max);//res = Math.min(res, min);  // 最小累乘积}return res;
}

10.子集

题目描述：给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。如[1,2,3]，返回[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。
思路：注意到幂集个数为2ⁿ，n为数组元素个数。利用0~2ⁿ-1对应的二进制中1的位置来取数组中的元素。比如nums = [1,2,3]，0的二进制000，什么都不取，为空子集；3的二进制011，取第二和第三个元素，子集为[2,3]；7的二进制111，三个元素都取，子集为[1,2,3]。
方法1是将二进制转成字符串处理，方法二是通过位运算处理。

public static String getDec2Bin(int a, int n) {  //补零String s = "";while (a != 0) {s = a % 2 + s;a /= 2;}while (s.length() < n) {s  = "0" + s;}return s;
}
public static List<List<Integer>> getSubCollection(int a[]){List<List<Integer>> lists = new ArrayList<List<Integer>>();for (int len = 0 ; len < Math.pow(2, a.length) ; len++) {  // 对每个len转成二进制String s = getDec2Bin(len, a.length);List<Integer> list = new ArrayList<Integer>();for (int i = 0; i < s.length() ; i++) {if (s.charAt(i) == '1') {list.add(a[i]);}}lists.add(list);}return lists;
}
public static List<List<Integer>> getSubCollection2(int a[]){  // 位运算List<List<Integer>> lists = new ArrayList<List<Integer>>();lists.add(new ArrayList<Integer>());  // 空集int hash = 1;while (hash < Math.pow(2, a.length)) {  // 1-7   有7种可能List<Integer> list = new ArrayList<Integer>();for (int k = 0 ; k < a.length ; k++) {  // 每种都要对原数组中的数进行测试，看看hash值的二进制形式有几个1（与测试）int c = 1<<k;  // c依次为001 010 100，k值为左移位数，也是将要从原数组a中某个下标为k的数添加到list中。if ((c & hash) != 0) {  // list.add(a[k]);}}lists.add(list);hash++;}return lists;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！