ดูรหัสก่อน
คลาสสาธารณะ Maxhuiwen {โมฆะคงที่สาธารณะหลัก (String [] args) {// todo วิธีการที่สร้างอัตโนมัติ stub String S = "ABB"; Maxhuiwen (s); } // 1 เอาต์พุต palindrome สตริงสาธารณะโมฆะคงที่ maxhuiwen (สตริง s) {// การจัดเก็บความยาวของสตริงความยาว int = s.length (); // ที่เก็บสตริงสตริง palindrome ที่ยาวที่สุด maxstring = ""; // transize substrings ทั้งหมดของสตริงปัจจุบันสำหรับ (int i = 0; i <length; i ++) {สำหรับ (int j = i; j <ความยาว+1; j ++) {สตริง s1 = s.substring (i, j); // ถ้าสตริงปัจจุบันเป็นสตริง palindrome และมากกว่าความยาวของ maxstring ให้แทนที่ maxstring ปัจจุบันถ้า (huiwen (s1) && s1.length ()> maxstring.length ()) {maxstring = s1; } //system.out.println(S1); }} // ถ้าความยาวของ maxstring มากกว่าหรือเท่ากับ 2 หมายความว่ามันเป็นสตริง palindrome ถ้า (maxstring.length ()> = 2) {system.out.println (maxstring); } else {system.out.println ("ไม่มีสตริง palindrome"); }} // 2 ตรวจสอบว่าสตริงเป็น palindrome สตริงสาธารณะบูลีนคงที่ huiwen (สตริง s) {ธงบูลีน = true; ความยาว int = s.length (); Char S1 [] = S.ToCharArray (); // ก่อนและหลังให้สำรวจสตริงและเปรียบเทียบสำหรับ (int i = 0, j = ความยาว-1; i <= j; i ++, j-) {ถ้า (s1 [i]! = s1 [j]) {flag = false; }} return flag; -1. คำพิพากษาของศิษยาภิบาล
ตรวจสอบว่าสตริงเป็น palindrome หรือไม่
คำอธิบายปัญหาได้รับสตริงเช่นสตริง t = "มาดาม"; เพื่อตรวจสอบว่าสตริงเป็น palindrome หรือไม่
วิธีการ 1: 1. กำหนดตัวชี้องค์ประกอบสตริงสองตัว (โปรดทราบว่า Java ไม่มีแนวคิดของพอยน์เตอร์), int Right = T.Length ()-1; int ซ้าย = 0;
2. นั่นคือซ้ายเริ่มจากซ้ายขวาเริ่มจากด้านขวาและเปรียบเทียบว่าอักขระที่อ้างอิงนั้นมีค่าเท่ากันในลำดับหรือไม่ หากพวกเขาเท่ากัน, ซ้าย ++, ขวา-; มิฉะนั้นจะถูกส่งคืนโดยตรงไม่ใช่ฉากหลัง
ในขณะที่ (ซ้าย <ขวา) {ถ้า (t.charat (ซ้าย)! = t.charat (ขวา)) ส่งคืน false; ซ้าย ++; ขวา-;} ส่งคืนจริง;รหัส:
/ * * 3: * Palindrome * คำอธิบายปัญหา: Palindrome, Palindrome ภาษาอังกฤษ, หมายถึงสตริงที่อ่านเหมือนกันและผกผันเช่น Madam ฉันรักฉัน * วิธีการ 1: * การวิเคราะห์: ใช้ "พอยน์เตอร์" สองตัวเพื่อสแกนจากจุดเริ่มต้นและจุดสิ้นสุดของสตริงตามลำดับ หากค่าที่ชี้ไปที่ "ตัวชี้" แต่ละตัวเท่ากันนี่คือ palindrome*/ public boolean ispalindrome (สตริง s) {ถ้า (s == null) ส่งคืนเท็จ; int ซ้าย = 0; int right = s.length ()-1; ในขณะที่ (ซ้าย <ขวา) {ถ้า (S.Charat (ซ้าย)! = S.Charat (ขวา)) กลับเท็จ; ซ้าย ++; ขวา--; } return true; - วิธีที่ 2: สตริงสีพาสลาร์เช่น "Madam" หากคุณย้อนกลับพวกเขาทั้งหมดคุณจะยังคงได้รับ "Madam" ของตัวเอง เมื่อเปรียบเทียบทั้งสองสตริงถ้าพวกเขาเท่ากันมันเป็นสีพาสลาร์
1. ใช้ฟังก์ชั่นที่ inverts strings
/** ใช้ฟังก์ชันการผกผันของสตริง*/ สตริงส่วนตัวย้อนกลับ (สตริง str) {string strresult = ""; สำหรับ (int i = str.length ()-1; i> = 0; i-) {strresult+= str.charat (i); } return strresult; } 2. สำหรับสตริงเป้าหมาย s, ย้อนกลับครั้งแรกมัน temp = ย้อนกลับ (s) จากนั้นตัดสิน temp.equals (s)/** กลับสตริงแล้วเปรียบเทียบกับสตริงต้นฉบับ ถ้าเท่ากันมันเป็น palindrome มิฉะนั้นจะไม่ใช่ * ความซับซ้อนของเวลาอัลกอริทึมคือ o (n) */บูลีนสาธารณะ ispalindrome2 (สตริง s) {สตริงอุณหภูมิ = ย้อนกลับ (s) ถ้า (s.equals (temp)) กลับจริง; elsereturn false;}}สอง: วิธีค้นหาสตริง palindromic สูงสุดสำหรับสตริงที่กำหนด
ตัวอย่างเช่นเมื่อได้รับสตริงสตริง t = "Google" วิธีการค้นหาสตริงย่อยที่ยาวที่สุดของ Palindrome "goog"
1. ความคิดที่ง่ายที่สุดและตรงที่สุดคือการค้นหาสายย่อยทั้งหมดของสตริงจากนั้นพิจารณาว่าแต่ละสายย่อยเป็น palindrome บันทึกเปรียบเทียบและค้นหา palindrome ของความยาวสูงสุด * ความซับซ้อนของเวลาอัลกอริทึมคือ o (n^3)
/ * * 4, ค้นหา palindrome substring ที่ยาวที่สุด * คำอธิบายปัญหา: ได้รับสตริง, ค้นหาสายย่อย palindrome ที่ยาวที่สุดในหมู่ย่อยทั้งหมดเช่นสตริง Google, substring ที่ยาวที่สุดคือการวิเคราะห์ GOOG *: 1 ความคิดที่ง่ายที่สุดและตรงที่สุด ความซับซ้อนคือ o (n^3) */ สตริงสาธารณะ LongestPalindRome1 (String S) {string result = null; สตริง tempstring = ""; // กำหนดความยาวของสายย่อย palindrome ที่ยาวที่สุด int max = 0; // ถ่ายโอนองค์ประกอบทั้งหมดในสตริงสำหรับ (int i = 0; i <s.length (); i ++) {// ตัวชี้ตัวชี้ห้อยอาร์เรย์ j เริ่มข้ามไปข้างหน้าจากสตริงสำหรับ (int j = s.length ()-1; j> i; j-) {// palindrome tempstring = s.substr (i, j+1); // ถ้า tempstring เป็น palindrome substring และความยาวของมัน (j-i+1)> สูงสุดถ้า (ispalindrome (tempstring) && (j-i+1)> สูงสุด) {max = j-i+1; result = substring (i, j+1); }}} ผลการส่งคืน; -2. ความคิดที่สองคือการตัดสินตัวละครทุกตัว t [i] ในสตริง
สายย่อยที่มีความยาวสม่ำเสมออยู่ตรงกลาง t [i], t [i+1] เป็น palindrome
เป็นสายย่อยที่มีความยาวคี่อยู่กึ่งกลางที่ t [i] palindrome
สตริงสาธารณะ LongestPalIndRome2 (String T) {String result = NULL; // จัดเก็บความยาวของสตริง palindrome สูงสุด int max = 0; // เดินทางผ่านตัวละครแต่ละตัวและตัดสินสตริงย่อยส่วนขยายพาริตีด้วยตัวละครแต่ละตัวเป็นศูนย์กลางสำหรับ (int i = 0; i <t.length (); i ++) {// กำหนดพอยน์เตอร์ตัวห้อยอาร์เรย์สองตัว int pend = i+1; ในขณะที่ (pstart> = 0 && pend <= (t.length ()-1) && t.charat (pstart) == t.charat (pend)) {pstart--; pend ++; } // ถ้าความยาวของ substring> สูงสุดความยาวของสตริงย่อย palindrome จะถูกเก็บไว้ชั่วคราวเป็นสตริงย่อยย่อยที่ยาวที่สุด = (pend-1)-(pstart+1) -1 = pend-pstart-1 ถ้า (pend-pstart-1> max) result = substring (pstart+1, pend-1+1); } // จาก i เป็นศูนย์กลางพิจารณาว่าลำดับคี่ขยายเป็น palindrome string pStart = i-1; pend = i+1; ในขณะที่ (pstart> = 0 && pend <= (t.length ()-1) && t.charat (pstart) == t.charat (pend)) {pstart--; pend ++; } if (pend-pstart-1> max) {max = pend-pstart-1; result = substrint (t, pstart+1, pend-1+1); }} ผลการส่งคืน; -