Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4d702a4

Browse files
authored
Merge pull requestneetcode-gh#2534 from tonngw/main
Create: 0706-design-hashmap.cpp and 0034-find-first-and-last-position-of-element-in-sorted-array.cpp
2 parents57e09db +2842da5 commit4d702a4

File tree

2 files changed

+91
-0
lines changed

2 files changed

+91
-0
lines changed
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/*
2+
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
3+
Ex. nums = [5,7,7,8,8,10], target = 8 -> [3, 4] (start position is 3, end position is 4)
4+
5+
Use binary search, firstly binary search left endpoint, then binary search right endpoint.
6+
7+
Time: O(log n)
8+
Space: O(1)
9+
*/
10+
11+
classSolution {
12+
public:
13+
vector<int>searchRange(vector<int>& nums,int target) {
14+
if (nums.empty())return {-1, -1};
15+
int l =0, r = nums.size() -1;
16+
while (l < r) {
17+
int mid = l + r >>1;
18+
if (nums[mid] >= target) r = mid;
19+
else l = mid +1;
20+
}
21+
if (nums[l] != target)return {-1, -1};
22+
int left = l;
23+
24+
l =0, r = nums.size() -1;
25+
while (l < r) {
26+
int mid = l + r +1ll >>1;
27+
if (nums[mid] <= target) l = mid;
28+
else r = mid -1;
29+
}
30+
return {left, r};
31+
}
32+
};

‎cpp/0706-design-hashmap.cpp

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
/*
2+
Design a HashMap without using any built-in hash table libraries.
3+
4+
Designing a hash table using the chaining method, where a vector holds a list of pairs representing the key-value mappings.
5+
6+
Time: O(n)
7+
Space: O(n)
8+
*/
9+
10+
classMyHashMap {
11+
public:
12+
constint N =10010;
13+
vector<list<pair<int,int>>> h;
14+
15+
/** Initialize your data structure here.*/
16+
MyHashMap() {
17+
h = vector<list<pair<int,int>>>(N);
18+
}
19+
20+
list<pair<int,int>>::iteratorfind(int key) {
21+
int t = key % N;
22+
for (auto it = h[t].begin(); it != h[t].end(); it ++ ) {
23+
if (it->first == key)
24+
return it;
25+
}
26+
return h[t].end();
27+
}
28+
29+
/** value will always be non-negative.*/
30+
voidput(int key,int value) {
31+
auto t = key % N;
32+
auto it =find(key);
33+
if (it == h[t].end()) h[t].push_back({key, value});
34+
else it->second = value;
35+
}
36+
37+
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key*/
38+
intget(int key) {
39+
auto t = key % N;
40+
auto it =find(key);
41+
if (it != h[t].end())return it->second;
42+
return -1;
43+
}
44+
45+
/** Removes the mapping of the specified value key if this map contains a mapping for the key*/
46+
voidremove(int key) {
47+
auto t = key % N;
48+
auto it =find(key);
49+
if (it != h[t].end()) h[t].erase(it);
50+
}
51+
};
52+
53+
/**
54+
* Your MyHashMap object will be instantiated and called as such:
55+
* MyHashMap* obj = new MyHashMap();
56+
* obj->put(key,value);
57+
* int param_2 = obj->get(key);
58+
* obj->remove(key);
59+
*/

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp