從刷Leetcode開始
- 兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值温赔，找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)一種答案它褪，且同樣的元素不能被重復(fù)利用饵骨。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析思路：
1.暴力遍歷，依次遍歷數(shù)組每個(gè)元素x列赎，然后查找是否存在目標(biāo)值-x的值宏悦，如果存在镐确，就返回包吝。時(shí)間復(fù)雜度O(n2),空間復(fù)雜度O(1).
2.利用hash表查找的時(shí)間復(fù)雜度是O(1)優(yōu)化算法，先遍歷一次源葫，存入hash表诗越，下標(biāo)作為hash的value，數(shù)組元素值作為hash的key息堂。再一次遍歷每個(gè)元素嚷狞，查找hash表中是否有對(duì)應(yīng)值块促。時(shí)間復(fù)雜度O(n2),空間復(fù)雜度O(n).
3.遍歷兩次可以優(yōu)化為一次即可，存儲(chǔ)之前先查找hashmap中有沒(méi)有對(duì)應(yīng)的值床未。如果有直接返回竭翠，沒(méi)有，再存入薇搁。
算法實(shí)現(xiàn)如下:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int differ = target - nums[i];
auto result = map.find(nums[i]);
if (result != map.end()) {
return {result->second,i};
}
else{
map[differ] = i;
}
}
return {};
}
};
使用C++11的unordered_map進(jìn)一步提高了算法效率
- 兩數(shù)相加
給定兩個(gè)非空鏈表來(lái)表示兩個(gè)非負(fù)整數(shù)斋扰。位數(shù)按照逆序方式存儲(chǔ)，它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字啃洋。將兩數(shù)相加返回一個(gè)新的鏈表传货。
你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會(huì)以零開頭宏娄。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
常規(guī)思路：初始化一條新的鏈表Result问裕。使用單指針同步遍歷兩個(gè)非空鏈表。使用臨時(shí)標(biāo)志位表示進(jìn)位孵坚。每一次遍歷求和結(jié)果就給Result鏈表拓展一個(gè)該值的節(jié)點(diǎn)粮宛，并且求和的時(shí)候把進(jìn)位值加上。
算法實(shí)現(xiàn)如下
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
struct ListNode* res = new ListNode(0);
struct ListNode* current = res;
int carry = 0;
while (l1 || l2) {
int sum = carry;
if (l1 != NULL) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != NULL) {
sum += l2->val;
l2 = l2->next;
}
current->val = sum%10;
carry = sum/10;
if (l1 || l2 || carry!= 0) {
current->next = new ListNode(0);
current = current->next;
}
}
if (carry != 0) {
current->val = carry;
}
return res;
}
};
需要注意的是1: 給定的兩個(gè)鏈表長(zhǎng)度不一致卖宠，2：最終有進(jìn)位的情況
時(shí)間復(fù)雜度: O(max(m,n)); 空間復(fù)雜度:O(max(m,n))+1;
