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
Appearance settings

Commit 7a1f42c

Browse filesBrowse files
theondtheond
committed
2 parents a63b215 + 1aa630a commit 7a1f42c
Copy full SHA for 7a1f42c

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Dismiss banner
Expand file treeCollapse file tree

63 files changed

+2139
-18
lines changed
Open diff view settings
Collapse file

‎cpp/cpp/array/BinarySearch.cpp‎

Copy file name to clipboard
+34Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
#include <iostream>
2+
#include "BinarySearch.h"
3+
using namespace std;
4+
5+
BinarySearch::BinarySearch(){}
6+
7+
int BinarySearch::binarySearch(int nums[], int tar, int length) {
8+
9+
int low = 0, high = length - 1;
10+
while (low < high) {
11+
int index = low + ((high - low) >> 1);
12+
if (nums[index] > tar) {
13+
low = index + 1;
14+
}
15+
else if(nums[index] < tar){
16+
high = index - 1;
17+
}
18+
else {
19+
return index;
20+
}
21+
}
22+
return -1;
23+
}
24+
25+
/*
26+
void main() {
27+
BinarySearch search;
28+
int input[7] = { 1,7,9,10,21,37,42};
29+
int length = sizeof(input) / sizeof(input[0]);
30+
//int result = search.binarySearch(input, 37, length);
31+
int result = search.binarySearch(input, 6, length);
32+
cout << result << endl;
33+
}
34+
*/
Collapse file

‎cpp/cpp/array/BinarySearch.h‎

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
#pragma once
2+
#ifndef BINARYSEARCH
3+
#define BINARYSEARCH
4+
class BinarySearch {
5+
private:
6+
public:
7+
BinarySearch();
8+
int binarySearch(int nums[], int tar, int length);
9+
};
10+
#endif // !BINARYSEARCH
11+
Collapse file

‎cpp/cpp/array/FindRotateMin.cpp‎

Copy file name to clipboard
+58Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
#include"FindRotateMin.h"
2+
#include<iostream>
3+
using namespace std;
4+
5+
6+
int result = INT_MAX;
7+
8+
FindRotateMin::FindRotateMin(){}
9+
10+
int FindRotateMin::findRotateMin(int nums[], int length) {
11+
12+
// best solution
13+
/*
14+
* int l=0,r=nums.size()-1;
15+
while(l<r){
16+
int mid=(r-l)/2+l;
17+
if(nums[mid]<nums[r]){
18+
r=mid;
19+
20+
}
21+
else{
22+
l=mid+1;
23+
}
24+
}
25+
return nums[l];
26+
*/
27+
findMin(nums, 0, length - 1);
28+
cout << result << endl;
29+
return result;
30+
}
31+
32+
void FindRotateMin::findMin(int nums[], int l, int r) {
33+
if (l > r)
34+
return;
35+
36+
int m = l + (r - l) / 2;
37+
if (nums[m] < nums[r]) {
38+
if(result > nums[m])
39+
result = nums[m];
40+
findMin(nums, l, m - 1);
41+
}else{
42+
if (result > nums[m])
43+
result = nums[m];
44+
findMin(nums, m+1,r);
45+
}
46+
}
47+
48+
/*
49+
int main() {
50+
FindRotateMin findRotateMin;
51+
int nums[7] = { 4,5,6,7,0,1,2 };
52+
int length = sizeof(nums) / sizeof(nums[0]);
53+
findRotateMin.findRotateMin(nums, length);
54+
for (int i = 0; i < length; i++) {
55+
cout << nums[i] << endl;
56+
}
57+
}
58+
*/
Collapse file

‎cpp/cpp/array/FindRotateMin.h‎

Copy file name to clipboard
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
#pragma once
2+
#ifndef FINDROTATEMIN
3+
class FindRotateMin {
4+
private:
5+
6+
public:
7+
FindRotateMin();
8+
int findRotateMin(int nums[], int length);
9+
10+
void findMin(int nums[], int l, int r);
11+
};
12+
#endif // !FINDROTATEMIN
Collapse file

‎cpp/cpp/array/FindRotateMin2.cpp‎

Copy file name to clipboard
+38Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
#include"FindRotateMin2.h"
2+
#include<iostream>
3+
using namespace std;
4+
5+
int result2 = INT_MAX;
6+
FindRotateMin2::FindRotateMin2(){}
7+
8+
int FindRotateMin2::findMin(int nums[], int length) {
9+
10+
int l = 0, r = length - 1;
11+
while (l < r) {
12+
int mid = l + (r - l) / 2;
13+
if (nums[mid] < nums[r]) {
14+
r = mid;
15+
}
16+
else if (nums[mid] > nums[r]) {
17+
l = mid + 1;
18+
}
19+
else {
20+
r--;
21+
}
22+
}
23+
24+
cout << nums[l] << endl;
25+
return nums[l];
26+
}
27+
28+
/*
29+
int main() {
30+
FindRotateMin2 findRotateMin;
31+
int nums[3] = { 1,3,3 };
32+
int length = sizeof(nums) / sizeof(nums[0]);
33+
findRotateMin.findMin(nums, length);
34+
for (int i = 0; i < length; i++) {
35+
cout << nums[i] << endl;
36+
}
37+
}
38+
*/
Collapse file

‎cpp/cpp/array/FindRotateMin2.h‎

Copy file name to clipboard
+10Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
#pragma once
2+
#ifndef FINDROTATEMIN2
3+
#define FINDROTATEMIN2
4+
class FindRotateMin2 {
5+
private:
6+
public:
7+
FindRotateMin2();
8+
int findMin(int nums[], int length);
9+
};
10+
#endif // !FINDROTATEMIN2
Collapse file

