1.“之” 字形打印矩陣

【題目】 給定一個(gè)矩陣matrix， 按照“之” 字形的方式打印這個(gè)矩陣， 例如： 1 2 3 4 5 6 7 8 9 10 11 12“之” 字形打印的結(jié)果為： 1， 2， 5， 9， 6， 3， 4， 7， 10， 11， 8， 12

【要求】 額外空間復(fù)雜度為O(1)。

1.1 分析

1.設(shè)置兩個(gè)點(diǎn)A，B，起始位置如圖：

• A每次向右走，走到最右邊的時(shí)候往下走；
• B每次往下走，走到最下邊的時(shí)候往右走；

A、B的運(yùn)動(dòng)方式可確定對(duì)角線(xiàn)的兩個(gè)端點(diǎn)，如圖：

接著，只要根據(jù)每次A、B的坐標(biāo)，打印這條對(duì)角線(xiàn)即可。

同時(shí)需要設(shè)置一個(gè)boolean值，表示打印對(duì)角線(xiàn)時(shí)是否是根據(jù)從右上往左下打印。

1.2 代碼實(shí)現(xiàn)

package Solution;public class ZhiPrintMatrix {public static void main(String[] args) {int[][] matrix= {{1,2,3,4},{5,6,7,8},{9,10,11,12}};PointCom(matrix);}public static void PointCom(int[][] m) {int ax=0;//Axint ay=0;//Ayint bx=0;//Bxint by=0;//Byint x=m.length-1;//行int y=m[0].length-1;//列boolean fromUp=false;while(ax<=x) {//ay=y說(shuō)明A到了最后一行，即走完了橫也走完了豎EdgePrint(m,ax,ay,bx,by,fromUp);//行號(hào)的變化：當(dāng)a的列數(shù)來(lái)到最后一列，它才往下走，即+1；否則不變ax=ay==y?ax+1:ax;//列號(hào)的變化：當(dāng)a的列號(hào)來(lái)到最后一列之前，一直+1，到最后一列之后就不變ay=ay==y?ay:ay+1;by=bx==x?by+1:by;bx=bx==x?bx:bx+1;fromUp=!fromUp;}}public static void EdgePrint(int[][] m,int ax,int ay,int bx,int by,boolean flag) {if(flag) {//從上到下while(ax<=bx) {System.out.print(m[ax++][ay--]+" ");}}else {while(bx>=ax) {System.out.print(m[bx--][by++]+" ");}}} }

運(yùn)行結(jié)果：

2.在行列都排好序的矩陣中找數(shù)

【題目】 給定一個(gè)有N*M的整型矩陣matrix和一個(gè)整數(shù)K，matrix的每一行和每一列都是排好序的。 實(shí)現(xiàn)一個(gè)函數(shù)， 判斷K是否在matrix中。 例如： 0 1 2 5 2 3 4 7 4 4 4 8 5 7 7 9 如果K為7， 返回true； 如果K為6， 返回false。

【要求】 時(shí)間復(fù)雜度為O(N+M)， 額外空間復(fù)雜度為O(1)。

2.1 分析

2.1.1 方法一：從右上角點(diǎn)開(kāi)始

若K>當(dāng)前節(jié)點(diǎn)，往下；

若K<當(dāng)前節(jié)點(diǎn)，往左；

若越界了都沒(méi)找到，則返回false。

比如找4：

2.1.2 方法二：從左下角開(kāi)始

若K>當(dāng)前節(jié)點(diǎn)，則往右；

若K<當(dāng)前節(jié)點(diǎn)，則往上；

2.2 代碼實(shí)現(xiàn)

package Solution;public class FindValue {public static void main(String[] args) {int[][] matrix= {{0, 1, 2, 5},{ 2, 3, 4, 7}, {4, 4, 4, 8}, {5, 7, 7, 9}};System.out.println("6:"+findValue(matrix,6));System.out.println("7:"+findValue(matrix,7));}public static boolean findValue(int[][] m,int k) {int x=m.length-1;int y=m[0].length-1;//從右上角的點(diǎn)開(kāi)始int i=0;int j=y;while(i<=x&&j>=0) {if(k==m[i][j])return true;else if(k>m[i][j])//k>當(dāng)前值，往下i++;elsej--;}return false;} }

運(yùn)行結(jié)果：

3.打印兩個(gè)有序鏈表的公共部分

【題目】 給定兩個(gè)有序鏈表的頭指針head1和head2， 打印兩個(gè)鏈表的公共部分。

3.1 分析

Merge的過(guò)程中相等的打印即可。

3.2 代碼實(shí)現(xiàn)

package Solution;public class PrintSameValue {public static void main(String[] args) {Node node1 = new Node(2);node1.next = new Node(3);node1.next.next = new Node(5);node1.next.next.next = new Node(6);Node node2 = new Node(1);node2.next = new Node(2);node2.next.next = new Node(5);node2.next.next.next = new Node(7);node2.next.next.next.next = new Node(8);printLinkedList(node1);printLinkedList(node2);printValue(node1, node2);}public static void printValue(Node head1,Node head2) {while(head1!=null&&head2!=null) {if(head1.value==head2.value) {System.out.print(head1.value+" ");head1=head1.next;head2=head2.next;}else if(head1.value>head2.value)head2=head2.next;elsehead1=head1.next;}}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();} }

運(yùn)行結(jié)果：

4.?判斷一個(gè)鏈表是否為回文結(jié)構(gòu)

【題目】 給定一個(gè)鏈表的頭節(jié)點(diǎn)head， 請(qǐng)判斷該鏈表是否為回文結(jié)構(gòu)。

例如： 1->2->1， 返回true。 1->2->2->1， 返回true。15->6->15， 返回true。 1->2->3， 返回false。

進(jìn)階： 如果鏈表長(zhǎng)度為N， 時(shí)間復(fù)雜度達(dá)到O(N)， 額外空間復(fù)雜度達(dá)到O(1)。

鏈表問(wèn)題的最優(yōu)解：往往在乎的是最小的空間復(fù)雜度（和其他題目有所不同）。

4.1 方法一

將鏈表遍歷一遍，值放入棧中。

進(jìn)行第二次遍歷，同時(shí)將遍歷到的節(jié)點(diǎn)值與彈出的棧頂元素相比較，若每一次都相等，則返回true；否則返回false。

4.1.1 代碼實(shí)現(xiàn)

package Solution;import java.util.List; import java.util.Stack;public class IsPalindrome {public static void main(String[] args) {Node head = null;printLinkedList(head);System.out.println(isPalindrome(head) );printLinkedList(head);System.out.println("=========================");head = new Node(1);printLinkedList(head);System.out.println(isPalindrome(head) );printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);printLinkedList(head);System.out.println(isPalindrome(head) );printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(1);printLinkedList(head);System.out.println(isPalindrome(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.println(isPalindrome(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.println(isPalindrome(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.println(isPalindrome(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.println(isPalindrome(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.println(isPalindrome(head) );printLinkedList(head);System.out.println("=========================");}public static boolean isPalindrome(Node head) {if (head == null || head.next == null) {return true;}Stack<Integer> help=new Stack<Integer>();Node newhead=head;while(head!=null) {help.push(head.value);head=head.next;} while(newhead!=null) {if(newhead.value==help.pop())newhead=newhead.next;elsereturn false;}return true;}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();} }

運(yùn)行結(jié)果：

4.2 方法二

兩個(gè)指針：

• 快指針每次走兩步；
• 慢指針每次走一步。

當(dāng)快指針走到末尾的時(shí)候，慢指針基本走到了中間。

然后慢指針繼續(xù)往后走，并將走過(guò)的節(jié)點(diǎn)值壓棧。后續(xù)過(guò)程同方法一。

4.2.1 代碼實(shí)現(xiàn)

package Solution;import java.util.List; import java.util.Stack;public class IsPalindrome {public static boolean isPalindrome(Node head) {//方法二if (head == null || head.next == null) {return true;}Node quick=head;Node slow=head;Stack<Integer> help=new Stack<Integer>();while(quick.next!=null&&quick.next.next!=null) {//可做到元素個(gè)數(shù)為奇數(shù)的時(shí)候來(lái)到重點(diǎn)，偶數(shù)個(gè)數(shù)的時(shí)候來(lái)到中間兩個(gè)的前者quick=quick.next.next;slow=slow.next;}while(slow!=null) {help.push(slow.value);slow=slow.next;}while(!help.isEmpty()) {if(head.value==help.pop())head=head.next;elsereturn false;}return true;}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();} }

4.3 方法三：不用輔助空間

兩個(gè)指針：

• 快指針每次走兩步；
• 慢指針每次走一步。

當(dāng)快指針走到末尾的時(shí)候，慢指針基本走到了中間。

然后將后半部分進(jìn)行逆序。

然后head和slow從各自的頭開(kāi)始往后比較。

最后返回之前再將后半部分逆序回來(lái)。

4.3.1 代碼實(shí)現(xiàn)

package Solution;import java.util.List; import java.util.Stack;public class IsPalindrome {public static boolean isPalindrome(Node head) {//方法三if (head == null || head.next == null) {return true;}Node quick=head;Node slow=head;while(quick.next!=null&&quick.next.next!=null) {quick=quick.next.next;slow=slow.next;}//此時(shí)quick指向的是末尾節(jié)點(diǎn)；slow指向的是中點(diǎn)quick=slow.next;//quick變?yōu)橛野氩糠值牡谝粋€(gè)節(jié)點(diǎn)，實(shí)例中的節(jié)點(diǎn)3后面的節(jié)點(diǎn)2slow.next=null;//中間節(jié)點(diǎn)的next為空Node newhead=null;while(quick!=null) {newhead=quick.next;quick.next=slow;slow=quick;quick=newhead;}newhead=slow;quick=head;//quick是左半邊的頭結(jié)點(diǎn)boolean result=true;while(quick!=null&&slow!=null) {if(quick.value==slow.value) {quick=quick.next;slow=slow.next;}else {//不能返回，右半部分還未還原result=false;break;} }slow=newhead.next;//slow指向倒數(shù)第二個(gè)節(jié)點(diǎn)newhead.next=null;while (slow != null) { // recover list//slow=head;quick=next;newhead=prequick = slow.next;slow.next = newhead;newhead = slow;slow = quick;}return result;}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();} }

?

?

?

總結(jié)

以上是生活随笔為你收集整理的算法练习day9——190327（“之” 字形打印矩阵、在行列都排好序的矩阵中找数、打印两个有序链表的公共部分、判断一个链表是否为回文结构）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。