simon.zhangsm
BAN USER//dp[i][j]: the minimal adjust cost on changing A[i] to j, dp[i][j] = min{dp[i-1][k] + |j-A[i]|} s.t. |k-j| <= target
#define MAXTARGET 100
int MinAdjustmentCost(vector<int> & A, int target){
if(A.empty()) return 0;
int dp[A.size()][MAXTARGET+1];
for (int i = 0; i <= MAXTARGET; ++i)
dp[0][i] = abs(i-A[0]);
for(int i=1; i<A.size();i++){
for(int j=0;j<=MAXTARGET;j++){
dp[i][j] = -1;
if (dp[i-1][j] < 0) continue;
for (int k = max(j-target, 0); k<=min(MAXTARGET, j+target); ++k) {
dp[i][k] = min(dp[i][k], dp[i-1][j] + abs(A[i]- k));
}
}
}
int ret = -1;
for (int i = 1; i <= MAXTARGET; i++) {
ret = min(ret, dp[A.size()-1][i]);
}
return ret;
}
A good DFS problem. Need to set 2 pointers, one in the pattern, and one in the string. Additionally, maintain a map to keep track of the mapping between a pattern letter and a substring.
bool isMatch(string str, int iStr, string ptn, int iPtn, unordered_map<char, string> &hmap){
if(iStr == str.size() && iPtn == ptn.size()) return true;
if(iStr == str.size() || iPtn == ptn.size()) return false;
char c = ptn[iPtn];
if(hmap.find(c)!=hmap.end()){
string toMatch = hmap[c];
for (int i = 0; i < toMatch.size(); i++) {
if (iStr >= str.size() || str[iStr] != toMatch[i])
return false;
istr++;
}
return isMatch(str, istr, ptn, iPtn+1, hmap);
}
//try all possiblities
bool flag = false;
for (int i = iStr; i < str.size(); i++){
hash[c] = str.substr(iStr, i - iStr + 1);
flag |= isMatch(str, i + 1, ptn, iPtn + 1, hmap);
hmap.erase(c);
if(flag) return true;
}
return false;
}
bool isMatch(string str, string ptn){
if(str.size()<ptn.size()) return false;
if(ptn.empty()) return str.empty()? true : false;
if(ptn.size()==1) return str.size()>1? true : false;
unordered_map<char, string> hmap;
return isMatch(str, 0, ptn, 0, hmap);
}
#define MAXTARGET 100
int MinAdjustmentCost(vector<int> A, int target) {
if (A.empty())
return 0;
int cur = 0;
// dp[i][j]: the minimal adjustment for change A[i] into j; dp[i][j] = min{dp[i-1][k] + |j-A[i]|} s.t. |k-j| <= target
int dp[2][MAXTARGET + 1];
memset(dp, 0x00, sizeof(dp));
for (int i = 0; i < A.size(); i++) {
int next = cur ^ 1;
for (int j = 1; j <= MAXTARGET; j++) {
dp[next][j] = INT_MAX;
for (int k = max(j-target, 1); k <= min(MAXTARGET, j+target); k++)
dp[next][j] = min(dp[next][j], dp[cur][k] + abs(A[i]-j));
}
cur ^= 1;
}
int ans = INT_MAX;
for (int i = 1; i <= MAXTARGET; i++)
ans = min(ans, dp[cur][i]);
return ans;
}
enum DIRECTS{S=4, W=3, N=2, E=1, SW=12, NW=6, SE=9, NE=3};
typedef unsigned char Byte;
struct Data{
int i;
DIRECTS op;
int j;
Data(int ii, DIRECTS oop, int jj):i(ii), op(oop), j(jj){}
};
bool validPoints(vector<Data> &dset){
if(dset.empty()) return true;
unordered_map<int, Byte> hmap;
for(auto &e:dset){
if(hmap.find(e.i)==hmap.end())
hmap[e.i] = 0;
Byte j = hmap[e.i] ^ e.op;
if(hmap.find(e.j)!=hmap.end() && hmap[e.j]&j!=0)
return false;
hmap[e.j] = j;
}
return true;
}
struct CTreeNode{
int count;
int val;
CTreeNode *left;
CTreeNode *right;
CTreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
CTreeNode *findNodeInOrder(CTreeNode *root, int k){
if(root==nullptr || k<0 || k>root->count) return nullptr;
if(k==root->count){
if(root->right==nullptr)
return root;
return findNodeInOrder(root->right, root->count);
}
if(root->left!=nullptr){
if(root->left->count>=k)
return findNodeInOrder(root->left, k);
else if(root->left->count==k-1)
return root;
else
return findNodeInOrder(root->right, k-root->left->count-1);
}
return findNodeInOrder(root->right, k);
}
//O(kn) O(k) space
int maxprofile(vector<int> &prices, int k){
if(prices.size()<2 || k<1) return 0;
int global[k+1];
int local[k+1];
memset(global, 0x00, sizeof(global));
memset(local, 0x00, sizeof(local));
for(int i=1; i<prices.size();i++){
int diff = prices[i] - prices[i-1];
for(int j=k; j>0; j--) {
local[j] = max(global[j-1]+max(diff, 0),local[j]+diff);
global[j] = max(local[j], global[j]);
}
}
return global[k];
}
//O(nlogn)
int maxProfile(vector<int> &prices, int k){
if(prices.size()<2 || k<1) return 0;
vector<int> positiveProfile;
int minp = prices[0];
for(int i=1; i<prices.size();i++){
if(prices[i]>=prices[i-1]) continue;
positiveProfile.push_back(prices[i-1]-minp);
minp = prices[i];
}
positiveProfile.push_back(prices[prices.size()-1]-minp);
sort(positiveProfile.begin(), positiveProfile.end());
int maxKprofile = 0;
for(int i=0; i<k && positiveProfile.size()-i>=0; i++)
maxKprofile += positiveProfile[positiveProfile.size()-1-i];
return maxKprofile;
}
1 3 9 27
1. turn on one switch for 5 minutes and turn off
2. turn on another switch
3. go upstair and the light bulb is for the turning switch, the hot bulb for first turned switch(turn on for 5 minutes) and the last one is for the third switch
1.5 teenagers eat 1.5 pizzas in 1.5 days
9 teenagers eat ?? pizzas in 3 days
*6 *6*2 *2
1.5*6*2=18
2^60V=jar==>2^59=jar/2
vector<double> solveQuadraticEquation(int a, int b, int c){
const double epsilon = 0.0000001;
double discrimnant = b*b - 4.0*a*c;
vector<double> res;
if(abs(discrimnant) <= epsilon){
res.push_back(-b/2.0/a);
}
if(discrimnant>epsilon){
discrimnant = sqrt(discrimnant);
res.push_back((-b + discrimnant)/2.0/a);
res.push_back((-b - discrimnant)/2.0/a);
}
return res;
}
Obviously, this problem must use bit operation to store the stats sine at each cell we only has three status: empty (00), occupied by X(01), and occupied by O(10). So each cell can be stored by two bits. So we only need 2*2^31*2^31 bits to store the configure. That's right.
- simon.zhangsm December 10, 2014bool existSum(int sortedA[], int n, int sum){
int i=0, j=n-1;
while(i<j){
int mid = ((i + j)>>1);
if(sortedA[mid]>sum)
j = mid-1;
else
i = mid+1;
}
i = 0;
while(i<j){
if(sortedA[i]+sortedA[j] == sum)
return true;
if(sortedA[i]+sortedA[j] > sum)
j--;
else
i++;
}
return false;
}
int MinIntNotSum(int A[], int n){
if(A==nullptr || n<1) return 0;
sort(A, A+n); //O(nlgn)
int minSum = A[0]+A[1];
while(existSum(A,n,minSum))
minSum++;
return minSum;
}
- simon.zhangsm February 23, 2015