0%

Posted on Edited on In

题目

原题在此

解析

一道经典的DP题目.

  1. dp[i] = min(dp[i - coins[0]], dp[i - coins[1]] ... dp[i - coins[n]])
  2. dp[0] = 0

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, 10001);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < coins.size(); j++) {
                if(i - coins[j] >= 0){
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == 10001 ? -1 : dp[amount];
    }
};

Posted on Edited on In

题目

原题在此

解析

将字母与数字的映射从大到小排列, 然后贪心的减去最大的值并拼接字符串.

代码

go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func intToRoman(num int) string {
    s := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
    arr := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    res := ""
    idx := 0
    for num != 0 {
        if arr[idx] <= num {
            res += s[idx]
            num -= arr[idx]
        } else {
            idx++
        }
    }
    return res
}

Posted on Edited on In

题目

原题在此

解析

常规的level order traversal即可, 没什么难度.

代码

c++

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
41
42
43
44
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(!root) return root;
        // if(d == 1) return make_shared<TreeNode>(v, root, NULL);
        if(d == 1) {
            TreeNode * foo = new TreeNode(v, root, NULL);
            return foo;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty() && d) {
            if(!--d) return root;
            int n = q.size();
            for(int i = 0; i < n; ++i) {
                TreeNode* tmp = q.front();
                q.pop();
                if(d == 1) {
                    TreeNode* l = tmp->left;
                    TreeNode* r = tmp->right;
                    tmp->left = new TreeNode(v);
                    tmp->right = new TreeNode(v);
                    tmp->left->left = l;
                    tmp->right->right = r;
                } else {
                    if(tmp -> left) q.push(tmp -> left);
                    if(tmp -> right) q.push(tmp -> right);
                }
            }
        }
        return root;
    } 
};

Posted on Edited on In

题目

原题在此

解析

根据题意有:

  1. str只包含'a'和'b';
  2. 要remove的是Subsequences而非substring;

所以str为空是0次, 是回文则1次, 否则就是2次.(第一次移除所有a第二次移除所有b)

代码

c++

1
2
3
4
5
6
7
8
class Solution {
public:
    int removePalindromeSub(string s) {
        if(s.empty()) return 0;
        if(s == string(s.rbegin(), s.rend())) return 1;
        return 2;
    }
};

Posted on Edited on In

题目

原题在此

解析

参考wiki, 实现HashMap, 需要考虑的有如下几点:

  1. 均匀分布的散列函数
  2. 冲突处理
  3. 动态扩容

面试能把这几点说清楚就差不多了. 这题不应该标记简单…

代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// template <typename K, typename V>
class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        length = 0;
        v.resize(20); 
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        // ref from http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html 
        // As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. 
        // Higher values decrease the space overhead but increase the lookup cost (reflected in most of the
        // operations of the HashMap class, including get and put). 
        // The expected number of entries in the map and its load factor should be taken into account when setting
        // its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is 
        // greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
        if(double(length / v.size()) > 0.5) expand();
        int idx = hash(key);
        auto head = v[idx];
        auto tmp = head;
        while(tmp) {
            if(key == tmp -> key) {
                tmp -> value = value;
                return;
            } 
            tmp = tmp -> next;
        }
        Node* node = new Node(key, value);
        node -> next = head;
        v[idx] = node;
        length++;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        // int idx = hash(key);
        Node* node = v[hash(key)];
        while(node) {
            if(key == node -> key) return node -> value;
            node = node -> next;
        }
        return -1;        
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int idx = hash(key);
        auto node = v[idx];
        Node* prev = NULL;
        while(node) {
            if(key == node -> key) {
                --length;
                prev ? prev -> next = node -> next : v[idx] = node -> next;
            }
            prev = node;
            node = node -> next;
        }
    }
    
private: 
    struct Node;
    vector<Node*> v;
    int length;
    
    // Dynamic resizing
    void expand() {
        vector<Node*> tmp(v.size());
        v.swap(tmp);
        v.resize(v.size() * 2);
        length = 0;
        for(auto &node : tmp) {
            while(node) {
                put(node -> key, node -> value);
                node = node -> next;
            }
        }
    }
    
    // knuth multiplicative hash
    int hash(int key){
        return (long long)key * 2654435761 % v.size();
    }

    // template <typename K, typename V>
    struct Node {
        Node(const int &key, const int &value) : key(key), value(value), next(NULL) {}
        int key;
        int value;
        Node* next;
    };
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

Posted on Edited on In

题目

原题在此

