Skip to content

Commit 2f75483

Browse files
CodingOfZeroCodingOfZero
committed
regular
0 parents  commit 2f75483

5 files changed

Lines changed: 256 additions & 0 deletions

‎Array/1002_FindCommonCharacters.cpp‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
时间：2019年12月29日 19:51:38
3+
题目：Given an array A of strings made only from lowercase letters,
4+
return a list of all characters that show up in all strings within the list (including duplicates).
5+
For example, if a character occurs 3 times in all strings but not 4 times,
6+
you need to include that character three times in the final answer.
7+
You may return the answer in any order.
8+
*/
9+
#include<string>
10+
#include<iostream>
11+
#include<vector>
12+
#include<algorithm>
13+
using namespace std;
14+
/*Runtime: 4 ms, faster than 99.83% of C++ online submissions for Find Common Characters.
15+
Memory Usage : 9.8 MB, less than 54.17% of C++ online submissions for Find Common Characters.
16+
*/
17+
vector<string> commonChars(vector<string>& A) {
18+
vector < int > count(26, INT_MAX);//统计字符出现最小次数，为总的统计次数
19+
for (int i = 0; i<A.size(); i++)//每个字符串中每个字符出现的次数
20+
{
21+
vector < int > countch(26, 0);
22+
for (int j = 0; j<A[i].size(); j++)
23+
countch[A[i][j] - 'a']++;
24+
for (int j = 0; j<26; j++)
25+
count[j] = min(countch[j], count[j]);//取最小的次数
26+
}
27+
vector <string> res;
28+
for (int i = 0; i<26; i++)
29+
for (int j = 0; j<count[i]; j++)
30+
res.push_back(string(1, i + 'a'));
31+
//cout<<(string(1, i + 'a'));
32+
return res;
33+
}
34+
int main() {
35+
vector<string> k = { "bella","label","roller" };
36+
vector<string> res=commonChars(k);
37+
for (string k : res) {
38+
cout << k;
39+
}
40+
}

‎Array/1122_RelativeSortArray.cpp‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/*
2+
Given two arrays arr1 and arr2, the elements of arr2 are distinct,
3+
and all elements in arr2 are also in arr1.
4+
Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2.
5+
Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.
6+
*/
7+
#include<iostream>
8+
#include<vector>
9+
#include<algorithm>
10+
using namespace std;
11+
/*Runtime: 8 ms, faster than 46.62% of C++ online submissions for Relative Sort Array.
12+
Memory Usage : 8.7 MB, less than 100.00% of C++ online submissions for Relative Sort Array.
13+
*/
14+
vector<int> res;
15+
void relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
16+
17+
vector<int>::iterator it;
18+
for (auto elem : arr2) {
19+
int m = count(arr1.begin(), arr1.end(), elem);
20+
for (size_t i = 0; i != m; i++)
21+
res.push_back(elem);
22+
}
23+
sort(arr1.begin(), arr1.end());
24+
for (auto elem : arr1) {
25+
it = find(arr2.begin(), arr2.end(), elem);
26+
if (it == arr2.end())
27+
res.push_back(elem);
28+
}
29+
}
30+
int main() {
31+
vector<int> arr1 = { 28, 6, 22, 8, 44, 17 };
32+
vector<int> arr2 = { 22, 28, 8, 6 };
33+
relativeSortArray(arr1, arr2);
34+
for (auto elem : res)
35+
cout << elem<<" ";
36+
}

‎Array/1160_FindWordsThatCanBeFormedbyCharacters.cpp‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/*
2+
时间：2019年12月21日 20:36:26
3+
题目：给定一个字符串数组、单词和字符串字符，
4+
如果字符串可以由字符组成(每个字符只能使用一次)，那么它就是一个好字符串。
5+
返回所有字符串长度的总和。
6+
*/
7+
#include<iostream>
8+
#include<vector>
9+
#include<algorithm>
10+
/*
11+
Runtime: 88 ms, faster than 53.06% of C++ online submissions for Find Words That Can Be Formed by Characters.
12+
Memory Usage: 17.6 MB, less than 100.00% of C++ online submissions for Find Words That Can Be Formed by Characters.
13+
*/
14+
#define MAX 102
15+
using namespace std;
16+
bool vis[MAX];
17+
int countCharacters(vector<string>& words, string chars) {
18+
int len = 0;
19+
for (auto elem : words) {
20+
for (size_t i = 0; i < chars.size(); i++)//标记数组，访问过变为false，
21+
vis[i] = true;
22+
//每个单词
23+
size_t j = 0;
24+
for (; j < elem.size();j++) {
25+
//查看chars中是否有这个字符
26+
size_t k = 0;
27+
for (; k < chars.size(); k++) {
28+
if (chars[k] == elem[j]&&vis[k]) {//如果找到，将标记数组置为false，表示已访问
29+
vis[k] = false;
30+
break;
31+
}
32+
}
33+
if (k == chars.size())break;//表示未能找到字符
34+
}
35+
if (j == elem.size())len += elem.size();//表示该单词的所有字符都能在chars中找到，此时记录长度
36+
}
37+
return len;
38+
}
39+
/*
40+
Runtime: 84 ms, faster than 57.59% of C++ online submissions for Find Words That Can Be Formed by Characters.
41+
Memory Usage: 15 MB, less than 100.00% of C++ online submissions for Find Words That Can Be Formed by Characters.
42+
利用std::count函数，该函数包含一对迭代器和一个值做参数，返回这个值出现的统计次数。头文件为algorithm
43+
判断单词中每个字符出现的次数是否大于chars中的字符，若大于，则失败
44+
*/
45+
int countCharacters_2(vector<string>& words, std::string chars) {
46+
int res = 0;
47+
for (const auto & w : words)
48+
{
49+
bool flg = true;
50+
for (const auto & c : w)
51+
{
52+
if (std::count(w.begin(), w.end(), c) > std::count(chars.begin(), chars.end(), c))
53+
{
54+
flg = false;
55+
break;
56+
}
57+
}
58+
if (flg) res += w.size();
59+
}
60+
return res;
61+
}
62+
int main() {
63+
vector<string> words = { "cat","bt","hat","tree" };
64+
vector<string> words2 = { "hello","world","leetcode" };
65+
66+
string chars = "atach";
67+
string c = "welldonehoneyr";
68+
int i = countCharacters(words, chars);
69+
int j= countCharacters(words2, c);
70+
int k = countCharacters_2(words2, c);
71+
cout << k << endl;
72+
}

