算法练习(一)

发表于 | 分类于

从刷Leetcode开始

  1. 两数之和
    给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
    你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
    示例:
    给定 nums = [2, 7, 11, 15], target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

分析思路：
1.暴力遍历，依次遍历数组每个元素x，然后查找是否存在目标值-x的值，如果存在，就返回。时间复杂度O(n2),空间复杂度O(1).
2.利用hash表查找的时间复杂度是O(1)优化算法，先遍历一次，存入hash表，下标作为hash的value，数组元素值作为hash的key。再一次遍历每个元素，查找hash表中是否有对应值。时间复杂度O(n2),空间复杂度O(n).
3.遍历两次可以优化为一次即可，存储之前先查找hashmap中有没有对应的值。如果有直接返回，没有，再存入。

算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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进一步提高了算法效率

  1. 两数相加
    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
    你可以假设除了数字 0 之外，这两个数字都不会以零开头。
    示例：
    输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

常规思路：初始化一条新的链表Result。使用单指针同步遍历两个非空链表。使用临时标志位表示进位。每一次遍历求和结果就给Result链表拓展一个该值的节点，并且求和的时候把进位值加上。

算法实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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: 给定的两个链表长度不一致，2：最终有进位的情况

时间复杂度: O(max(m,n)); 空间复杂度:O(max(m,n))+1;