文章目錄
- 兩數之和
- 題目
- 我的思路
- leetcode解析
- 解析解法-兩遍hash表
- 解析解法-一遍hash表
- 兩數相加
- 題目
- 我的做法
- leetcode解析
兩數之和
題目
我的思路
利用一個嵌套循環，外循環從下标0到length-1（不包括length-1），内循環從1到length（不包括length），判斷是否等于target。
這種做法我感覺很low，效率會很低，同一個元素用了很多次。
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for(int i = 0;i<nums.length-1;i++){
for(int j = 1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
result[0] = i;
result[1] = j;
break;
}
}
}
return result;
} leetcode解析
我這屬于暴力法。完全是最簡單的思路。效率應該最低。
解析中有hashmap的解法，分别是兩遍hash表和一遍hash表。
解析解法-兩遍hash表
為了對運作時間複雜度進行優化，我們需要一種更有效的方法來檢查數組中是否存在目标元素。如果存在，我們需要找出它的索引。保持數組中的每個元素與其索引互相對應的最好方法是什麼？哈希表。
通過以空間換取速度的方式，我們可以将查找時間從 O(n) 降低到 O(1)。哈希表正是為此目的而建構的，它支援以 近似 恒定的時間進行快速查找。我用“近似”來描述，是因為一旦出現沖突，查找用時可能會退化到 O(n)。但隻要你仔細地挑選哈希函數，在哈希表中進行查找的用時應當被攤銷為 O(1)。
一個簡單的實作使用了兩次疊代。在第一次疊代中，我們将每個元素的值和它的索引添加到表中。然後，在第二次疊代中，我們将檢查每個元素所對應的目标元素（target - nums[i]target−nums[i]）是否存在于表中。注意，該目标元素不能是 nums[i]nums[i] 本身！
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
} 總結：這種方式沒有用嵌套，沒有用暴力破解的方法，摒棄了全拿過來挨個算一下的思想。采用的思想是，先逮住一個數，與目标值一起計算求內插補點，然後利用hash去定位是否存在這個內插補點，當然要想定位哦這個內插補點得做為key，然後要求輸入的數組不能有重複的值，這都是一些前提條件。判定的時候，需要定位+非i，這兩個條件一起成立才可以。典型的空間換時間，一定程度上提升了效率。
複雜度分析：
解析解法-一遍hash表
事實證明，我們可以一次完成。在進行疊代并将元素插入到表中的同時，我們還會回過頭來檢查表中是否已經存在目前元素所對應的目标元素。如果它存在，那我們已經找到了對應解，并立即将其傳回。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
} 兩數相加
題目
我的做法
結果是做的稀爛，沒做出來，貼出來支離破碎的代碼：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode listNodeResult = null;
ListNode currentNode = null;
int temp = 0;
while(true){
temp=l1.val+l2.val;
if(listNodeResult==null&&temp<10){
listNodeResult = new ListNode(temp);
currentNode = listNodeResult；
}else if(listNodeResult==null&&temp>=10){
listNodeResult = new ListNode(temp-10)
listNodeResult.next = new ListNode(1);
currentNode = listNodeResult；
}else{
currentNode = currentNode.next;
//下面是2次以後的處理
if(temp<10){
}else{//>=10
}
}
}
} 總結：完全是用if可能性的方法在思考，沒有任何的數學邏輯在裡面。是以寫到最後寫不進去了。拿到題，先要想好政策再下手，否則寫着寫着就寫不下去了，這也算是教訓。思路不清晰就先寫注釋列清楚邏輯。
leetcode解析
我們使用變量來跟蹤進位，并從包含最低有效位的表頭開始模拟逐位相加的過程。
圖1，對兩數相加方法的可視化: 342 + 465 = 807342+465=807，每個結點都包含一個數字，并且數字按位逆序存儲。
請注意，我們使用啞結點來簡化代碼。如果沒有啞結點，則必須編寫額外的條件語句來初始化表頭的值。 啞節點：頭節點初始化為0
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
//看到這裡，做題中想到的一個每一個連結清單都要有目前位置的想法是正确的。
ListNode p = l1, q = l2, curr = dummyHead;
//考慮一下進位 0 或者 1
int carry = 0;
//考慮連結清單不一樣長
while (p != null || q != null) {
//考慮不一樣長的情況，特殊處理x和y
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
//計算進去進位值
int sum = carry + x + y;
//計算是否有進位，最大不過1
carry = sum / 10;
//首節點為0的啞節點，統一為隻考慮next
curr.next = new ListNode(sum % 10);
//三條連結清單統一往後移動
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
//最後一位如果出現進位，則新增一個節點
if (carry > 0) {
curr.next = new ListNode(carry);
}
//傳回的時候不包括啞節點就ok了
return dummyHead.next;
}