Last active
April 21, 2024 04:13
-
-
Save huynhthaihoa/367bb02ea0105c924c9c2a2ddeab47ff to your computer and use it in GitHub Desktop.
Array-2
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int minimumBoxes(vector<int>& apple, vector<int>& capacity) { | |
| int appleNum = 0; | |
| for(auto const &instance: apple) | |
| appleNum += instance; | |
| sort(capacity.begin(), capacity.end(), greater<int>()); | |
| int boxNum = 0; | |
| for(int i = 0; i < capacity.size(); ++i) | |
| { | |
| if(appleNum <= 0) | |
| break; | |
| appleNum -= capacity[i]; | |
| ++boxNum; | |
| } | |
| return boxNum; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| long long countAlternatingSubarrays(vector<int>& nums) { | |
| int size = nums.size(); | |
| int begin = 0; | |
| long long numSubArray = 0; | |
| for(int i = 1; i <= size; ++i) | |
| { | |
| if(i == size || nums[i] == nums[i - 1]) | |
| { | |
| //count the number of subarray in range [begin, i - 1] | |
| int numElems = i - begin; | |
| numSubArray += ((numElems * (long)(numElems + 1)) >> 1); | |
| begin = i; | |
| } | |
| } | |
| return numSubArray; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int maxFrequencyElements(vector<int>& nums) { | |
| map<int, int> numMap; | |
| for(auto const &num: nums) | |
| numMap[num]++; | |
| map<int, int> freqMap; | |
| for(auto const &pair: numMap) | |
| freqMap[pair.second]++; | |
| return freqMap.rbegin()->first * freqMap.rbegin()->second; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| long long countSubarrays(vector<int>& nums, int k) { | |
| if(nums.size() == 1) | |
| { | |
| if(k == 1) | |
| return 1; | |
| return 0; | |
| } | |
| int maxVal = nums[0]; //to find maximum element in nums | |
| vector<int> maxIdxs; //to save every position of maximum element in nums | |
| maxIdxs.push_back(0); | |
| for(int i = 1; i < nums.size(); ++i) | |
| { | |
| if(nums[i] >= maxVal) | |
| { | |
| if(nums[i] > maxVal) | |
| { | |
| maxVal = nums[i]; | |
| maxIdxs.clear(); | |
| } | |
| maxIdxs.push_back(i); | |
| } | |
| } | |
| //we will consider each subarray that contains maxIdxs[i] and maxIdxs[i + j - 1], with j from k to lim | |
| long long num = 0; | |
| int indexNum = maxIdxs.size(); | |
| for(int i = 0; i <= indexNum - k; ++i) | |
| { | |
| long long startPos = (i == 0)? maxIdxs[i] + 1 : maxIdxs[i] - maxIdxs[i - 1]; | |
| //end pos is from maxIdxs[i + k - 1] to end | |
| long long endPos = nums.size() - maxIdxs[i + k - 1]; | |
| num += startPos * endPos; | |
| } | |
| return num; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| bool isVowel(const char &c) | |
| { | |
| return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'); | |
| } | |
| vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) { | |
| vector<int> candidates; | |
| vector<int> result(queries.size()); | |
| for(int i = 0; i < words.size(); ++i) | |
| { | |
| if(isVowel(words[i][0]) && isVowel(words[i].back())) | |
| candidates.push_back(i); | |
| } | |
| for(int i = 0; i < result.size(); ++i) | |
| { | |
| int pivot = -1; | |
| int j; | |
| for(j = 0; j < candidates.size(); ++j) | |
| { | |
| if(candidates[j] > queries[i][1]) | |
| break; | |
| if(candidates[j] >= queries[i][0] && pivot == -1) | |
| pivot = j; | |
| } | |
| if(pivot != -1) | |
| result[i] = j - pivot; | |
| } | |
| return result; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<vector<int>> findFarmland(vector<vector<int>>& land) { | |
| int m = land.size(); | |
| int n = land[0].size(); | |
| map<pair<int, int>, vector<int>> farmrowMap; //key: pair of begin column - end column, value: list of all rows that have farm area in | |
| //the range from begin column - end column | |
| for(int i = 0; i < m; ++i) //iterate by row | |
| { | |
| int beginIdx = -1; | |
| for(int j = 0; j <= n; ++j) //iterate by column | |
| { | |
| if(j == n || land[i][j] == 0) | |
| { | |
| if(beginIdx != -1) | |
| farmrowMap[make_pair(beginIdx, j - 1)].push_back(i); | |
| beginIdx = -1; | |
| } | |
| else if(land[i][j] == 1 && beginIdx == -1) | |
| beginIdx = j; | |
| } | |
| } | |
| vector<vector<int>> result; | |
| for(map<pair<int, int>, vector<int>>::iterator it = farmrowMap.begin(); it != farmrowMap.end(); ++it) | |
| { | |
| vector<int> rows = it->second; | |
| int beginIdx = 0; | |
| for(int i = 1; i <= rows.size(); ++i) | |
| { | |
| if(i == rows.size() || rows[i] > rows[i - 1] + 1) | |
| { | |
| //from rows[beginIdx] to rows[i - 1] | |
| //top-left: rows[beginIdx] - (it->first).first | |
| //bottom-right: rows[i - 1] - (it->first).second | |
| vector<int> group = {rows[beginIdx], (it->first).first, rows[i - 1], (it->first).second}; | |
| result.push_back(group); | |
| beginIdx = i; | |
| } | |
| } | |
| } | |
| return result; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) { | |
| vector<int> answer(2, -1); | |
| for(int i = 0; i < nums.size(); ++i) | |
| { | |
| if(i >= indexDifference) | |
| { | |
| for(int j = 0; j <= i - indexDifference; ++j) | |
| { | |
| if(abs(nums[i] - nums[j]) >= valueDifference) | |
| { | |
| answer[0] = i; | |
| answer[1] = j; | |
| return answer; | |
| } | |
| } | |
| } | |
| if(i <= nums.size() - 1 - indexDifference) | |
| { | |
| for(int j = i + indexDifference; j < nums.size(); ++j) | |
| { | |
| if(abs(nums[i] - nums[j]) >= valueDifference) | |
| { | |
| answer[0] = i; | |
| answer[1] = j; | |
| return answer; | |
| } | |
| } | |
| } | |
| } | |
| return answer; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| private: | |
| public: | |
| bool withinPeriod(const string& first, const string &second) | |
| { | |
| if(first[0] == second[0]) | |
| { | |
| if(first[1] == second[1]) | |
| return true; | |
| if(first[1] + 1 != second[1]) | |
| return false; | |
| if(first[2] > second[2]) | |
| return true; | |
| if(first[2] < second[2]) | |
| return false; | |
| return(first[3] > second[3]); | |
| } | |
| if(first[0] + 1 != second[0]) //must be (0..., 1...) or (1..., 2...) | |
| return false; | |
| if(first[1] != '9' || second[1] != '0') //must be (09.., 10..) or (19.., 20..) | |
| return false; | |
| if(first[2] > second[2]) | |
| return true; | |
| if(first[2] < second[2]) | |
| return false; | |
| return(first[3] > second[3]); | |
| } | |
| vector<string> findHighAccessEmployees(vector<vector<string>>& access_times) { | |
| map<string, vector<string>> accessMap; | |
| vector<string> highAccessEmployees; | |
| for(auto const& access_time: access_times) | |
| accessMap[access_time[0]].push_back(access_time[1]); | |
| for(map<string, vector<string>>::iterator it = accessMap.begin(); it != accessMap.end(); ++it) | |
| { | |
| vector<string> cache = it->second; | |
| if(cache.size() > 2) | |
| { | |
| sort(cache.begin(), cache.end()); | |
| for(int i = 0; i < cache.size() - 2; ) | |
| { | |
| if(withinPeriod(cache[i], cache[i + 1])) | |
| { | |
| if(withinPeriod(cache[i], cache[i + 2])) | |
| { | |
| highAccessEmployees.push_back(it->first); | |
| break; | |
| } | |
| else | |
| ++i; | |
| } | |
| else | |
| ++i; | |
| } | |
| } | |
| } | |
| return highAccessEmployees; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| long long maximumHappinessSum(vector<int>& happiness, int k) { | |
| sort(happiness.begin(), happiness.end(), greater<int>()); | |
| long long sum = 0; | |
| for(int i = 0; i < k; ++i) | |
| { | |
| happiness[i] -= i; | |
| if(happiness[i] < 0) | |
| happiness[i] = 0; | |
| sum += happiness[i]; | |
| } | |
| return sum; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int maxCount(vector<int>& banned, int n, int maxSum) { | |
| sort(banned.begin(), banned.end()); | |
| int bannedSize = banned.size(); | |
| int count = 0; | |
| int curChosen = 1; //the current chosen value | |
| int curIdx = 0; //inspection index on banned array | |
| while(maxSum >= curChosen && curChosen <= n) | |
| { | |
| if(curChosen < banned[curIdx]) | |
| { | |
| maxSum -= curChosen; | |
| ++curChosen; | |
| ++count; | |
| } | |
| else if(curChosen == banned[curIdx]) | |
| ++curChosen; | |
| else | |
| { | |
| if(curIdx < bannedSize - 1) | |
| ++curIdx; | |
| else | |
| { | |
| maxSum -= curChosen; | |
| ++curChosen; | |
| ++count; | |
| } | |
| } | |
| } | |
| return count; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int maxSum(vector<vector<int>>& grid) { | |
| int res = 0; | |
| int nRows = grid.size() - 2; | |
| int nCols = grid[0].size() - 2; | |
| for(int i = 0; i < nRows; ++i) | |
| { | |
| for(int j = 0; j < nCols; ++j) | |
| { | |
| int tmpSum = grid[i][j] + grid[i][j + 1] + grid[i][j + 2] + grid[i + 1][j + 1] + grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2]; | |
| if(tmpSum > res) | |
| res = tmpSum; | |
| } | |
| } | |
| return res; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| long long maximumTripletValue(vector<int>& nums) { | |
| long long result = 0; | |
| int n = nums.size(); | |
| for(int i = 0; i < n - 2; ++i) | |
| { | |
| for(int j = i + 1; j < n - 1; ++j) | |
| { | |
| if(nums[j] < nums[i]) | |
| { | |
| long long tmp = nums[j + 1]; | |
| for(int k = j + 2; k < n; ++k) | |
| { | |
| if(nums[k] > tmp) | |
| tmp = nums[k]; | |
| } | |
| tmp *= (nums[i] - nums[j]); | |
| if(tmp > result) | |
| result = tmp; | |
| } | |
| } | |
| } | |
| return result; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int minAbsoluteDifference(vector<int>& nums, int x) { | |
| int res = 999999999; | |
| for(int i = 0; i < nums.size() - x; ++i) | |
| { | |
| for(int j = i + x; j < nums.size(); ++j) | |
| { | |
| if(nums[i] == nums[j]) | |
| return 0; | |
| int tmp = abs(nums[i] - nums[j]); | |
| if(tmp < res) | |
| res = tmp; | |
| } | |
| } | |
| return res; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int getCommon(vector<int>& nums1, vector<int>& nums2) { | |
| set<int> numSet; | |
| for(auto const &num: nums1) | |
| numSet.insert(num); | |
| for(auto const &num: nums2) | |
| { | |
| if(numSet.find(num) != numSet.end()) | |
| return num; | |
| } | |
| return -1; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int minimumLevels(vector<int>& possible) { | |
| int size = possible.size(); | |
| vector<int> accumPoints(size); | |
| if(possible[0] == 1) | |
| accumPoints[0] = 1; | |
| else | |
| accumPoints[0] = -1; | |
| for(int i = 1; i < size; ++i) | |
| { | |
| if(possible[i] == 1) | |
| accumPoints[i] = accumPoints[i - 1] + 1; | |
| else | |
| accumPoints[i] = accumPoints[i - 1] - 1; | |
| } | |
| int i = 0; | |
| --size; | |
| accumPoints[size] >>= 1; | |
| for(; i < size; ++i) | |
| { | |
| if(accumPoints[i] > accumPoints[size]) | |
| break; | |
| } | |
| if(i == size) | |
| return -1; | |
| return i + 1; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int minOperations(vector<int>& nums, int k) { | |
| set<int> collection; | |
| for(int i = 1; i <= k; ++i) | |
| collection.insert(i); | |
| int count = 0; | |
| for(int i = nums.size() - 1; i >= 0; --i) | |
| { | |
| if(collection.find(nums[i]) != collection.end()) | |
| collection.erase(nums[i]); | |
| ++count; | |
| if(collection.size() == 0) | |
| return count; | |
| } | |
| return 0; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int minimumSum(vector<int>& nums) { | |
| int res = -1; | |
| int n = nums.size(); | |
| for(int i = 1; i < n - 1; ++i) | |
| { | |
| int left_bound = -1; | |
| for(int j = 0; j < i; ++j) | |
| { | |
| if(nums[j] < nums[i] && (left_bound == -1 || left_bound > nums[j])) | |
| left_bound = nums[j]; | |
| } | |
| if(left_bound != -1) | |
| { | |
| int right_bound = -1; | |
| for(int j = i + 1; j < n; ++j) | |
| { | |
| if(nums[j] < nums[i] && (right_bound == -1 || right_bound > nums[j])) | |
| right_bound = nums[j]; | |
| } | |
| if(right_bound != -1) | |
| { | |
| int tmp = left_bound + nums[i] + right_bound; | |
| if(res == -1 || res > tmp) | |
| res = tmp; | |
| } | |
| } | |
| } | |
| return res; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int minimumSum(vector<int>& nums) { | |
| int res = -1; | |
| int n = nums.size(); | |
| for(int i = 1; i < n - 1; ++i) | |
| { | |
| int left_bound = -1; | |
| for(int j = 0; j < i; ++j) | |
| { | |
| if(nums[j] < nums[i] && (left_bound == -1 || left_bound > nums[j])) | |
| left_bound = nums[j]; | |
| } | |
| if(left_bound != -1) | |
| { | |
| int right_bound = -1; | |
| for(int j = i + 1; j < n; ++j) | |
| { | |
| if(nums[j] < nums[i] && (right_bound == -1 || right_bound > nums[j])) | |
| right_bound = nums[j]; | |
| } | |
| if(right_bound != -1) | |
| { | |
| int tmp = left_bound + nums[i] + right_bound; | |
| if(res == -1 || res > tmp) | |
| res = tmp; | |
| } | |
| } | |
| } | |
| return res; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) { | |
| int size = nums.size(); | |
| map<int, long long> freqMap; | |
| vector<long long> res(size, 0); | |
| map<long long, int> maxMap; | |
| for(int i = 0; i < size; ++i) | |
| { | |
| if(freqMap.find(nums[i]) != freqMap.end()) | |
| { | |
| --maxMap[freqMap[nums[i]]]; | |
| if(maxMap[freqMap[nums[i]]] == 0) | |
| maxMap.erase(freqMap[nums[i]]); | |
| freqMap[nums[i]] += freq[i]; | |
| } | |
| else | |
| freqMap[nums[i]] = freq[i]; | |
| ++maxMap[freqMap[nums[i]]]; | |
| res[i] = maxMap.rbegin()->first; | |
| } | |
| return res; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) { | |
| int k = pattern.size(); | |
| int n = nums.size() - 1; | |
| vector<int> signs; | |
| for(int i = 1; i <= n; ++i) | |
| { | |
| if(nums[i - 1] < nums[i]) | |
| signs.push_back(1); | |
| else if(nums[i - 1] == nums[i]) | |
| signs.push_back(0); | |
| else | |
| signs.push_back(-1); | |
| } | |
| int count = 0; | |
| for(int i = 0; i <= n - k; ++i) | |
| { | |
| int j = 0; | |
| for(; j < k; ++j) | |
| { | |
| if(signs[i + j] != pattern[j]) | |
| break; | |
| } | |
| if(j == k) | |
| ++count; | |
| } | |
| return count; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| long long zeroFilledSubarray(vector<int>& nums) { | |
| int pivot = -1; | |
| long long res = 0; | |
| for(int i = 0; i < nums.size(); ++i) | |
| { | |
| if(nums[i] == 0) | |
| { | |
| if(pivot == -1) | |
| pivot = i; | |
| if((i == nums.size() - 1 || nums[i + 1] != 0) && pivot != -1) | |
| { | |
| long long tmp = 0; | |
| if((i - pivot + 1) & 1) | |
| { | |
| tmp = ((i - pivot + 2) >> 1); | |
| tmp *= (i - pivot + 1); | |
| } | |
| else | |
| { | |
| tmp = ((i - pivot + 1) >> 1); | |
| tmp *= (i - pivot + 2); | |
| } | |
| res += tmp; | |
| pivot = -1; | |
| } | |
| } | |
| } | |
| return res; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<vector<int>> permute(vector<int>& nums) { | |
| vector<vector<int>> res; | |
| if(nums.size() == 1) | |
| { | |
| vector<int> elems = {nums[0]}; | |
| res.push_back(elems); | |
| } | |
| else | |
| { | |
| for(int i = 0; i < nums.size(); ++i) | |
| { | |
| vector<int> tmp_nums(nums); | |
| tmp_nums.erase(tmp_nums.begin() + i); | |
| vector<vector<int>> tmp_res = permute(tmp_nums); | |
| for(int j = 0; j < tmp_res.size(); ++j) | |
| { | |
| vector<int> tmp_tmp_nums; | |
| tmp_tmp_nums.push_back(nums[i]); | |
| if(tmp_res[j].size()) | |
| { | |
| for(auto const &elem: tmp_res[j]) | |
| tmp_tmp_nums.push_back(elem); | |
| } | |
| res.push_back(tmp_tmp_nums); | |
| } | |
| } | |
| } | |
| return res; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<vector<int>> permuteUnique(vector<int>& nums) { | |
| vector<vector<int>> permutations; //permutation list | |
| if(nums.size() == 1) | |
| { | |
| vector<int> permutation = {nums[0]}; | |
| permutations.push_back(permutation); | |
| } | |
| else | |
| { | |
| map<int, pair<int, int>> numMap; //save the unique numbers and their corresponding frequencies | |
| for(int i = 0; i < nums.size(); ++i) | |
| { | |
| if(numMap.find(nums[i]) == numMap.end()) | |
| { | |
| numMap[nums[i]] = make_pair(i, 1); | |
| } | |
| else | |
| numMap[nums[i]].second++; | |
| } | |
| if(numMap.size() == 1) | |
| { | |
| vector<int> permutation(numMap.begin()->second.second, numMap.begin()->first); | |
| permutations.push_back(permutation); | |
| } | |
| else | |
| { | |
| for(auto const& numPair: numMap) | |
| { | |
| int index = numPair.second.first; | |
| vector<int> tmp_nums(nums); | |
| tmp_nums.erase(tmp_nums.begin() + index); | |
| vector<vector<int>> tmp_permutations = permuteUnique(tmp_nums); | |
| for(int j = 0; j < tmp_permutations.size(); ++j) | |
| { | |
| vector<int> tmp_permutation; | |
| tmp_permutation.push_back(nums[index]); | |
| if(tmp_permutations[j].size()) | |
| { | |
| for(auto const &elem: tmp_permutations[j]) | |
| tmp_permutation.push_back(elem); | |
| } | |
| permutations.push_back(tmp_permutation); | |
| } | |
| } | |
| } | |
| } | |
| return permutations; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<double> sampleStats(vector<int>& count) { | |
| vector<double> stats(5); | |
| int maxFreq = 0; | |
| map<int, int> countMap; //key: k, value: number of times that k appears in the sample | |
| int numSamples = 0; | |
| double accumVal = 0; | |
| for(int i = 0; i < count.size(); ++i) | |
| { | |
| if(count[i] != 0) | |
| { | |
| countMap[i] = count[i]; | |
| numSamples += count[i]; | |
| accumVal += (i * double(count[i])); | |
| if(count[i] > maxFreq) | |
| { | |
| stats[4] = i; //mode | |
| maxFreq = count[i]; | |
| } | |
| } | |
| } | |
| stats[0] = countMap.begin()->first; //minimum: first key in countMap | |
| stats[1] = countMap.rbegin()->first; //maximum: last key in countMap | |
| stats[2] = accumVal / numSamples; //mean | |
| int accumNumSamples = 0; | |
| for(map<int, int>::iterator it = countMap.begin(); it != countMap.end(); ++it) | |
| { | |
| if(accumNumSamples + it->second > ((numSamples + 1) >> 1)) | |
| { | |
| stats[3] = it->first; //median | |
| break; | |
| } | |
| else if(accumNumSamples + it->second == ((numSamples + 1) >> 1)) | |
| { | |
| if(numSamples & 1) | |
| stats[3] = it->first; //median | |
| else | |
| { | |
| map<int, int>::iterator tmpIt = it; | |
| ++tmpIt; | |
| stats[3] = double(it->first + tmpIt->first) / 2; //median | |
| } | |
| break; | |
| } | |
| else | |
| accumNumSamples += it->second; | |
| } | |
| return stats; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| bool isKSetBit(const int &num, int k) | |
| { | |
| int count = 0; | |
| int n = num; | |
| while(n > 0) | |
| { | |
| count += (n & 1); | |
| if(count > k) | |
| return false; | |
| n >>= 1; | |
| } | |
| return (count == k); | |
| } | |
| int sumIndicesWithKSetBits(vector<int>& nums, int k) { | |
| int sum = 0; | |
| for(int i = 0; i <nums.size(); ++i) | |
| { | |
| if(isKSetBit(i, k)) | |
| sum += nums[i]; | |
| } | |
| return sum; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment