1. 兩數(shù)之和 ：
題目 ： https://leetcode-cn.com/problems/two-sum/
兩數(shù)之和的O(n)算法
O(n)算法實(shí)現(xiàn)：
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ans = new int[2] ;
Map<Integer,Integer> bt = new HashMap<>() ;
for (int i= 0 ;i <nums.length ;i++){
if(bt.containsKey( target - nums[i]) ){
return new int[]{i, bt.get(target - nums[i])} ;
}
else{
bt.put(nums[i],i) ;
}
}
return ans;
}
}
2. 兩數(shù)相加 ：
題目 ： https://leetcode-cn.com/problems/two-sum/
兩數(shù)相加
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = new ListNode() ;
//邊界情況處理
if(l1 == null && l2 == null) return ans;
if(l1 == null) return l2;
if(l2 == null) return l1;
//開始構(gòu)建ans指向的鏈表柜裸，ans是頭節(jié)點(diǎn)
ListNode current = ans ;
//記錄進(jìn)位數(shù)
int carry = 0 ;
//兩個(gè)鏈表都還有值
while(l1 != null && l2 != null){
int v1 = l1.val ;
int v2 = l2.val ;
ListNode thisNode = new ListNode( (v1 + v2 + carry)%10 ) ;
current.next = thisNode ;
current = current.next;
l1 = l1.next;
l2 = l2.next;
carry = (v1 + v2 + carry)/10 ;
}
//鏈表2有值
while(l2 != null){
int v2 = l2.val;
ListNode thisNode = new ListNode( (v2 + carry)%10 ) ;
current.next = thisNode ;
current = current.next;
l2 = l2.next;
carry = (v2 + carry)/10 ;
}
//鏈表1有值
while(l1 != null){
int v1 = l1.val;
ListNode thisNode = new ListNode( (v1 + carry)%10 ) ;
current.next = thisNode ;
current = current.next;
l1 = l1.next;
carry = (v1 + carry)/10 ;
}
if(carry > 0) {
ListNode thisNode = new ListNode( carry ) ;
current.next = thisNode ;
current = current.next;
}
ans = ans.next ; //注意這一步
return ans;
}
}
3.整數(shù)反轉(zhuǎn) ：
整數(shù)反轉(zhuǎn)思路
class Solution {
public int reverse(int x) {
int ans = 0 ;
while(x != 0){
//如果已經(jīng)達(dá)到了Integer.MAX_VALUE/10的級(jí)別缕陕，那么下個(gè)迭代肯定越界了
if(ans > Integer.MAX_VALUE/10 || ans < -1 * Integer.MAX_VALUE/10)
{
return 0 ;
}
int dig = x % 10 ;
x = x/10 ;
ans = ans * 10 + dig ;
}
return ans ;
}
}
4. 字符串轉(zhuǎn)換整數(shù) (atoi)
題目地址 ： https://leetcode-cn.com/problems/string-to-integer-atoi/
該題是中等難度，我寫出了思路疙挺，但是因?yàn)橐绯鰲l件測(cè)試了很久都沒有通過扛邑，這里溢出時(shí)，需要注意铐然，必須測(cè)試ans 和 Integer.MAX_VALUE/10的大小關(guān)系蔬崩，不能判斷相加結(jié)果與Integer.MAX_VALUE的關(guān)系，因?yàn)橄嗉右绯龊蟛笫睿苯又稻妥兞肆ぱ簟Ｔ擃}還有個(gè)難點(diǎn)桐罕，就是int的最大值是2147483647，如果加完之后等于 2147483646 那就不溢出了死宣，所以這里判斷溢出的條件是：ans > Integer.MAX_VALUE/10 || (ans == Integer.MAX_VALUE/10 && lg > 7)
下邊是完整的代碼 ：
class Solution {
public int myAtoi(String s) {
//去除空格
String clearStr = s.trim() ;
if(clearStr.length() == 0) return 0 ;
//ans保存最終的數(shù)字和，flag表示輸出正數(shù)還是負(fù)數(shù)
int ans = 0 , flag = 1 , lg =0 ;
//處理第一位為 + 或者 - 的情況
if(clearStr.charAt(0) == '+' || clearStr.charAt(0) == '-'){
flag = clearStr.charAt(0) == '+' ? 1:-1;
clearStr = clearStr.substring(1) ;
}
char[] chList = clearStr.toCharArray() ;
for(char p : chList){
//這里的判斷char是數(shù)字的字符的方法，值得記下來
if (p >= '0' && p <= '9'){
lg = p - 48;
//這里的越界判斷，測(cè)試了很久召噩，需要注意
if(ans > Integer.MAX_VALUE/10 || (ans == Integer.MAX_VALUE/10 && lg > 7)){
ans = flag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE ;
return ans;
}
else{
ans = ans*10 + lg ;
}
}
else{
//非數(shù)字字符'0'~'9'直接退出了
return ans * flag ;
}
}
return ans*flag ;
}
}
5. 回文數(shù)
題目地址： https://leetcode-cn.com/problems/palindrome-number/
這個(gè)題目非常簡(jiǎn)單师倔，做了一次通過凶朗。核心是判斷回文字符串的一個(gè)方法，我的方法是將String轉(zhuǎn)化為Char Array宛畦，從第一個(gè)元素迭代到中間羊精，分別比對(duì) i 和 length-i 如果不一樣就不是回文，否則是回文燃少。
class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false ;
char[] cx = String.valueOf(x).toCharArray() ;
if (cx.length == 1) return true ;
/**
* 4444
*/
int len = cx.length;
int mid = cx.length/2;
boolean flag = true;
for (int i =0;i<mid;i++){
if(cx[i] != cx[len-1-i]){
flag = false ;
break;
}
}
return flag ;
}
}
