1. 回文系列
- 最長回文子串
class Solution {
public String longestPalindrome(String s) {
/*
最長回文子串，時間復雜度O(n2)
7.22
*/
//雙指針中心擴散，不轉(zhuǎn)換為字符數(shù)組，回文長度為len*2-1
String result = "";
for(int i=0;i<s.length()*2-1;i++){
int left = i/2;
int right = left + i%2;
//while循環(huán)判斷
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
//截取子串長度
String temp = s.substring(left,right+1);
//判斷長度
if(temp.length() > result.length()){
result = temp;
}
left--;
right++;
}
left--;
right++;
}
return result;
}
}
- 回文子串
class Solution {
public int countSubstrings(String s) {
/*
回文子串
7.26
*/
//雙指針中心擴散
if(s.length() == 0){
return 0;
}
int result = 0;
for(int i=0;i<s.length()*2-1;i++){
int left = i/2;
int right = left + i%2;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
result++;
left--;
right++;
}
left--;
right++;
}
return result;
}
}
2. 其他
- 字符串壓縮
class Solution {
public String compressString(String S) {
/*
字符串壓縮
7.27
*/
if(S.length() < 2){
return S;
}
StringBuilder result = new StringBuilder();
char[] str = S.toCharArray();
result.append(str[0]);
int count = 1;
for(int i=1;i<str.length;i++){
if(str[i] == str[i-1]){
count++;
}else{
//添加上一個字符的count和本次的字符
result.append(count).append(str[i]);
count = 1;
}
}
//添加最后一個字符的count
result.append(count);
//判斷長度
if(result.length() >= S.length()){
return S;
}else{
return result.toString();
}
}
}
- 字符串相加
class Solution {
public String addStrings(String num1, String num2) {
/*
字符串相加
7.26
*/
//十進制相加，雙指針指向末尾模仿柱式相加
int left = num1.length()-1;
int right = num2.length()-1;
int carry = 0;
StringBuilder result = new StringBuilder();
while(left >= 0 || right >= 0 || carry != 0){
if(left >= 0){
carry += num1.charAt(left--) - '0';
}
if(right >= 0){
carry += num2.charAt(right--) - '0';
}
result.append(carry%10);
carry /= 10;
}
return result.reverse().toString();
}
}
- 字符串相乘
class Solution {
public String multiply(String num1, String num2) {
/*
字符串相乘
8.1
*/
//參考字符串相加，兩層遍歷，外層為num1，內(nèi)層為num2，使用數(shù)組來存相乘結(jié)果，sum = (result[i+j+1] + n1*n2)，result[i+j+1] = sum%10，result[i+j] += sum/10;
//判斷0
if(num1.equals("0") || num2.equals("0")){
return "0";
}
int[] result = new int[num1.length() + num2.length()];
//倒序遍歷實現(xiàn)柱式相乘
for(int i=num1.length()-1;i>=0;i--){
//提取num1
int n1 = num1.charAt(i) - '0';
for(int j=num2.length()-1;j>=0;j--){
//提取num2
int n2 = num2.charAt(j) - '0';
//相乘
int sum = (result[i+j+1] + n1*n2);
result[i+j+1] = sum%10;
//進位
result[i+j] += sum/10;
}
}
StringBuilder str = new StringBuilder();
for(int i=0;i<result.length;i++){
if(i == 0 && result[i] == 0){
continue;
}
str.append(result[i]);
}
return str.toString();
}
}
3. 筆試題
- 大疆筆試：
C平時最喜歡玩數(shù)字游戲，最近他碰到一道有趣的數(shù)字題，他和他的好朋友打賭，一定能在10分鐘內(nèi)解出這道題，成功完成，小C就可以得到好朋友送他的Switch游戲機啦，你能幫助小C贏得獎品嗎？
題目是這樣的：給定一個非負的、字符串形式的整形數(shù)字，例如“12353789”，字符串的長度也就是整形數(shù)字的位數(shù)不超過10000位，并且字符串不會以0開頭，小C需要挑選出其中K個數(shù)字（K小于字符串的長度）并刪掉他們，使得剩余字符組成新的整數(shù)是最小的。
樣例輸入
71245323308
4
樣例輸出
1223308
輸入樣例二:
1683212
3
輸出樣例二:
1212
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int count = sc.nextInt();
//還有考慮字符串后面有空字符的情況
if(count == 0 || count > str.length() || str == "" || str.trim() == ""){
System.out.println(str);
}
//k不能大于str的長度
if(count >= str.length()){
System.out.println("0");
}
//使用StringBuilder進行delete，先存入str
StringBuilder builder = new StringBuilder(str);
while(count > 0){
int index = 0;
//while循環(huán)排除不用刪的字符：如果后一個字符大于等于當前字符，index++跳過當前
while(index < builder.length()-1 && builder.charAt(index) <= builder.charAt(index+1)){
index++;
}
//排除完之后，刪除前一個
builder.deleteCharAt(index);
count--;
}
//結(jié)果的開頭不能為0，因此builder.charAt(0)=='0'需要全部移除
while(builder.length() != 0 && builder.charAt(0) == '0'){
builder.deleteCharAt(0);
}
System.out.println(builder.toString());
}
}
- 奇安信筆試：編輯和回退：輸入一個字符串，當遇到"undo"時，刪除前一個字符串，當遇到"redo"時，恢復上一個刪除的字符串。沒做出來，只過了20%，貼一個大佬的80%的答案。
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] str = sc.nextLine().split(" ");
//雙棧維護彈出和恢復
Stack<String> redo = new Stack<>();
Stack<String> undo = new Stack<>();
for(int i=0;i<str.length;i++){
//如果str[i]是undo，且redo棧不為空，undo棧存入redo的彈出
if(str[i].equals("undo")){
if(!redo.isEmpty()){
undo.push(redo.pop());
}
//如果str[i]是redo，且undo棧不為空，redo棧存入undo的彈出
}else if(str[i].equals("redo")){
if(!undo.isEmpty()){
redo.push(undo.pop());
}
}else{
redo.push(str[i]);
}
//redo存入
}
String[] temp = new String[redo.size()];
//因為彈出棧頂，所以數(shù)組倒序存入
int index = temp.length-1;
while(!redo.isEmpty()){
temp[index] = redo.pop();
--index;
}
StringBuilder result = new StringBuilder();
for(int i=0;i<temp.length;i++){
result.append(temp[i]+" ");
}
System.out.println(result.toString().trim());
}
}
- 貝殼筆試：回文串構(gòu)造：求一個字符串最少修改多少次能變成回文串
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String len = sc.nextLine();
String str = sc.nextLine();
int result = 0;
//雙指針
int left = 0;
int right = str.length()-1;
while(left <= right){
if(str.charAt(left++) != str.charAt(right--)){
result++;
}
}
System.out.println(result);
}
}
