算法的深入浅出--9.面试基础问题（2）.

矫情吗；* 2021-11-10 03:22 231阅读 0赞

**目录**

一、旋转正方形矩阵

二、反转单向和双向链表

三、“之” 字形打印矩阵

四、旋转打印矩阵

四、判断一个链表是否为回文结构

五、将单向链表按某值划分成左边小、 中间相等、 右边大的形式

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

# 一、旋转正方形矩阵 #

给定一个 整型正方形矩阵matr ix，请把该矩阵调整成顺时针旋转90度的样子。  
(要求\]额外空间复 杂度为0(1)。

public class RotateMatrix {
        public static void rotate(int[][] matrix){
            int tR=0;
            int tC=0;
            int dR=matrix.length-1;
            int dC=matrix[0].length-1;
            while(tR<dR){
                rotateEdge(matrix,tR++,tC++,dR--,dC--);
            }
        }
    
        private static void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
            int times=dC-tC;
            int tmp=0;
            for(int i=0;i!=times;i++){
                tmp=matrix[tR][tC+i];
                matrix[tR][tC + i] = matrix[dR - i][tC];
                matrix[dR - i][tC] = matrix[dR][dC - i];
                matrix[dR][dC - i] = matrix[tR + i][dC];
                matrix[tR + i][dC] = tmp;
            }
            }
        }
    }

# 二、反转单向和双向链表 #

分别实现反转单向链表和反转双向链表的函数。  
【要求】 如果链表长度为N， 时间复杂度要求为O(N)， 额外空间  
复杂度要求为O(1)

package cn.mxl.work.problem;
    
    /**
     * #
     * # 　　　┏┓　　　┏┓
     * # 　　┏┛┻━━━┛┻┓
     * # 　　┃　　　　　　　 ┃
     * # 　　┃　　　━　　　 ┃
     * # 　　┃　┳┛　┗┳　┃
     * # 　　┃　　　　　　　 ┃
     * # 　　┃　　　┻　　　 ┃
     * # 　　┃　　　　　　　 ┃
     * # 　　┗━┓　　　┏━┛Codes are far away from bugs with the animal protecting
     * # 　　　　┃　　　┃    神兽保佑,代码无bug
     * # 　　　　┃　　　┃
     * # 　　　　┃　　　┗━━━┓
     * # 　　　　┃　　　　　 ┣┓
     * # 　　　　┃　　　　 ┏┛
     * # 　　　　┗┓┓┏━┳┓┏┛
     * # 　　　　　┃┫┫　┃┫┫
     * # 　　　　　┗┻┛　┗┻┛
     */
    public class ReverseList {
        public static class Node{
            public int value;
            public Node next;
            public Node(int data){
                this.value=data;
            }
        }
    
        public  static Node reverseList(Node head){
            Node pre=null;
            Node next=null;
            while(head!=null){
                next=head.next;
                head.next=pre;
                pre=head;
                head=next;
            }
            return  pre;
        }
    
        public static class DoubleNode {
            public int value;
            public DoubleNode last;
            public DoubleNode next;
    
            public DoubleNode(int data) {
                this.value = data;
            }
        }
    
        public static DoubleNode reverseList(DoubleNode head) {
            DoubleNode pre = null;
            DoubleNode next = null;
            while (head != null) {
                next = head.next;
                head.next = pre;
                head.last = next;
                pre = head;
                head = next;
            }
            return pre;
        }
    
        public static void printLinkedList(Node head) {
            System.out.print("Linked List: ");
            while (head != null) {
                System.out.print(head.value + " ");
                head = head.next;
            }
            System.out.println();
        }
    
        public static void printDoubleLinkedList(DoubleNode head) {
            System.out.print("Double Linked List: ");
            DoubleNode end = null;
            while (head != null) {
                System.out.print(head.value + " ");
                end = head;
                head = head.next;
            }
            System.out.print("| ");
            while (end != null) {
                System.out.print(end.value + " ");
                end = end.last;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            Node head1 = new Node(1);
            head1.next = new Node(2);
            head1.next.next = new Node(3);
            printLinkedList(head1);
            head1 = reverseList(head1);
            printLinkedList(head1);
    
            DoubleNode head2 = new DoubleNode(1);
            head2.next = new DoubleNode(2);
            head2.next.last = head2;
            head2.next.next = new DoubleNode(3);
            head2.next.next.last = head2.next;
            head2.next.next.next = new DoubleNode(4);
            head2.next.next.next.last = head2.next.next;
            printDoubleLinkedList(head2);
            printDoubleLinkedList(reverseList(head2));
    
        }
    }

# 三、“之” 字形打印矩阵 #

给定一个矩阵matrix， 按照“之” 字形的方式打印这  
个矩阵， 例如： 1 2 3 4 5 6 7 8 9 10 11 12  
“之” 字形打印的结果为： 1， 2， 5， 9， 6， 3， 4， 7， 10， 11，  
8， 12  
【要求】 额外空间复杂度为O(1)。

public class ZigZagPrintMatrix {
        public static void printMatrixZigZag(int[][] matrix) {
            int tR = 0;
            int tC = 0;
            int dR = 0;
            int dC = 0;
            int endR = matrix.length - 1;
            int endC = matrix[0].length - 1;
            boolean fromUp = false;
            while (tR != endR + 1) {
                printLevel(matrix, tR, tC, dR, dC, fromUp);
                tR = tC == endC ? tR + 1 : tR;
                tC = tC == endC ? tC : tC + 1;  
    //上面两个的顺序不能调换
                dC = dR == endR ? dC + 1 : dC;
                dR = dR == endR ? dR : dR + 1;
    //上面两个的顺序不能调换
                fromUp = !fromUp;
            }
            System.out.println();
        }
    
        public static void printLevel(int[][] m, int tR, int tC, int dR, int dC,
                                      boolean f) {
            if (f) {
                while (tR != dR + 1) {
                    System.out.print(m[tR++][tC--] + " ");
                }
            } else {
                while (dR != tR - 1) {
                    System.out.print(m[dR--][dC++] + " ");
                }
            }
        }
    
        public static void main(String[] args) {
            int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
            printMatrixZigZag(matrix);
    
        }
    }

# 四、旋转打印矩阵 #

public class PrintMatrixSpiralOrder {
        public static void spiralOrderPrint(int[][] matrix) {
            int tR = 0;
            int tC = 0;
            int dR = matrix.length - 1;
            int dC = matrix[0].length - 1;
            while (tR <= dR && tC <= dC) {
                printEdge(matrix, tR++, tC++, dR--, dC--);
            }
        }
    
        public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
            if (tR == dR) {
                for (int i = tC; i <= dC; i++) {
                    System.out.print(m[tR][i] + " ");
                }
            } else if (tC == dC) {
                for (int i = tR; i <= dR; i++) {
                    System.out.print(m[i][tC] + " ");
                }
            } else {
                int curC = tC;
                int curR = tR;
                while (curC != dC) {
                    System.out.print(m[tR][curC] + " ");
                    curC++;
                }
                while (curR != dR) {
                    System.out.print(m[curR][dC] + " ");
                    curR++;
                }
                while (curC != tC) {
                    System.out.print(m[dR][curC] + " ");
                    curC--;
                }
                while (curR != tR) {
                    System.out.print(m[curR][tC] + " ");
                    curR--;
                }
            }
        }
    
        public static void main(String[] args) {
            int[][] matrix = {
                    { 1, 2, 3, 4 },
                    { 5, 6, 7, 8 },
                    { 9, 10, 11, 12 },
                    { 13, 14, 15, 16 }
            };
            spiralOrderPrint(matrix);
    
        }
    
    }

