|
字串問題是我最喜歡玩的
因為字串問題在我看來任意性很強，好比拼積木，只要符合時間空間復雜度，可以隨便玩
當年我參加第十屆藍橋杯Java B組基本也是靠著字串的優勢拿的獎，盡管當時花的心思最多的是DFS，但是最后就考了一道BFS，最后還沒做出來給我氣的，不過反正結局一樣，也懶得去計較了
|
回文串
問題描述
輸入一個字串（長度在 100 以內），統計其中數字字符出現的次數，
樣例輸入
Ab100cd200
樣例輸出
6
分析與解答
這道題其實很簡單，核心就是判斷數字
查看代碼
import java.util.Scanner;
public class CountOfNum {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
scanner.close();
int num = 0;
for (int i = 0; i < str.length(); i++) {
// 轉換為字符判斷是否有數字
if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
num++;
}
}
System.out.print(num);
}
}
|
統計字符
問題描述
曉曉同學剛剛開始學編程不久，老師打算出一道簡單的題目考考她，有一個字串，有若干個空格，老師想把里面的空格全部替換成為 CODE 這樣的字串，曉曉欣然接受了這個挑戰，這么簡單的問題可難不住曉曉，她知道 Java 里面有直接實作功能的 api，于是很快就實作了：
查看代碼
public String replaceSpace(String str) {
return str.replaceAll(" ","CODE");
}
但是這樣顯示不出她的實力，所以加了一個要求，需要自己去實作陣列插入的功能，思路如下：
- 將字串轉換成為字符陣列，遍歷一次，統計出空格的個數，
- 構建出新的字符陣列，初始化的大小 = 原來的字符陣列長度 + 空格長度 x 3（空格是一個字符，
CODE 是 4 個字符，替換一個空格增加了三個字符），
- 遍歷一次，復制，當不為空格時直接復制，當為空格時，則把
CODE 這幾個字符復制過去，
分析與解答
首先忍不住吐槽這位同學，對自己要求高干嘛為難我們呢，不過他提出來了咱們就得做
大家其實學習演算法的開始就知道廣義的演算法就是拿程式解決問題
所以我們要解決兩個問題
【1】根據空格數建立新陣列
【2】將舊陣列的字符放入新陣列
這道題其實也不難，就是用陣列來做，實際上很多同學會犯的一個錯誤就是構建新陣列的同時再放入字符
其實也不需要，這樣等于就我們一段代碼干兩件事情非常麻煩
一段代碼盡可能做一件事情
查看代碼
public class ReplaceSpaceSolution {
public static void main(String[] args) {
System.out.println(replaceSpace(new StringBuffer("Hello Wolrd !lanqiao")));
}
public static String replaceSpace(StringBuffer str) {
// 轉換成為字符陣列
char[] originChars = str.toString().toCharArray();
int spaceNum = 0;
// 計算出空格的個數
for (int i = 0; i < originChars.length; i++) {
if (originChars[i] == ' ') {
spaceNum++;
}
}
// 新字符陣列的長度
int newCharsLength = originChars.length + 3 * spaceNum;
char[] newChars = new char[newCharsLength];
int newStrIndex = 0;
for (int index = 0; index <= originChars.length - 1; index++) {
if (originChars[index] != ' ') {
// 直接復制
newChars[newStrIndex++] = originChars[index];
} else {
// 空格則需要復制幾個
newChars[newStrIndex++] = 'C';
newChars[newStrIndex++] = 'O';
newChars[newStrIndex++] = 'D';
newChars[newStrIndex++] = 'E';
}
}
// 轉成字串
return new String(newChars);
}
}
|
翻轉單詞
尋找最長回文子串
問題描述
"上海自來水來自海上"，這句話不管是順著讀還是逆著讀，都是一樣的，這就是回文串，相信如何判斷一個字串是回文串，這個問題大家都會（根據中心對稱來判斷即可），現在問題升級了，給出一個字串 s，找到 s 里面包含的最長的回文串，
例子
輸入：s = abddbc
輸出：bd
最直接的解法是我們對字串中的每一段子串進行判斷，也就是 “abdbdc” 可以分為以下的子串：
- 以 a 開頭的：a，ab，abd，abdd，abddb，abddbc，
- 以 b 開頭的：b，bd，bdd，bddb，bddbc，
- 以 d 開頭的：d，dd，ddb，ddbc，
- 以 d 開頭的：d，db，dbc，
- 以 b 開頭的：b，bc，
- 以 c 開頭的：c，
然后對所有的子串進行判定，是否為回文串，程序中記錄最長的回文串即可，
分析與解答
這道題我們需要解決兩件事情
第一件事情是判斷回文子串
第二件事情是遍歷所有的子串
查看代碼
public class LongestPalindrome {
public static void main(String[] args) {
LongestPalindrome longestPalindrome = new LongestPalindrome();
System.out.println(longestPalindrome.longestPalindrome("abdbdc"));
}
// 判斷是否是回文串
public boolean isMatch(String s) {
int len = s.length();
for (int i = 0; i < len / 2; i++) {
// 根據中心判斷是否相等
if (s.charAt(i) != s.charAt(len - i - 1)) {
return false;
}
}
return true;
}
public String longestPalindrome(String s) {
String result = "";
int max = 0;
int len = s.length();
for (int i = 0; i < len; i++)
for (int j = i + 1; j <= len; j++) {
// 判斷每一段子串
String str = s.substring(i, j);
if (isMatch(str) && str.length() > max) {
result = s.substring(i, j);
// 記錄回文串的最大長度
max = Math.max(max, result.length());
}
}
return result;
}
}
|
在黑夜里夢想著光，心中覆寫悲傷，在悲傷里忍受孤獨，空守一絲溫暖，
我的淚水是無底深海，對你的愛已無言，相信無盡的力量，那是真愛永在，
我的信仰是無底深海，澎湃著心中火焰，燃燒無盡的力量，那是忠誠永在
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412980.html
標籤：其他
上一篇：【計理02組06號】十大經典排序演算法【上篇】
下一篇：從遞回到記憶化搜索到動態規劃