‎cpp/cpp/array/FourSum.cpp‎

Copy file name to clipboard
+81Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
#include"FourSum.h"
2+
#include<iostream>
3+
using namespace std;
4+
5+
FourSum::FourSum(){}
6+
7+
void FourSum::fourSum(int nums[], int length, int target) {
8+
if (length < 4)
9+
return;
10+
11+
quickSort(nums, 0, length - 1);
12+
for (int i = 0; i < length - 3; i++) {
13+
//if (nums[i] > target)
14+
// break;
15+
if (i > 0 && nums[i] == nums[i - 1])
16+
continue;
17+
for (int j = i + 1; j < length - 2; j++) {
18+
//if (nums[i] + nums[j] > target)
19+
// break;
20+
if (j > i+1 && nums[j] == nums[j - 1])
21+
continue;
22+
23+
int sub = target - nums[i] - nums[j];
24+
int k = j + 1, l = length - 1;
25+
while (k < l) {
26+
if (nums[k] + nums[l] == sub) {
27+
cout << nums[i] << ',' << nums[j] << ',' << nums[k] << ',' << nums[l] << endl;
28+
29+
k++;
30+
l--;
31+
while (k <= l && nums[k] == nums[k - 1]) k++;
32+
while (l >= k && nums[l] == nums[l + 1]) l--;
33+
}
34+
else if (nums[k] + nums[l] < sub) {
35+
k++;
36+
}
37+
else {
38+
l--;
39+
}
40+
}
41+
}
42+
}
43+
}
44+
45+
void FourSum::quickSort(int nums[], int low, int high) {
46+
if (low >= high)
47+
return;
48+
49+
int le = low - 1, cur = low, ri = high, stand = nums[high];
50+
while (cur <= ri) {
51+
if (nums[cur] > stand) {
52+
int temp = nums[ri];
53+
nums[ri] = nums[cur];
54+
nums[cur] = temp;
55+
ri--;
56+
}
57+
else if (nums[cur] < stand) {
58+
int temp = nums[le + 1];
59+
nums[le + 1] = nums[cur];
60+
nums[cur] = temp;
61+
le++;
62+
cur++;
63+
}
64+
else {
65+
cur++;
66+
}
67+
}
68+
quickSort(nums, low, le);
69+
quickSort(nums, cur, high);
70+
}
71+
72+
//int main() {
73+
// FourSum fourSum;
74+
// int nums[8] = { 1,-2,-5,-4,-3,3,3,5};
75+
// int length = sizeof(nums) / sizeof(nums[0]);
76+
// //fourSum.quickSort(nums, 0, length-1);
77+
// fourSum.fourSum(nums, length, -11);
78+
// for (int i = 0; i < length; i++) {
79+
// cout << nums[i] << endl;
80+
// }
81+
//}
Collapse file

‎cpp/cpp/array/FourSum.h‎

Copy file name to clipboard
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
#pragma once
2+
#ifndef FOURSUM
3+
#define FOURSUM
4+
class FourSum {
5+
private:
6+
public:
7+
FourSum();
8+
void quickSort(int nums[], int low, int high);
9+
void fourSum(int nums[], int length, int target);
10+
};
11+
#endif // !FOURSUM
12+
Collapse file

‎cpp/cpp/array/MajorityElement.cpp‎

Copy file name to clipboard
+59Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
#include <iostream>
2+
#include <unordered_map>
3+
#include "MajorityElement.h"
4+
5+
using namespace std;
6+
7+
MajorityElement::MajorityElement() {}
8+
9+
int MajorityElement::majorityElement(int nums[], int length) {
10+
int mid = length >> 1;
11+
unordered_map<int, int> numCount;
12+
for (int i = 0; i < length; i++) {
13+
++numCount[nums[i]];
14+
if (numCount[nums[i]] > mid) {
15+
return nums[i];
16+
}
17+
}
18+
/*
19+
for (int i = 0; i < length; i++) {
20+
if (numCount.count(nums[i]) == 0) {
21+
numCount.insert({ nums[i], 1 });
22+
}
23+
else {
24+
numCount.insert({ nums[i], numCount[nums[i]]++ });
25+
}
26+
27+
if (numCount[nums[i]] > mid) {
28+
return nums[i];
29+
}
30+
}*/
31+
return -1;
32+
}
33+
34+
//Boyer–Moore vote 算法，适用于超过半数的众数
35+
int MajorityElement::majority2(int nums[], int length) {
36+
int majority = 0, count = 0;
37+
for (int i = 0; i < length; i++) {
38+
if (count == 0) {
39+
majority = nums[i];
40+
count = 1;
41+
}
42+
else {
43+
count += (majority == nums[i] ? 1 : -1);
44+
}
45+
}
46+
return majority;
47+
}
48+
49+
/*
50+
int main() {
51+
MajorityElement majority;
52+
int input[7] = { 1,1,9,3,3,3,3 };
53+
int length = sizeof(input) / sizeof(input[0]);
54+
// int result = majority.majorityElement(input, 7);
55+
int result = majority.majority2(input, 7);
56+
cout << result << endl;
57+
return 0;
58+
}
59+
*/
Collapse file

‎cpp/cpp/array/MajorityElement.h‎

Copy file name to clipboard
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
#pragma once
2+
#ifndef MAJORITYELEMENT
3+
#define MAJORITYELEMENT
4+
class MajorityElement {
5+
private:
6+
public:
7+
MajorityElement();
8+
int majorityElement(int nums[], int length);
9+
int majority2(int nums[], int length);
10+
};
11+
#endif // !MAJORITYELEMENT
12+

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.