# 四、判断一个链表是否为回文结构 #

给定一个链表的头节点head， 请判断该链表是否为回  
文结构。 例如： 1->2->1， 返回true。 1->2->2->1， 返回true。  
15->6->15， 返回true。 1->2->3， 返回false。  
进阶： 如果链表长度为N， 时间复杂度达到O(N)， 额外空间复杂  
度达到O(1)

import java.util.Stack;
    
    public class IsPalindromeList {
        public static class Node {
            public int value;
            public Node next;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        // need n extra space
        public static boolean isPalindrome1(Node head) {
            Stack<Node> stack = new Stack<Node>();
            Node cur = head;
            while (cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
            while (head != null) {
                if (head.value != stack.pop().value) {
                    return false;
                }
                head = head.next;
            }
            return true;
        }
    
        // need n/2 extra space
        public static boolean isPalindrome2(Node head) {
            if (head == null || head.next == null) {
                return true;
            }
            Node right = head.next;
            Node cur = head;
            while (cur.next != null && cur.next.next != null) {
                right = right.next;
                cur = cur.next.next;
            }
            Stack<Node> stack = new Stack<Node>();
            while (right != null) {
                stack.push(right);
                right = right.next;
            }
            while (!stack.isEmpty()) {
                if (head.value != stack.pop().value) {
                    return false;
                }
                head = head.next;
            }
            return true;
        }
    
        // need O(1) extra space
        public static boolean isPalindrome3(Node head) {
            if (head == null || head.next == null) {
                return true;
            }
            Node n1 = head;
            Node n2 = head;
            while (n2.next != null && n2.next.next != null) { // find mid node
                n1 = n1.next; // n1 -> mid
                n2 = n2.next.next; // n2 -> end
            }
            n2 = n1.next; // n2 -> right part first node
            n1.next = null; // mid.next -> null
            Node n3 = null;
            while (n2 != null) { // right part convert
                n3 = n2.next; // n3 -> save next node
                n2.next = n1; // next of right node convert
                n1 = n2; // n1 move
                n2 = n3; // n2 move
            }
            n3 = n1; // n3 -> save last node
            n2 = head;// n2 -> left first node
            boolean res = true;
            while (n1 != null && n2 != null) { // check palindrome
                if (n1.value != n2.value) {
                    res = false;
                    break;
                }
                n1 = n1.next; // left to mid
                n2 = n2.next; // right to mid
            }
            n1 = n3.next;
            n3.next = null;
            while (n1 != null) { // recover list
                n2 = n1.next;
                n1.next = n3;
                n3 = n1;
                n1 = n2;
            }
            return res;
        }
    
        public static void printLinkedList(Node node) {
            System.out.print("Linked List: ");
            while (node != null) {
                System.out.print(node.value + " ");
                node = node.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            Node head = null;
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            head.next.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(2);
            head.next.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            head.next.next.next = new Node(2);
            head.next.next.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
        }
    }

# 五、将单向链表按某值划分成左边小、 中间相等、 右边大的形式 #

给定一个单向链表的头节点head， 节点的值类型是整型， 再给定一个整 数pivot。 实现一个调整链表的函数， 将链表调整为左部分都是值小于 pivot的节点， 中间部分都是值等于pivot的节点， 右部分都是值大于 pivot的节点。除这个要求外， 对调整后的节点顺序没有更多的要求。 例如： 链表9->0->4->5->1， pivot=3。 调整后链表可以是1->0->4->9->5， 也可以是0->1->9->5->4。 总之， 满 足左部分都是小于3的节点， 中间部分都是等于3的节点（本例中这个部分为空） ， 右部分都是大于3的节点即可。 对某部分内部的节点顺序不做 要求。

进阶： 在原问题的要求之上再增加如下两个要求。在左、 中、 右三个部分的内部也做顺序要求， 要求每部分里的节点从左 到右的顺序与原链表中节点的先后次序一致。 例如： 链表9->0->4->5->1， pivot=3。调整后的链表是0->1->9->4->5。 在满足原问题要求的同时， 左部分节点从左到右为0、 1。 在原链表中也 是先出现0， 后出现1；中间部分在本例中为空， 不再讨论； 右部分节点 从左到右为9、 4、 5。 在原链表中也是先出现9， 然后出现4，  
最后出现5。如果链表长度为N， 时间复杂度请达到O(N)， 额外空间复杂度请达到O(1)。

public class SmallerEqualBigger {
        public static class Node {
            public int value;
            public Node next;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static Node listPartition1(Node head, int pivot) {
            if (head == null) {
                return head;
            }
            Node cur = head;
            int i = 0;
            while (cur != null) {
                i++;
                cur = cur.next;
            }
            Node[] nodeArr = new Node[i];
            i = 0;
            cur = head;
            for (i = 0; i != nodeArr.length; i++) {
                nodeArr[i] = cur;
                cur = cur.next;
            }
            arrPartition(nodeArr, pivot);
            for (i = 1; i != nodeArr.length; i++) {
                nodeArr[i - 1].next = nodeArr[i];
            }
            nodeArr[i - 1].next = null;
            return nodeArr[0];
        }
    
        public static void arrPartition(Node[] nodeArr, int pivot) {
            int small = -1;
            int big = nodeArr.length;
            int index = 0;
            while (index != big) {
                if (nodeArr[index].value < pivot) {
                    swap(nodeArr, ++small, index++);
                } else if (nodeArr[index].value == pivot) {
                    index++;
                } else {
                    swap(nodeArr, --big, index);
                }
            }
        }
    
        public static void swap(Node[] nodeArr, int a, int b) {
            Node tmp = nodeArr[a];
            nodeArr[a] = nodeArr[b];
            nodeArr[b] = tmp;
        }
    
        public static Node listPartition2(Node head, int pivot) {
            Node sH = null; // small head
            Node sT = null; // small tail
            Node eH = null; // equal head
            Node eT = null; // equal tail
            Node bH = null; // big head
            Node bT = null; // big tail
            Node next = null; // save next node
            // every node distributed to three lists
            while (head != null) {
                next = head.next;
                head.next = null;
                if (head.value < pivot) {
                    if (sH == null) {
                        sH = head;
                        sT = head;
                    } else {
                        sT.next = head;
                        sT = head;
                    }
                } else if (head.value == pivot) {
                    if (eH == null) {
                        eH = head;
                        eT = head;
                    } else {
                        eT.next = head;
                        eT = head;
                    }
                } else {
                    if (bH == null) {
                        bH = head;
                        bT = head;
                    } else {
                        bT.next = head;
                        bT = head;
                    }
                }
                head = next;
            }
            // small and equal reconnect
            if (sT != null) {
                sT.next = eH;
                eT = eT == null ? sT : eT;
            }
            // all reconnect
            if (eT != null) {
                eT.next = bH;
            }
            return sH != null ? sH : eH != null ? eH : bH;
        }
    
        public static void printLinkedList(Node node) {
            System.out.print("Linked List: ");
            while (node != null) {
                System.out.print(node.value + " ");
                node = node.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            Node head1 = new Node(7);
            head1.next = new Node(9);
            head1.next.next = new Node(1);
            head1.next.next.next = new Node(8);
            head1.next.next.next.next = new Node(5);
            head1.next.next.next.next.next = new Node(2);
            head1.next.next.next.next.next.next = new Node(5);
            printLinkedList(head1);
            // head1 = listPartition1(head1, 4);
            head1 = listPartition2(head1, 5);
            printLinkedList(head1);
    
        }
    }