w****x
发帖数: 2483 | 1 一直认为面试出这么难得题真是过分啊！！
================= kth element in young tablet (M+N)log(numeric range)
solution ===========
const int M = 4;
const int N = 4;
int getOrder(int A[M][N], int tg)
{
int c = 0;
int i = 0;
int j = N-1;
while (i < M && j >= 0)
{
if (A[i][j] >= tg)
j--;
else
{
c += j+1;
i++;
}
}
return c+1;
}
int getKthMin(int A[M][N], int k)
{
if (k <= 0 || k > M*N)
return INT_MIN;
int nBe... 阅读全帖 |
|
w****x
发帖数: 2483 | 2 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
int getHeight(NODE* pNode, bool bLft)
{
int nRet = 0;
NODE* pIter = pNode;
while (NULL != pIter)
{
if (bLft)
pIter = pIter->pLft;
else
pIter = pIter->pRgt;
nRet++;
}
return nRet;
}
int getNum(int h)
{
return pow((double)2, h) -1;
}
int getNumberOfNodes(NODE* pRoot)
{
NODE* pNode = pRoot;
int h = get... 阅读全帖 |
|
w****x
发帖数: 2483 | 3
不知道有没有其他bug
int myatoi(const char* p)
{
assert(p);
int nFlg = 1;
if ('-' == *p)
nFlg = -1;
if ('-' == *p || '+' == *p)
p++;
if ('\0' == *p)
throw CException("Invalid expression");
int nRet = 0;
while('\0' != *p)
{
if (*p < '0' || *p > '9')
throw CException("Invalid character");
int nVal = *p - '0';
int nNew = nRet*10 + nFlg * nVal;
if (nRet != 0 && ((nNew & 0x80000000) != (nRet & 0x80000000)))
... 阅读全帖 |
|
w****x
发帖数: 2483 | 4
那个因该不是最优解，但是想法蛮独特的，是csdn上一个人告诉我的，后来我实现了一
下，很久以前做的。
===============================================================
// Find the kth element in young table
// young table is a two dimensional matrix with its rows and columns sorted
// Solution
// It's hard to find the kth element directly, but its easy to find how many
elements are smaller than a given number.
// So, use binary search to find a number which is bigger than k elements in
the young table. Then, travel through
// the table to the ele... 阅读全帖 |
|
w****x
发帖数: 2483 | 5 N queen
int _inner_get_ways(int pRec[], int n, int nCur)
{
if (nCur >= n)
return 1;
int nRet = 0;
for (int i = 0; i < n; i++)
{
bool bNoneAttack = true;
for (int j = 0; j < nCur && bNoneAttack; j++)
{
if (pRec[j] == i || abs(nCur - j) == abs(i - pRec[j]))
bNoneAttack = false;
}
if (bNoneAttack)
{
pRec[nCur] = i;
nRet += _inner_get_ways(pRec, n, nCur+1);
}
}
... 阅读全帖 |
|
w****x
发帖数: 2483 | 6 int _inner_get_ways(int pRec[], int n, int nCur)
{
if (nCur >= n)
return 1;
int nRet = 0;
for (int i = 0; i < n; i++)
{
bool bNoneAttack = true;
for (int j = 0; j < nCur && bNoneAttack; j++)
{
if (pRec[j] == i || abs(nCur - j) == abs(i - pRec[j]))
bNoneAttack = false;
}
if (bNoneAttack)
{
pRec[nCur] = i;
nRet += _inner_get_ways(pRec, n, nCur+1);
}
}
return n... 阅读全帖 |
|
w****x
发帖数: 2483 | 7 int CalculateContain(int a[], int n)
{
assert(a && n > 0);
int nRet = 0;
stack stk;
for (int i = 0; i < n; i++)
{
if (!stk.empty() && a[stk.top()] < a[i])
{
int nPrev = stk.top();
stk.pop();
while (!stk.empty() && a[stk.top()] <= a[i])
{
int nCur = stk.top();
stk.pop();
int nLimit = a[nCur] <= a[i] ? a[nCur] : a[i];
nRet += (nLimit - a[nPrev]) *... 阅读全帖 |
|
w****x
发帖数: 2483 | 8 struct NODE
{
vector vecGUID;
NODE* nodes[256];
NODE() { memset(nodes, 0, sizeof(nodes)); }
};
void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
{
if (NULL == pNode)
return;
if (k <= 0)
{
vec = pNode->vecGUID;
return;
}
_inner_get_guid(pNode->nodes[*str], str+1, k-1, vec);
}
vector getGUID(const char* str, NODE* pRoot, int k)
{
vector vecRet;
if (NULL == pRoot || NULL == str || *str == 0 ... 阅读全帖 |
|
w****x
发帖数: 2483 | 9
//Turn Roman number to decimal
//I(1), V(5), X(10), L(50), C(100), D(500), M(1000)
int GetNum(char c)
{
if (c == 'I' || c == 'i')
return 1;
else if (c == 'V' || c == 'v')
return 5;
else if (c == 'X' || c == 'x')
return 10;
else if (c == 'L' || c == 'l')
return 50;
else if (c == 'C' || c == 'c')
return 100;
else if (c == 'D' || c == 'd')
return 500;
else if (c == 'M' || c == 'm')
return 1000;
return 0;
}
... 阅读全帖 |
|
w****x
发帖数: 2483 | 10 /*
Say you have an array for which the ith element is the price of a given
stock on day i.
Design an algorithm to find the maximum profit. You may complete as many
transactions as you like (ie, buy one and sell one share of the stock
multiple times). However, you may not engage in multiple transactions at the
same time (ie, you must sell the stock before you buy again).
*/
class Solution {
public:
int maxProfit(vector &a) {
int n = a.size();
int* rec = new int[n]... 阅读全帖 |
|
w****x
发帖数: 2483 | 11 发现这道题属于没见过肯定想不出来，知道怎么解也很难写对。昨天重新写了一下，觉
得学到蛮多的，分享一下。
以前写过一个很挫的DP版本：
int GetEditDist(const char* str1, const char* str2)
{
assert(str1 && str2);
int nLen1 = strlen(str1);
int nLen2 = strlen(str2);
int* rec = new int[nLen2];
bool bFound = false;
for (int i = 0; i < nLen2; i++)
{
if (str2[i] == str1[0])
bFound = true;
rec[i] = bFound ? i : i+1;
}
bFound = (str2[0] == str1[0]); //(str2[0] == str1[0]) not false
for (int i = 1; i < nLe... 阅读全帖 |
|
w***o
发帖数: 109 | 12 倒着来想法很新颖，但好像有问题，比如 IVX = (V - I) + X, not (X - V - I)
const char* pIter = szNum + nLen - 1;
int nRet = 0;
int nPrev = 0;
while (pIter >= szNum)
{
int nCur = GetNum(*pIter);
if (nCur >= nPrev)
nRet += nCur;
else nRet -= nCur;
nPrev = nCur;
pIter--;
} |
|
w****x
发帖数: 2483 | 13 int _inner_ways(const char* pStr)
{
if (*pStr == 0)
return 1;
if (*pStr <= '0' || *pStr > '9')
return 0;
int n = _inner_ways(pStr+1);
if ((*pStr == '1' && *(pStr + 1) >= '0' && *(pStr + 1) <= '9')
|| (*pStr == '2' && *(pStr + 1) >= '0' && *(pStr + 1) <= '6'))
n += _inner_ways(pStr+2);
return n;
}
int GetWays(const char* pStr)
{
if (NULL == pStr || *pStr == 0)
return 0;
return _inner_ways(pStr);
}
int GetWaysDP(const char* pStr)
... 阅读全帖 |
|
w****x
发帖数: 2483 | 14 vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - flg > 0)
{
vec.push_back(nCur - flg);
flg = (flg << 1);
}
return vec;
}
int getMinStep(int n, int nMaxStep)
{
if (n <= 0 || nMaxStep < n)
return -1;
int* rec = new int[nM... 阅读全帖 |
|
d**********x
发帖数: 4083 | 15 应该没问题，和coldknight的程序在2-10000之内做了对比，结果完全一致。他的
nMaxStep我设置为了2 * target，不知道会不会引起问题。
在纸面上也做了不太严格的证明。。这样复杂度就是O(logn)。
对比程序：（前半部分还是coldknight的）
#include
#include
#include
using namespace std;
vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - ... 阅读全帖 |
|
