LintCode 134-LRU缓存策略

分析

  • 链表实现即可
  • set和get操作命中时都认为是使用过,必须移到队尾
1
class LRUCache{
2
public:
3
    struct ListNode {
4
        ListNode *next;
5
        int key, value;
6
        
7
        ListNode(int k, int v) {
8
            key = k;
9
            value = v;
10
            next = NULL;
11
        }
12
    };
13
    // @param capacity, an integer
14
    int count, cap;
15
    ListNode *head, *tail;
16
    LRUCache(int capacity) {
17
        // write your code here
18
        count = 0;
19
        cap = capacity;
20
        head = tail = NULL;
21
    }
22
    
23
    // @return an integer
24
    int get(int key) {
25
        // write your code here
26
        ListNode *p = head, *front = NULL;
27
        int ret = -1;
28
        while (p) {
29
            if (p->key == key) {
30
                ret = p->value;
31
                break;
32
            }
33
            front = p;
34
            p = p->next;
35
        }
36
        if (ret != -1 && p != tail) {
37
            if (front) {
38
                front->next = p->next;
39
            } else {
40
                head = p->next;
41
            }
42
            p->next = NULL;
43
            tail->next = p;
44
            tail = p;
45
        }
46
        return ret;
47
    }
48
49
    // @param key, an integer
50
    // @param value, an integer
51
    // @return nothing
52
    void set(int key, int value) {
53
        // write your code here
54
        ListNode *p = head, *front = NULL;
55
        bool found = false;
56
        while (p) {
57
            if (p->key == key) {
58
                found = true;
59
                p->value = value;
60
                break;
61
            }
62
            front = p;
63
            p = p->next;
64
        }
65
        if (!found) {
66
            ++count;
67
            ListNode *q = new ListNode(key, value);
68
            if (!tail) {
69
                head = tail = q;
70
            } else {
71
                tail->next = q;
72
                tail = q;
73
            }
74
            if (count > cap) {
75
                --count;
76
                ListNode *q = head;
77
                head = q->next;
78
                delete q;
79
            }
80
        } else {
81
            if (p != tail) {
82
                if (front) {
83
                    front->next = p->next;
84
                } else {
85
                    head = p->next;
86
                }
87
                p->next = NULL;
88
                tail->next = p;
89
                tail = p;
90
            }
91
        }
92
    }
93
};

LintCode 140-快速幂

分析

注意溢出

1
class Solution {
2
public:
3
    /*
4
     * @param a, b, n: 32bit integers
5
     * @return: An integer
6
     */
7
    int fastPower(int a, int b, int n) {
8
        // write your code here
9
        return dfs(a % b, b, n);
10
    }
11
    
12
    long long dfs(int a, int b, int n) {
13
        if (!n) return 1 % b;
14
        int r = n / 2;
15
        long long t = dfs(a, b, r);
16
        if (n % 2 == 0) {
17
            return t * t % b;
18
        } else {
19
            return (t * t % b) * a % b;
20
        }
21
    }
22
};

LintCode 144-交错正负数

分析

  • 注意正负总数不同的情况
  • 采用2个游标分别指向偶数下标和奇数下标,交换不符合条件的元素
1
class Solution {
2
public:
3
    /**
4
     * @param A: An integer array.
5
     * @return: void
6
     */
7
    void rerange(vector<int> &A) {
8
        // write your code here
9
        int tag = 0;
10
        for (int i = 0; i < A.size(); ++i) {
11
             if (A[i] > 0) --tag;
12
             else ++tag;
13
        }
14
        if (!tag) tag = 1;
15
        for (int i = 0, j = 1; i < A.size() && j < A.size(); i += 2, j += 2) {
16
            while (i < A.size() && tag * A[i] < 0) i += 2;
17
            while (j < A.size() && tag * A[j] > 0) j += 2;
18
            if (i < A.size() && j < A.size()) {
19
                int t = A[i];
20
                A[i] = A[j];
21
                A[j] = t;
22
            }
23
        }
24
    }
25
};

LintCode 156-合并区间

分析

注意细节处理就好

1
/**
2
 * Definition of Interval:
3
 * class Interval {
4
 *     int start, end;
5
 *     Interval(int start, int end) {
6
 *         this->start = start;
7
 *         this->end = end;
8
 *     }
9
 */
