Vova
BAN USERHere is my solution using backtracking. First we will find the sum of max scaled path and then we will find the actual path.
#include <iostream>
using namespace std;
int MaxPath(int** mat,int n,int row,int col)
{
if (row >= n ||col >= n) return 0;
return mat[row][col] + max<int>(
MaxPath(mat,n,row+1,col),
MaxPath(mat,n,row+1,col + 1) );
}
bool PrintmaxPath(int** mat,int n,int row,int col,int pathLength)
{
if(row >= n || col >= n )
if(pathLength == 0)return true;
else return false;
if(PrintmaxPath(mat,n,row+1,col,pathLength - mat[row][col]))
{
cout<<mat[row][col]<<'\t';
return true;
}
if(PrintmaxPath(mat,n,row+1,col + 1,pathLength - mat[row][col]))
{
cout<<mat[row][col]<<'\t';
return true;
}
}
int main(int argc, char** argv) {
int n;
cin >> n;
int ** mat = new int* [n];
for(int i = 0; i < n; i++)
mat[i] = new int [n];
for(int i = 0; i < n ; i++)
for(int j = 0; j <= i; j++)
cin >> mat[i][j];
int maxL = MaxPath(mat,n,0,0);
PrintmaxPath(mat,n,0,0,maxL);
cout << " Max weight is: "<<maxL<<endl;
return 0;
}
Hi mates. I suggest to find min element using heapify approach, the code below is the implementation, what about assignments, the count of assignments is O(n)
#include <iostream>
using namespace std;
void minHeap(int aArr[],int aRoot,int aSize)
{
int left = 2*aRoot;
int right = 2*aRoot + 1;
int lMin = aArr[aRoot];
if(left < aSize && aArr[lMin] > aArr[left]) lMin = left;
if(right < aSize && aArr[lMin] > aArr[right])lMin = right;
if(lMin != aRoot)
swap(aArr[aRoot],aArr[lMin]);
}
void Heapify(int aArr[],int aSize)
{
for(int i = aSize/2; i >= 0; --i)
minHeap(aArr,i,aSize) ;
}
int main()
{
int Arr[] = {3,7,9,7,4,15,8};
Heapify(Arr,sizeof(Arr)/sizeof(int));
cout << Arr[0];
return 0;
}
Here is my solution by templates.
#include "stdafx.h"
#include<iostream>
using namespace std;
const int cMaxSize = 100;
template<typename T>
class OneDimArr
{
public:
OneDimArr(int aSize = cMaxSize)
{
m_Elems = new T[aSize];
}
~OneDimArr()
{
delete []m_Elems;
}
T& operator[](int aIndex)
{
return m_Elems[aIndex];
}
private:
T* m_Elems;
int m_Size;
};
int _tmain(int argc, _TCHAR* argv[])
{
OneDimArr<int> oneDimArr;
OneDimArr<OneDimArr<int> > twoDimArr;
OneDimArr<OneDimArr<OneDimArr<int> > > threeDimArr;
oneDimArr[0] = 8;
twoDimArr[0][2] = 23;
threeDimArr[1][0][3] = 8;
cout << oneDimArr[0] <<'\t'<<twoDimArr[0][2] << '\t'<< threeDimArr[1][0][3]<<endl;
return 0;
}
I suggest to keet three maps, all operations are 3*(operation for map) I think it would be not much, here is implementation.
#include "stdafx.h"
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<list>
using namespace std;
class MultipleKey
{
public:
void insert(vector<int> aKeyList,int aVal)
{
m_MK_1.insert(pair<int,int>(aKeyList[0],aVal));
m_Ptr ptr = m_MK_1.find(aKeyList[0]);
m_MK_2.insert(pair<int,m_Ptr>(aKeyList[1],ptr));
m_MK_2.insert(pair<int,m_Ptr>(aKeyList[2],ptr));
}
private:
typedef map<int,int>::iterator m_Ptr;
map<int,int> m_MK_1;
map<int,m_Ptr> m_MK_2;
map<int,m_Ptr> m_MK_3;
}
;/**/
int _tmain(int argc, _TCHAR* argv[])
{
MultipleKey obj;
vector<int> vec(3);
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
obj.insert(vec,999);
return 0;
}
Here is my solution in C++, anagram function takes complexity n*m and the other liner.
#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
bool isAnagram(string s1,string s2)
{
int s_IT;
if ( s1.length() != s2.length()) return false;
for(int i = 0; i < s1.length(); i++)
{
s_IT = s2.find(s1[i]);
if(s_IT == string::npos) return false;
else
s2.erase(s_IT,1);
}
return s2.empty();
}
void findInd(string s2,string s1)
{
int len = s1.length();
for(int i = 0; i < s2.length() - len + 1; i++)
{
string s3 = s2.substr(i,len);
if (isAnagram(s3,s1))
cout << i <<endl;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
string s1 = "abcd";
string s2 = "abcdefcdbacd";
findInd(s2,s1);
return 0;
}
#include<iostream.h>
#include<string.h>
string reverse (string src)
{
int i = 0, j = src.length() - 1;
while(i < j)
{
char temp = src.at(i);
src.at(i) = src.at(j);
src.at(j) = temp;
i++;
j--;
}
return src;
}
string intToString(int src)
{
string result;
do
{
int res = (int)'0' + src%10;
src = src/10;
result.push_back(res);
}
while(src != 0);
return reverse(result);
}
int main(int argc, char* argv[])
{
string str;
float f = 7.65;
int intPart = (int)f;
int decPart = 0;
float temp = f - int(f);
while(temp - (int)temp != 0.0)
{
temp = temp*10;
}
decPart = temp;
str = intToString(intPart)+ '.'+ intToString(decPart);
cout << str;
cin.get();
return 0;
}
In BSS section stored only static variables by default initializing 0. The non-static variables don't store in BSS part! One of the differences of static and non static declarations is that static variables seen only in file where declared non static variables you can use in other files.
- Vova August 15, 2013
Repammiwilson5, Personnel at BMO Harris Bank
Hi I am Ammy from Served on a research team for improved customer satisfaction survey process,Moderated focus groups to ...
The solution that you introduce is the solution in linear complexity not in logarithmic.
- Vova June 30, 2015