vucuong020195
BAN USERint countZero(vector<vector<int>> table){
//Find the most right 0 of the first row
int col = 0;
int res = 0;
while (col < table.size() && table[1][col] == 0) col++;
if (col == 0) return 0; res += col; col--;
for (int i = 1; i < table.size(); i++){
while(col > -1 && table[i][col] == 1) col--;
res += col + 1;
if (col == -1) return res;
}
}
Time complexity: O (row * col)
// Example program
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int findNumberOfWords(vector<string> stringList, int row, int col){
int r = 0, c = 0, i = 0;
int res = 0;
while (r < row){
cout << r << " " << c << " " << stringList[i] << " " << res << endl;
if (stringList[i].length() > col) return res;
if (stringList[i].length()+ (c==0?0:1) + c <= col) {
if (c + stringList[i].length()+ (c==0?0:1) == col) r++;
c = (c + stringList[i].length()+ (c==0?0:1)) % col;
i = (i + 1) % stringList.size();
res++;
} else {
r++; c = 0;
}
}
return res;
}
int main()
{
//Input
vector<string> stringList = {"aa", "aaa"};
int row = 2;
int col = 9;
cout << findNumberOfWords(stringList, row, col) << endl;
return 0;
}
You can solve this problem with O(n) for test() and O(log(n)) for store().
- For store(): use insert() function of set to always have a sorted set
- For test(): use left and right variable to narrow down the range of finding the 2 target numbers.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
class NumberManager {
public:
void store(int number){
numbers.insert(number);
}
bool check(int number){
set<int>::iterator left = numbers.begin();
set<int>::iterator right = --numbers.end();
while (left != right){
if (number == *left + *right){
return true;
} else if (number > *left + *right){
left++;
} else {
right--;
}
}
return false;
}
void printNumbers(){
for (set<int>::iterator left = numbers.begin(); left != numbers.end(); left++){
cout << *left << " ";
}
cout << endl;
}
private:
set<int> numbers;
};
int main(){
NumberManager test;
test.store(1);
test.store(3);
test.store(2);
test.printNumbers();
cout << test.check(3) << endl;
return 0;
}
void findSegment(int *arr, int n, int target){
// closest is the closest position on the left such that sum from closest to current position
// is greater or equal target
int closest = -1; //doesn't exist initially
int* sum = new int[n];
int* res = NULL;
for (int i = 0; i < n; i++){
//sum[i]: sum of the first i+1 elements
if (i == 0) sum[i] = arr[i]; else sum[i] = sum[i-1] + arr[i];
if (sum[i] < target) continue;
// find new closest
if (closest == -1)
if (sum[i] >= target) closest = 0;
while (closest <= i && sum[i] - sum[closest] + arr[closest] >= target){
closest++;
}
closest--;
if (sum[i] - sum[closest] + arr[closest] == target) {
for (int j = 0; j < i - closest + 1; j++)
cout << arr[closest + j] << " " ;
return;
}
}
cout << "No solution !" << endl;
}
This problem can be solved with complexity O(n) using deque: d[i] is the closest number on the right that is greater than numbers[i]:
- vucuong020195 July 14, 2016