解析

因为题中说到words.size() <= 7, 所以可以按照字符串长度给words排序, 复杂度几乎可以忽略不计. 之后再逐个尝试插入即可.

当words.size()很大时, 就需直接用前缀树了.

代码

c++

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
class Solution {
public:
    // 非常暴力的空间换时间, 根据题意设置好长度的前缀树.
    const static int N = 14007;
    int idx = 0;
    int map[N][26];
    
    bool insert(string &s) {
        int p = 0;
        bool res = true;
        for(int i = s.size() - 1; i >= 0; i--) {
            int u = s[i] - 'a';
            if(map[p][u] == 0) {
                map[p][u] = ++idx;
                res = false;
            }
            p = map[p][u];
        }
        return res;
    }
    
    int minimumLengthEncoding(vector<string>& words) {
        sort(words.begin(), words.end(),
             [](const string & a, const string & b) -> bool { 
                return a.size() > b.size(); 
        });
        int res = 0;
        for(auto & word : words) {
            if(!insert(word)) res += word.size() + 1;
        }
        return res;
    }
};

前缀树模板

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
class Trie {
private:
	bool is_string = false;
	Trie* next[26] = { nullptr };
public:
	Trie() {}
	void insert(const string& word) {
		Trie* root = this;
		for (const auto& w : word) {
			if (root->next[w - 'a'] == nullptr)root->next[w - 'a'] = new Trie();
			root = root->next[w - 'a'];
		}
		root->is_string = true;
	}

	bool search(const string& word) {
		Trie* root = this;
		for (const auto& w : word) {
			if (root->next[w - 'a'] == nullptr)return false;
			root = root->next[w - 'a'];
		}
		return root->is_string;
	}

	bool startsWith(const string& prefix) {
		Trie* root = this;
		for (const auto& p : prefix) {
			if (root->next[p - 'a'] == nullptr)return false;
			root = root->next[p - 'a'];
		}
		return true;
	}
};

Posted on Edited on In

题目

原题在此

解析

标准的level order traversal, 没啥好讲的.

代码

c++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if(!root) return {};
        vector<double> res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int n = q.size();
            long long sum = 0;
            for(int i = 0; i < n; ++i) {
                TreeNode* tmp = q.front();
                q.pop();
                sum += tmp->val;
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            res.push_back(double(sum) / double(n));
        }
        return res;
    }
};

Posted on Edited on In

题目

原题在此

解析

用两个指针同时开始遍历两个list, 在任意一个指针走到头时开始切换到另一个head继续遍历. 再两指针相等时退出循环. 此时如果两指针不为空则停在了交点处, 否则代表两个list没有交点.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *foo, ListNode *bar) {
        ListNode *a = foo, *b = bar;
        while(a != b) {
            a = a ? a->next : bar;
            b = b ? b->next : foo;
        }
        return a;
    }
};

Posted on Edited on In

题目

原题在此

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length
  • 1 <= n <= $10^4$
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

解析

求和,异或都行.非常简单.

代码

c++/xor

1
2
3
4
5
6
7
8
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size(), res = 0;
        for(int i = 0; i < n; i++) res ^= (i ^ nums[i]);
        return res ^ n;
    }
};

java/sum

1
2
3
4
5
6
7
public int missingNumber(int[] nums) {
    int len = nums.length;
    int sum = (0+len)*(len+1)/2;
    for(int i=0; i<len; i++)
        sum-=nums[i];
    return sum;
}

Posted on In

题目

原题在此

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:
Input: nums = [1,2,2,4]
Output: [2,3]

Example 2:
Input: nums = [1,1]
Output: [1,2]

Constraints:

  • 2 <= nums.length <= $10^4$
  • 1 <= nums[i] <= $10^4$

解析

根据题意,要返回一个长度为2的数组, 其中res[0]为重复出现的值, res[1]为缺少的值.
对于任意整数i, 有 i ^ i == 0 => 1^2^3^4 ^ 1^2^3^4 == 0 => 1^2^3^4 ^ 1^2^2^4 == 2 ^ 3, 将异或结果暂存在res[1];
统计每个元素的出现次数, 将出现两次的数记录在res[0], 此时res[1] = res[1] ^ res[0].

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        vector<int> count(n);
        vector<int> res = {0, 0};
        for(int i = 0; i < n; ++i) {
            res[1] ^= nums[i] ^ (i+1);
            if(++count[nums[i]-1] == 2) res[0] = nums[i];
        }
        res[1] ^= res[0];
        return res;
    }
};