10
class Solution {
11
public:
12
    /**
13
     * @param intervals: interval list.
14
     * @return: A new interval list.
15
     */
16
    vector<Interval> merge(vector<Interval> &intervals) {
17
        // write your code here
18
        sort(intervals, 0, intervals.size() - 1);
19
        vector<Interval> ret;
20
        if (intervals.empty()) return ret;
21
        Interval interval(intervals[0].start, intervals[0].end);
22
        for (int i = 1; i < intervals.size(); ++i) {
23
            if (intervals[i].start > interval.end) {
24
                ret.push_back(interval);
25
                interval.start = intervals[i].start;
26
                interval.end = intervals[i].end;
27
            } else {
28
                interval.end = max(interval.end, intervals[i].end);
29
            }
30
        }
31
        ret.push_back(interval);
32
        return ret;
33
    }
34
    
35
    void sort(vector<Interval> &v, int bottom, int top) {
36
        if (bottom >= top) return;
37
        int i, j;
38
        Interval interval = v[bottom];
39
        i = bottom;
40
        j = top;
41
        while (i < j) {
42
            for (; i < j && v[j].start >= interval.start; --j);
43
            v[i] = v[j];
44
            for (; i < j && v[i].start <= interval.start; ++i);
45
            v[j] = v[i];
46
        }
47
        v[i] = interval;
48
        sort(v, bottom, i - 1);
49
        sort(v, i + 1, top);
50
    }
51
};

LintCode 167-链表求和

分析

注意进位

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    /**
12
     * @param l1: the first list
13
     * @param l2: the second list
14
     * @return: the sum list of l1 and l2 
15
     */
16
    ListNode *addLists(ListNode *l1, ListNode *l2) {
17
        // write your code here
18
        int carry = 0;
19
        ListNode *head = NULL, *p;
20
        while (l1 && l2) {
21
            int sum = l1->val + l2->val + carry;
22
            int remain = sum % 10;
23
            carry = sum / 10;
24
            p = new ListNode(remain);
25
            p->next = head;
26
            head = p;
27
            l1 = l1->next;
28
            l2 = l2->next;
29
        }
30
        while (l1) {
31
            int sum = l1->val + carry;
32
            int remain = sum % 10;
33
            carry = sum / 10;
34
            p = new ListNode(remain);
35
            p->next = head;
36
            head = p;
37
            l1 = l1->next;
38
        }
39
        while (l2) {
40
            int sum = l2->val + carry;
41
            int remain = sum % 10;
42
            carry = sum / 10;
43
            p = new ListNode(remain);
44
            p->next = head;
45
            head = p;
46
            l2 = l2->next;
47
        }
48
        if (carry) {
49
            p = new ListNode(carry);
50
            p->next = head;
51
            head = p;
52
        }
53
        if (head) {
54
            p = head->next;
55
            head->next = NULL;
56
            while (p) {
57
                ListNode *q = p->next;
58
                p->next = head;
59
                head = p;
60
                p = q;
61
            }
62
        }
63
        
64
        return head;
65
    }
66
};

LintCode 171-乱序字符串

分析

hash的使用

1
class Solution {
2
public:    
3
    /**
4
     * @param strs: A list of strings
5
     * @return: A list of strings
6
     */
7
    vector<string> anagrams(vector<string> &strs) {
8
        // write your code here
9
        unordered_map<string, int> index;
10
        unordered_map<string, int>::iterator it;
11
        vector<string> ret;
12
        vector<vector<string>> save;
13
        for (int i = 0; i < strs.size(); ++i) {
14
            vector<int> h(26, 0);
15
            for (int j = 0; j < strs[i].length(); ++j) {
16
                int dist = strs[i][j] - 'a';
17
                ++h[dist];
18
            }
19
            string s = hash(h);
20
            it = index.find(s);
21
            if (it != index.end()) {
22
                int id = it->second;
23
                save[id].push_back(strs[i]);
24
            } else {
25
                vector<string> vs;
26
                vs.push_back(strs[i]);
27
                save.push_back(vs);
28
                index.insert(make_pair(s, save.size() - 1));
29
            }
30
        }
31
        for (int i = 0; i < save.size(); ++i) {
32
            if (save[i].size() > 1) {
33
                for (int j = 0; j < save[i].size(); ++j) {
34
                    ret.push_back(save[i][j]);
35
                }
36
            }
37
        }
38
        return ret;
39
    }
40
    
41
    string hash(const vector<int> &h) {
42
        stringstream ss;
43
        for (int i = 0; i < 26; ++i) {
44
            if (h[i]) {
45
                char ch = 'a' + i;
46
                ss << ch;
47
                if (h[i] > 1) {
48
                    ss << h[i];
49
                }
50
            }
51
        }
52
        return ss.str();
53
    }
54
};

LintCode 178-图是否是树

分析

  • 判断边总数是否为n-1;
  • 判断一次dfs是否能访问所有节点。
