Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
--------------------------------------------------
set up an dictionary and an array of values in order
pay attention to "4", "9", "19", "989", etc
先检查 == 4，再检查 == 9
COME_BACK
class Solution {
public:
string intToRoman(int num) {
unordered_map k;
k[1] = 'I';
k[5] = 'V';
k[10] = 'X';
k[50] = 'L';
k[100] = 'C';
k[500] = 'D';
k[1000] = 'M';
string s = "";
vector order = {1000,500,100,50,10,5,1};
for (int i = 0; i < 7; i++) {
if (num / order[i] < 0) continue;
if (num / order[i] == 4) {
s = s + k[order[i]] + k[order[i - 1]];
num %= order[i];
}else if (i + 1 < 7 && num / order[i + 1] == 9) {
s = s + k[order[i + 1]] + k[order[i - 1]];
num %= order[i + 1];
}else if (num / order[i] < 4){
for (int j = 0; j < num / order[i]; j++) {
s = s + k[order[i]];
}
num %= order[i];
}
}
return s;
}
};
另一种简单方法
class Solution {
public:
string intToRoman(int num) {
vector<string> roman = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
vector<int> numbers = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
string rt = "";
for (int i = 0; i < 13; i++) {
while (num >= numbers[i]) {
rt += roman[i];
num -= numbers[i];
}
}
return rt;
}
};
3 SumGiven an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
----------------------------------------------------------Solution #1, O(n^2) time, O(n) space.
Hash first, then find out all possible pairs, then check for existence of the remaining value
Time Limit Exceeded in large test cases, possibly 'cause of sort() and find() functions.
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > result;
if (num.size() < 3) {
return result;
}
unordered_map<int,int> mapping;
for (int i=0;i<num.size();i++) {
if (mapping[num[i]] == NULL) {
mapping[num[i]] = 1;
}else {
mapping[num[i]] = mapping[num[i]] + 1;
}
}
for (int i=0;i<num.size()-2;i++) {
for (int j=i+1;j<num.size()-1;j++) {
int target = -(num[i] + num[j]);
// check if target exists
if (mapping[target] != NULL) {
// check duplication
if ((num[i] == target && mapping[num[i]] == 1)
|| (num[j] == target && mapping[num[j]] == 1)) {
continue;
}
// check tri-plication
if (num[i] == num[j] && num[i] == target && mapping[num[i]] < 3) {
continue;
}
vector<int> t = {num[i],num[j],target};
sort(t.begin(),t.end());
if (find(result.begin(), result.end(), t) == result.end()) {
result.push_back(t);
}
}
}
}
return result;
}
};
Solution #2, O(n^2) time based on 2sum's algorithmsort first
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > result;
if (num.size() < 3) {
return result;
}
sort(num.begin(),num.end());
for (int i=0;i<num.size()-2;i++) {
int a = num[i];
int left = i+1;
int right = num.size() - 1;
// 2 sum
while (left < right) {
int b = num[left];
int c = num[right];
int sum = a + b + c;
if (sum == 0) {
vector<int> t = {a,b,c};
if (find(result.begin(), result.end(), t) == result.end()) {
result.push_back(t);
}
right--;
left++;
}else if (sum < 0) {
left++;
}else {
right--;
}
}
}
return result;
}
};
Update on Sep-10-2014 Solution #3, O(n^2), no need to check for duplicates of vectors
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > rt;
if (num.size() < 3) return rt;
sort(num.begin(),num.end());
for (int i = 0; i < num.size() - 2; i++) {
int end = num.size() - 1;
int start = i + 1;
if (i > 0 && num[i] == num[i -1]) {
continue;
}
while (start < end) {
int sum = num[i] + num[start] + num[end];
if (sum == 0) {
vector<int> v;
v.push_back(num[i]);
v.push_back(num[start]);
v.push_back(num[end]);
rt.push_back(v);
while (num[start] == num[start + 1]) {
start++;
}
while (num[end] == num[end - 1]) {
end--;
}
}
if (sum < 0) {
start++;
}else {
end--;
}
}
}
return rt;
}
};
Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> rt = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (left > i + 1 && nums[left] == nums[left - 1]) {
left++;
continue;
}
if (right < nums.length - 1 && nums[right] == nums[right + 1]) {
right--;
continue;
}
int sum = nums[left] + nums[right] + nums[i];
if (sum == 0) {
List<Integer> r = new ArrayList<>();
rt.add(r);
r.add(nums[i]);
r.add(nums[left]);
r.add(nums[right]);
left++;
right--;
}else if (sum < 0) {
left++;
}else {
right--;
}
}
}
return rt;
}
}
3Sum ClosestGiven an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
----------------------------------------------------
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int min = INT_MAX;
int retSum = 0;
sort(num.begin(),num.end());
for (int i=0;i<num.size()-2;i++) {
int a = num[i];
int left = i+1;
int right = num.size() - 1;
// 2 sum
while (left < right) {
int b = num[left];
int c = num[right];
int sum = a + b + c;
int dif = abs(sum - target);
if (dif < min) {
min = dif;
retSum = sum;
}
if (sum > target) {
right--;
}else {
left++;
}
}
}
return retSum;
}
};
No comments:
Post a Comment