文章目錄
- 整數反轉
- 題幹
- 我的思路與代碼
- 解析
- 踩坑與收獲
- 回文數
- 題幹
- 我的思路與代碼
- 解析
- 總結與收獲
- 羅馬數字轉整數
- 題幹
- 我的思路
- 解析
- 最長公共字首
- 題幹
- 我的思路與代碼
- 解析
- 有效的括号
- 題幹
- 我的思路與代碼
- 解析
整數反轉
題幹
給出一個 32 位的有符号整數，你需要将這個整數中每位上的數字進行反轉。
假設我們的環境隻能存儲得下 32 位的有符号整數，則其數值範圍為 [−231, 231 − 1]。請根據這個假設，如果反轉後整數溢出那麼就傳回 0。
我的思路與代碼
class Solution {
public int reverse(int x) {
//拿到幾位數n，然後拿出來一個尾巴，跟n計算一下。
//需要考慮正負，最後一位是0
//處理正負
boolean isLowerThanZero = false;
if (x<0) {
isLowerThanZero = true;
x = -x;
}
//用棧來存放資料
Stack stack = new Stack();
while(x != 0){
stack.push(x%10);
x = x/10;
}
//下面這段代碼是從棧裡拿出來資料組裝成想要的樣子 123 -》 321
int result = 0;
int tenTimes = 1;
while(!stack.empty()){
result = result + (int)stack.pop()*tenTimes;
tenTimes *= 10;
}
//考慮整數溢出的情況，這部分代碼有問題一直沒調出來
int max = (2<<31) -1 ;
if(result > 2147483647){
return 0;
}
//如果是負數還原
if(isLowerThanZero){
result = -result;
}
return result;
}
} 廢了很多功夫，最終沒做出來。指數運算與溢出的處理，超出了腦容量了。處理的不是很好。做的過程中很努力的在避開循環了，但是還是做的不好。
解析
class Solution {
public int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
rev = rev * 10 + pop;
}
return rev;
}
} 
踩坑與收獲
- if條件判斷，遇到多個與或的情況，要用括号明确的标示出優先級。要不就容易不按照預想的進行。
- int的max與min，已經在Integer對象中定義出來了，不用自己用2去移位了。
回文數
題幹
判斷一個整數是否是回文數。回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。
我的思路與代碼
回文數無非就是頭尾對應位置的數是一樣的，就想着轉化為字元串去比對。
過程中需要注意，字元串最後一個是str.length()-1。跟數組一樣，到不了length，是從0開始的。
class Solution {
public boolean isPalindrome(int x) {
//轉換成字元串
String str = x + "";
boolean result = true;
for (int i = 0; i < str.length()/2; i++) {
if(str.charAt(i) != str.charAt(str.length()-1-i)){
result = false;
}
}
return result;
}
} 解析
public class Solution {
public bool IsPalindrome(int x) {
// 特殊情況：
// 如上所述，當 x < 0 時，x 不是回文數。
// 同樣地，如果數字的最後一位是 0，為了使該數字為回文，
// 則其第一位數字也應該是 0
// 隻有 0 滿足這一屬性
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// 當數字長度為奇數時，我們可以通過 revertedNumber/10 去除處于中位的數字。
// 例如，當輸入為 12321 時，在 while 循環的末尾我們可以得到 x = 12，revertedNumber = 123，
// 由于處于中位的數字不影響回文（它總是與自己相等），是以我們可以簡單地将其去除。
return x == revertedNumber || x == revertedNumber/10;
}
} 總結與收獲
- 時空複雜度的計算需要強化一下。
- 如何截取一半的數字？ 一邊截取一邊跟截斷之後的原串比一下。
羅馬數字轉整數
題幹
我的思路
先建立一個羅馬數字與數值對應的字典，然後一個一個字元解析之後累加。
針對特殊處理的字元，确定之後，用負數的形式進行特殊的負數累加。
我認為這個思路沒什麼問題，但是sign那一行報空指針。最後原因是我初始化字典的時候，錯用了雙引号。
最終也可以成功送出。
// 先把字典裝進map裡面
Map<Character,Integer> map = new HashMap<>();
//1
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 result = 0;
for (int i = 0; i < s.length()-1; i++) {
int sign = 1;
if ((s.charAt(i)=='I' ||s.charAt(i)=='X' ||s.charAt(i)=='C') ) {
if(map.get(s.charAt(i))*5 ==map.get(s.charAt(i+1)) ||
map.get(s.charAt(i))*10 ==map.get(s.charAt(i+1))){
sign = -1;
}
}
result+= sign* map.get(s.charAt(i));
}
result+= map.get(s.charAt(s.length()-1));
return result;
} 解析
代碼：
class Solution {
public int romanToInt(String s) {
Map<String, Integer> map = new HashMap<>();
map.put("I", 1);
map.put("IV", 4);
map.put("V", 5);
map.put("IX", 9);
map.put("X", 10);
map.put("XL", 40);
map.put("L", 50);
map.put("XC", 90);
map.put("C", 100);
map.put("CD", 400);
map.put("D", 500);
map.put("CM", 900);
map.put("M", 1000);
int ans = 0;
for(int i = 0;i < s.length();) {
if(i + 1 < s.length() && map.containsKey(s.substring(i, i+2))) {
ans += map.get(s.substring(i, i+2));
i += 2;
} else {
ans += map.get(s.substring(i, i+1));
i ++;
}
}
return ans;
}
} 解析裡面的做法是在哈希表裡面增加一個字元與2個字元。然後利用字元串切割并比對的思路。
根據用的字元的數量移動遊标i，控制一步還是兩步。
這個解法比我想的要更奇妙。
hashmap可以換成switch，可能效率更快。
最長公共字首
題幹
我的思路與代碼
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0){
return "";
}
//1.比較長度 選最小的長度 作為循環的n 拿出來去比
int minLengthIndex = 0;
for (int i = 1; i < strs.length; i++) {
if (strs[i].length()< strs[minLengthIndex].length()) {
minLengthIndex = i;
}
}
String CommonPrefix = "";
for (int i = 0; i < strs[minLengthIndex].length() ; i ++) {
boolean isAdd = true;
for (int j = 0; j < strs.length; j++) {
if (strs[j].charAt(i)!=strs[minLengthIndex].charAt(i)) {
isAdd = false;
break;
}
}
if(isAdd){
CommonPrefix = CommonPrefix + strs[minLengthIndex].charAt(i);
}else {
break;
}
}
return CommonPrefix;
}
} 上來判斷一下特殊情況，空數組。
然後找出最短長度的數組中的元素，作為字元遊标移動的母串。
以最短的那個為目标，對比每一個的每一位，看是不是一樣。
思路很簡單，但是部分測試用例。沒有通過。
後來ide打斷點，我對後面比對的資料沒有做處理，加了isAdd的else判斷之後就能通過了。
解析
這個題，解析有好多。
有效的括号
題幹
給定一個隻包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字元串，判斷字元串是否有效。
有效字元串需滿足：
左括号必須用相同類型的右括号閉合。
左括号必須以正确的順序閉合。
注意空字元串可被認為是有效字元串。
我的思路與代碼
首先想到的就是棧的思想，加一個哈希表做檢索比對。但是代碼最終失敗了。
class Solution {
public boolean isValid(String s) {
//第一想到的就是棧
Stack stack = new Stack();
boolean result = true;
Map<String,String> map = new HashMap<>();
map.put(")","(");
map.put("}","{");
map.put("]","[");
while(s.equals("")){
Character tmp = s.charAt(0);
if (map.containsKey(tmp+"")) {
String returnChar = (String)stack.pop();
if (!returnChar.equals(map.get(tmp+""))) {
result = false;
}
}else{
stack.push(tmp+"");
}
s = s.substring(1);
}
if(!stack.empty()){
result = false;
}
return result;
}
} 解析
class Solution {
// Hash table that takes care of the mappings.
private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read.
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// If the current character is a closing bracket.
if (this.mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#'
char topElement = stack.empty() ? '#' : stack.pop();
// If the mapping for this bracket doesn't match the stack's top element, return false.
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
// If it was an opening bracket, push to the stack.
stack.push(c);
}
}
// If the stack still contains elements, then it is an invalid expression.
return stack.isEmpty();
}
}