【100天算法入門 - 每日三題 - Day3】回文數、羅馬數字轉數字、最大公共前綴

哪 吒 2021-08-15 22:05:22 阅读数:698

本文一共[544]字,预计阅读时长:1分钟~
算法 每日 day3 day 回文

大家好,我是哪吒,一個熱愛編碼的Java工程師,本著“欲速則不達,欲達則欲速”的學習態度,在程序猿這條不歸路上不斷成長,所謂成長,不過是用時間慢慢擦亮你的眼睛,少時看重的,年長後卻視若鴻毛,少時看輕的,年長後卻視若泰山,成長之路,亦是漸漸放下執念,內心歸於平靜的旅程。

也許,我們永遠都不會知道自己能走到何方,遇見何人,最後會變成什麼樣的人,但一定要記住,能讓自己登高的,永遠不是別人的肩膀,而是挑燈夜戰的自己,人生的道路剛剛啟程,當你累了倦了也不要迷茫,回頭看一看,你早已不再是那個年少輕狂的少年。

1、LeetCode 9.回文數

題目

給你一個整數 x ,如果 x 是一個回文整數,返回 true ;否則,返回 false 。

回文數是指正序(從左向右)和倒序(從右向左)讀都是一樣的整數。例如,121 是回文,而 123 不是。

小編菜解

public static boolean isPalindrome(int x) {
int compare = x;
if (x < 0){
return false;
}
int result = 0;
while(x != 0) {
int tmp = result; // 保存計算之前的結果
result = (result * 10) + (x % 10);
x /= 10;
}
if (result == compare) {
return true;
}
return false;
}

so easy,提交通過了。身為小菜的我,對官方大神的解法很好奇,於是,我打開了官方答案,閃瞎我的雙眼,我的解法簡直low爆了。

我的解法會有一個致命的問題,那就是如果反轉後的數字大於int.MAX,我們將遇到整數溢出問題。

思路及算法

為了避免數字反轉可能導致的溢出問題,為什麼不考慮只反轉數字的一半?畢竟,如果該數字是回文,其後半部分反轉後應該與原始數字的前半部分相同。

現在的問題是,我們如何知道反轉數字的比特數已經達到原始數字比特數的一半?

由於整個過程我們不斷將原始數字除以 10,然後給反轉後的數字乘上 10,所以,當原始數字小於或等於反轉後的數字時,就意味著我們已經處理了一半比特數的數字了。

大神解法

public static boolean isPalindrome2(int x) {
//當為負數或為以0結尾的數,反轉肯定不等
if(x < 0 || (x%10 == 0 && x != 0)){
return false;
}
int revert = 0;
//當原始數字小於或等於反轉後的數字時,就意味著我們已經處理了一半比特數的數字了。
while (x > revert){
revert = (revert * 10) + (x % 10);
x /= 10;
}
// 當數字長度為奇數時,我們可以通過 revert/10 去除處於中比特的數字。
// 例如,當輸入為 12321 時,在 while 循環的末尾我們可以得到 x = 12,revert = 123,
// 由於處於中比特的數字不影響回文(它總是與自己相等),所以我們可以簡單地將其去除。
return x == revert || x == revert / 10;
}

2、LeetCode 13.羅馬數字轉數字

題目

羅馬數字包含以下七種字符: I, V, X, LCD 和 M

字符          數值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 羅馬數字 2 寫做 II ,即為兩個並列的 1。12 寫做 XII ,即為 X + II 。 27 寫做  XXVII, 即為 XX + V + II 。

通常情况下,羅馬數字中小的數字在大的數字的右邊。但也存在特例,例如 4 不寫做 IIII,而是 IV。數字 1 在數字 5 的左邊,所錶示的數等於大數 5 减小數 1 得到的數值 4 。同樣地,數字 9 錶示為 IX。這個特殊的規則只適用於以下六種情况:

I 可以放在 V (5) 和 X (10) 的左邊,來錶示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊,來錶示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左邊,來錶示 400 和 900。
給定一個羅馬數字,將其轉換成整數。輸入確保在 1 到 3999 的範圍內。

小編菜解

/**
* 給定一個羅馬數字,將其轉換成整數。輸入確保在 1 到 3999 的範圍內。
*/
public static int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('I',1);
map.put('V',5);
map.put('X',10);
map.put('L',50);
map.put('C',100);
map.put('D',500);
map.put('M',1000);
int ret = 0;
for (int i = 0; i < s.length(); i++) {
int value = map.get(s.charAt(i));
if((i + 1) < s.length() && value < map.get(s.charAt(i + 1))){
ret = ret - value;
}else {
ret = ret + value;
}
}
return ret;
}

無情啊,居然和大神解答的一模一樣,有進步。

3、LeetCode 14.最大公共前綴

題目

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴,返回空字符串 ""

小編菜解

/**
* 編寫一個函數來查找字符串數組中的最長公共前綴。
* 如果不存在公共前綴,返回空字符串 ""。
* 輸入:strs = ["flower","flow","flight"]
* 輸出:"fl"
*/
public static String longestCommonPrefix(String[] strs) {
Integer index = 0;
int suffixNum = 0;
//key為第一比特到最後一比特的下角標,value為對應比特置的值
Map<Integer, Character> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
if(!map.containsKey(index)){
map.put(index, strs[i].charAt(index));
}
if(map.containsKey(index)){
int equalNum = 0;
for (int j = i+1; j < strs.length; j++) {
if(map.get(index) == strs[j].charAt(i)){
equalNum++;
}
}
if(equalNum == strs.length-1){
suffixNum++;
}
}
index++;
}
return strs[0].substring(0,suffixNum);
}

大神解法

public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int length = strs[0].length();
int count = strs.length;
for (int i = 0; i < length; i++) {
char c = strs[0].charAt(i);
for (int j = 1; j < count; j++) {
if (i == strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}

上一篇:【100天算法入門 - 每日三題 - Day2】二分查找、第一個錯誤的版本、搜索插入比特置

往期精彩內容:

Java知識體系總結

【全棧最全Java框架總結】SSH、SSM、Springboot

超詳細的springBoot學習筆記

常見數據結構與算法整理總結

Java設計模式:23種設計模式全面解析

Java面試題總結(附答案)

10萬字208道Java經典面試題總結(附答案,建議收藏)

MySql知識體系總結

Linux知識體系總結

【Vue基礎知識總結 1】Vue入門

Redis知識體系總結

版权声明:本文为[哪 吒]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815220515726E.html