‎Array/1200_MinimumAbsoluteDifference.cpp‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
时间:2019年12月29日 20:47:40
3+
题意：返回距离最小的整数对
4+
*/
5+
#include<iostream>
6+
#include<vector>
7+
#include<algorithm>
8+
using namespace std;
9+
/*
10+
Runtime: 116 ms, faster than 83.12% of C++ online submissions for Minimum Absolute Difference.
11+
Memory Usage: 17.9 MB, less than 100.00% of C++ online submissions for Minimum Absolute Difference.
12+
*/
13+
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
14+
sort(arr.begin(), arr.end());
15+
vector<int> m,n;
16+
vector<vector<int>> res;
17+
int min_dis = INT_MAX;
18+
for (size_t i = 1; i < arr.size(); i++) {
19+
min_dis=min(min_dis,arr[i] - arr[i - 1]);
20+
}
21+
for (size_t i = 1; i < arr.size(); i++) {
22+
if ((arr[i] - arr[i - 1]) == min_dis) {
23+
vector<int> b;
24+
b.push_back(arr[i-1]);
25+
b.push_back(arr[i]);
26+
res.push_back(b);
27+
}
28+
}
29+
return res;
30+
}

‎Array/1252_CellswithOddValuesinaMatrix.cpp‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
/*
2+
时间：2019年12月20日 16:19:32
3+
题目：Given n and m which are the dimensions of a matrix initialized by zeros
4+
and given an array indices where indices[i] = [ri, ci].
5+
For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1
6+
题意：将ri行加一，ci列加一
7+
*/
8+
9+
#include<vector>
10+
#include<iostream>
11+
using namespace std;
12+
/*
13+
Runtime: 4 ms, faster than 83.07% of C++ online submissions for Cells with Odd Values in a Matrix.
14+
Memory Usage: 9.2 MB, less than 100.00% of C++ online submissions for Cells with Odd Values in a Matrix.
15+
*/
16+
#define MAXN 55
17+
#define MAXM 55
18+
int cells[MAXN][MAXM];
19+
int oddCells_1(int n, int m, vector<vector<int>>& indices) {//直接暴力求解
20+
int odd = 0;
21+
for (int i = 0; i < n; i++)
22+
for (int j = 0; j < m; j++)
23+
cells[i][j] = 0;
24+
for (size_t i = 0; i < indices.size(); i++) {
25+
int a = indices[i][0];
26+
int b = indices[i][1];
27+
for (int i = 0; i < m; i++)
28+
cells[a][i]++;
29+
for (int i = 0; i < n; i++)
30+
cells[i][b]++;
31+
}
32+
for (int i = 0; i < n; i++)
33+
for (int j = 0; j < m; j++)
34+
if (cells[i][j] % 2 != 0)
35+
odd++;
36+
return odd;
37+
}
38+
/*
39+
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Cells with Odd Values in a Matrix.
40+
Memory Usage: 9.3 MB, less than 100.00% of C++ online submissions for Cells with Odd Values in a Matrix.
41+
*/
42+
int oddCells_2(int n, int m, vector<vector<int>>& indices) {
43+
vector<int> oddRows;
44+
vector<int> oddCols;
45+
//初始化所有行与列,0是偶数
46+
oddRows.assign(n, 0);
47+
oddCols.assign(m, 0);
48+
49+
50+
for (const auto &elem : indices) {
51+
oddRows[elem[0]] = 1 - oddRows[elem[0]];
52+
oddCols[elem[1]] = 1 - oddCols[elem[1]];
53+
}
54+
//统计奇数的列数
55+
int numOddCols = 0;
56+
for (const auto c : oddCols)//这种写法会比下方速度快
57+
numOddCols += c;
58+
/*for (size_t i = 0; i < oddCols.size(); i++)
59+
if (oddCols[i] == 1)
60+
numOddCols++;*/
61+
62+
int numEvenCols = m - numOddCols;
63+
64+
//输出奇数个数
65+
int Odd = 0;
66+
for (auto r:oddRows)
67+
Odd += r ? numEvenCols : numOddCols;
68+
return Odd;
69+
}
70+
71+
int main() {
72+
vector<vector<int>> indices = { {1,1},{0,0} };
73+
vector<vector<int>> indices2 = { { 0,1 },{ 1,1 } };
74+
int odd1=oddCells_1(2, 2, indices);
75+
int odd2= oddCells_2(2, 3, indices2);
76+
cout << odd2;
77+
}
78+

0 commit comments

Comments
 (0)