郭霖的博客

腾讯音乐实习ing

发表于 更新于 分类于
本文字数： 34k 阅读时长 ≈ 31 分钟

非线程安全的缓存

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
package simple_cache;

import java.util.HashMap;
import java.util.concurrent.TimeUnit;

// 最简单的缓存形式：HashMap
public class Cache1 {
    private HashMap<String, Integer> cache = new HashMap<>();

    public Integer compute(String userId) throws InterruptedException {
        Integer result = cache.get(userId);

        // 先检查HashMap里面有没有保存过之前的计算结果
        if (result == null) {
            // 如果缓存中找不到，那么需要现在来计算一下结果，并保存到HashMap中
            result = doCompute(userId);
            cache.put(userId, result);
        }        return result;
    }

    // 模拟实际的业务中的计算逻辑，采用sleep代替
    private Integer doCompute(String userId) throws InterruptedException {
        TimeUnit.SECONDS.sleep(5);
        return new Integer(userId);
    }

    public static void main(String[] args) throws InterruptedException {
        Cache1 cache1 = new Cache1();
        System.out.println("开始计算了");
        Integer result = cache1.compute("13");
        System.out.println("第一次计算结果：" + result);

        result = cache1.compute("13");
        System.out.println("第二次计算结果：" + result);
    }
}
阅读全文 »

发表于 更新于 分类于
本文字数： 8.7k 阅读时长 ≈ 8 分钟

万能头文件

1
#include＜bits/stdc++.h＞

加快输入输出

1
2
3
4
main函数中加入以下代码，降低时长
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0)
阅读全文 »

发表于 更新于 分类于
本文字数： 60k 阅读时长 ≈ 55 分钟

1. 两数之和

两数之和

思路：
用哈希表储存已经遍历过的值，再通过int r = target - nums[i];查看哈希表中是否存在一个值，与nums[i]之和为target

时间复杂度：O(n)
核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;
        for (int i = 0; i < nums.size(); i++) {
            int tmp = target - nums[i];
            if (hashmap.count(tmp)) {
                return {hashmap[tmp], i};
            } else {
                hashmap[nums[i]] = i;
            }
        }
        return {};
    }
};
阅读全文 »

发表于 更新于 分类于
本文字数： 52k 阅读时长 ≈ 47 分钟

数组中重复的数字

数组中重复的数字

原地哈希做法：时间复杂度：O(n)，空间复杂度：O(1)

核心代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] != i && nums[nums[i]] != nums[i]) swap(nums[nums[i]], nums[i]);
            if (nums[i] != i && nums[nums[i]] == nums[i]) return nums[i];
        }
        return -1;
    }
};
阅读全文 »