1
class Solution {
2
public:
3
    /**
4
     * @param n an integer
5
     * @param edges a list of undirected edges
6
     * @return true if it's a valid tree, or false
7
     */
8
    bool validTree(int n, vector<vector<int>>& edges) {
9
        // Write your code here
10
        if (edges.size() != n - 1) return false;
11
        vector<vector<int>> map(n, vector<int>(n, 0));
12
        for (int i = 0; i < edges.size(); ++i) {
13
            int p1 = edges[i][0], p2 = edges[i][1];
14
            map[p1][p2] = map[p2][p1] = 1;
15
        }
16
        vector<bool> visited(n, false);
17
        dfs(map, 0, visited);
18
        for (int i = 0; i < visited.size(); ++i) {
19
            if (!visited[i]) return false;
20
        }
21
        return true;
22
    }
23
    
24
    void dfs(vector<vector<int>> &map, int curr, vector<bool> &visited) {
25
        visited[curr] = true;
26
        for (int i = 0; i < map[curr].size(); ++i) {
27
            if (map[curr][i] && !visited[i]) {
28
                dfs(map, i, visited);
29
            }
30
        }
31
    }
32
};

LintCode 30-插入区间

1
/**
2
 * Definition of Interval:
3
 * class Interval {
4
 * public:
5
 *     int start, end;
6
 *     Interval(int start, int end) {
7
 *         this->start = start;
8
 *         this->end = end;
9
 *     }
10
 * }
11
 */
12
class Solution {
13
public:
14
    /**
15
     * Insert newInterval into intervals.
16
     * @param intervals: Sorted interval list.
17
     * @param newInterval: new interval.
18
     * @return: A new interval list.
19
     */
20
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
21
        // write your code here
22
        vector<Interval> ret;
23
        int i = 0;
24
        while (i < intervals.size() && intervals[i].end < newInterval.start) {
25
            ret.push_back(intervals[i]);
26
            ++i;
27
        }
28
        if (i == intervals.size()) {
29
            ret.push_back(newInterval);
30
            return ret;
31
        }
32
        int start, end;
33
        start = min(intervals[i].start, newInterval.start);
34
        while (i < intervals.size() && intervals[i].start <= newInterval.end) {
35
            ++i;
36
        }
37
        end = i > 0 ? max(intervals[i-1].end, newInterval.end) : newInterval.end;
38
        Interval interval(start, end);
39
        ret.push_back(interval);
40
        while (i < intervals.size()) {
41
            ret.push_back(intervals[i]);
42
            ++i;
43
        }
44
        return ret;
45
    }
46
};

LintCode 57-三数之和

分析

注意hash去重

1
class Solution {
2
public:    
3
    /**
4
     * @param numbers : Give an array numbers of n integer
5
     * @return : Find all unique triplets in the array which gives the sum of zero.
6
     */
7
    vector<vector<int> > threeSum(vector<int> &nums) {
8
        // write your code here
9
        vector<vector<int>> ret;
10
        unordered_set<long long> d;
11
        for (int i = 0; i < nums.size() - 2; ++i) {
12
            int sum = -nums[i];
13
            unordered_set<int> s;
14
            for (int j = i + 1; j < nums.size(); ++j) {
15
                if (s.find(nums[j]) != s.end()) {
16
                    vector<int> ans;
17
                    ans.push_back(nums[i]);
18
                    ans.push_back(nums[j]);
19
                    ans.push_back(-(nums[i] + nums[j]));
20
                    sort(ans.begin(), ans.end());
21
                    long long t = 33 * 33 * ans[0] + 33 * ans[1] + ans[2];
22
                    if (d.find(t) == d.end()) {
23
                        ret.push_back(ans);
24
                        d.insert(t);
25
                    }
26
                } else {
27
                    s.insert(sum - nums[j]);
28
                }
29
            }
30
        }
31
        return ret;
32
    }
33
};

LintCode 58-四数之和

1
class Solution {
2
public:
3
    /**
4
     * @param numbers: Give an array numbersbers of n integer
5
     * @param target: you need to find four elements that's sum of target
6
     * @return: Find all unique quadruplets in the array which gives the sum of 
7
     *          zero.
8
     */
9
    vector<vector<int> > fourSum(vector<int> nums, int target) {
10
        // write your code here
11
        vector<vector<int>> ret;
12
        set<int> dup;
13
        sort(nums.begin(), nums.end());
14
        for (int i = 0; i < nums.size(); ++i) {
15
            for (int j = i + 1; j < nums.size(); ++j) {
16
                unordered_set<int> s;
17
                for (int k = j + 1; k < nums.size(); ++k) {
18
                    int r = target - nums[i] - nums[j] - nums[k];
19
                    if (r < nums[j]) break;
20
                    if (r <= nums[k] && s.find(nums[k]) != s.end()) {
21
                        int h = hash(nums[i], nums[j], r, nums[k]);
22
                        if (dup.find(h) == dup.end()) {
23
                            vector<int> ans({nums[i], nums[j], r, nums[k]});
24
                            ret.push_back(ans);
25
                            dup.insert(h);
26
                        }
27
                    } else {
28
                        s.insert(r);
29
                    }
30
                }
31
            }
32
        }
33
        return ret;
34
    }
35
    
36
    int hash(int a, int b, int c, int d) {
37
        return a + 10 * b + 100 * c + 35937 * d;
38
    }
39
};
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×