《深入理解计算机系统》学习笔记 - 前言节选

发表于 2016-11-10 | 分类于 CSAPP

本书的主要读者是计算机科学家、计算机工程师，以及那些想通过学习计算机系统的内在运作而能够写出更好程序的人。

我们的目标是解释所有计算机系统的本质概念，并向你展示这些概念是如何实实在在地影响应用程序的正确性、性能和实用性的。其它的系统类书籍都是从构建者的角度来写的，讲述如何实现硬件或是系统软件，包括操作系统、编译器和网络接口。而本书是从程序员的角度来写的，讲述应用程序员如何能够利用系统知识来编写出更好的程序。

阅读全文 »

Leetcode 题解 - 225. Implement Stack using Queues

发表于 2016-11-10 | 分类于 Leetcode

题目

使用队列来实现下列的栈操作：

push(x) – 把元素 x 压栈。
pop() – 删除栈顶元素。
top() – 获取栈顶元素。
empty() – 返回栈是否为空。

阅读全文 »

Leetcode 题解 - 234. Palindrome Linked List

发表于 2016-11-08 | 分类于 Leetcode

题目

给定一个单向链表，判断它是否回文链表。

阅读全文 »

Leetcode 题解 - 88. Merge Sorted Array

发表于 2016-11-07 | 分类于 Leetcode

题目

给定两个有序的整数数组 nums1 和 nums2，把 num2 合并到 nums1 使之成为一个有序数组。

阅读全文 »

Leetcode 题解 - 219. Contains Duplicate II

发表于 2016-11-07 | 分类于 Leetcode

题目

给定一个整数数组 nums 和一个整数 k，判断是否存在两个不同的索引 i, j，使得 nums[i] = nums[j]，且 i, j 之差最多为 k。

难度：容易

编程语言：C++

分析

程序框架为：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        
    }
};

我的思路是：

取 i = 0，j = k，判断是否 nums[i] = nums[j]，是则 return true，否则 i, j 分别 +1，重复本步骤直到 j = nums.size()-1。
来到第 2 步，说明没有找到两个不同的索引 i, j，使得 nums[i] = nums[j]，且 i, j 之差为 k，所以 k -= 1，继续第 1 步，直到 k = 1。

代码如下：

#include <frequently-used-code-snippets.h>
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        for (; k > 0; k--) {
            for (int i = 0, j = k; j < nums.size(); i++, j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
};
int main() {
    int array[] = { 1, 2, 3, 4, 2, 1 };
    vector<int> nums = convertArrayToVector(array, ARRAY_LENGTH(array));
    Solution sol;
    cout << sol.containsNearbyDuplicate(nums, 2);
}
// 输出结果：
// 1

提交到 Leetcode，Time Limit Exceeded! 导致超时的输入为 nums = { 0, 1, 2, 3, …, 29999 }，k = 15000。上面代码的时间复杂度为 O(n^2)。

那就换个思路，每遍历 nums 一个元素，放到 map<int, int> 里，key 为元素值，value 为元素索引。如果当前元素不存在于 map，那么添加到 map。如果已存在于 map，判断两个索引之差是否 <= k，如果是 retur true，否则更新 value 值。

代码如下：

#include <frequently-used-code-snippets.h>
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        for (; k > 0; k--) {
            for (int i = 0, j = k; j < nums.size(); i++, j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
    bool containsNearbyDuplicate2(vector<int>& nums, int k) {
        map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            int key = nums[i];
            int val = i;
            map<int, int>::iterator iter = m.find(key);
            if (iter != m.end()) {   // 找到重复元素
                if (val - iter->second <= k) {
                    return true;
                }
                else {
                    iter->second = val;
                }
            }
            else {      // 没找到重复元素
                m[key] = val;
            }
        }
        return false;
    }
};
int main() {
    int array[] = { 1, 2, 1 };
    vector<int> nums = convertArrayToVector(array, ARRAY_LENGTH(array));
    Solution sol;
    cout << sol.containsNearbyDuplicate2(nums, 0);
}
// 输出结果：
// 0