w****x
发帖数: 2483 | 1 发现这道题属于没见过肯定想不出来，知道怎么解也很难写对。昨天重新写了一下，觉
得学到蛮多的，分享一下。
以前写过一个很挫的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... 阅读全帖 |
|
b***m
发帖数: 5987 | 2
刚刚花了一点儿时间写了代码，后来发现跟150上的思路差不多。没什么特别的，凑数
吧，还在考虑怎么优化。
void DoubleColumn(int **ppn, int nNumRows, int idCol)
{
if( !ppn ) return;
for( int i = 0; i < nNumRows; i++ )
{
ppn[i][idCol] *= 2;
}
}
void DecreaseRow(int **ppn, int nNumCols, int idRow)
{
if( !ppn ) return;
for( int i = 0; i < nNumCols; i++ )
{
ppn[idRow][i]--;
}
}
vector GetColsWithMinValue(int **ppn, int nNumCols, int idRow)
{
int i, nMin = MAX_INT;
vector vecMinCols;
... 阅读全帖 |
|
w****x
发帖数: 2483 | 3 迭代法:
//Find the nth number which is composed by factor 2, 3 and 5
void PrintSerials(int n)
{
assert(n > 0);
vector vec;
vec.push_back(1);
int nI2 = 0;
int nI3 = 0;
int nI5 = 0;
int nCount = 1;
while(nCount < n)
{
int nTmp2 = vec[nI2]*2;
int nTmp3 = vec[nI3]*3;
int nTmp5 = vec[nI5]*5;
int nMin = min(min(nTmp2, nTmp3), nTmp5);
if (vec.back() != nMin)
{
vec.push_back(nMin);
nCount++;
... 阅读全帖 |
|
w****x
发帖数: 2483 | 4 //least cost to cut a batten
//the cost of cutting each segment is the cost of the segment length, an
array is storing each end point, eg:
// [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
//No greedy solution to this problem
int getMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int rec[100][100] = {0};
for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
for (... 阅读全帖 |
|
w****x
发帖数: 2483 | 5 打印版本，真难做对：
int printMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int recCost[100][100] = {0};
int recSplit[100][100] = {0};
for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
int nSplitIndex = 1;
for (int k = 1; k < i; k++)
{
int nCost = recCost[j][j+k] + recCost[j+k][j+i] + a[j+i] - a
[j];
if (nCost < nMin)
... 阅读全帖 |
|
w****x
发帖数: 2483 | 6 //least cost to cut a batten
//the cost of cutting each segment is the cost of the segment length, an
array is storing each end point, eg:
// [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
//No greedy solution to this problem
int getMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int rec[100][100] = {0};
for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
for (... 阅读全帖 |
|
w****x
发帖数: 2483 | 7 打印版本，真难做对：
int printMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int recCost[100][100] = {0};
int recSplit[100][100] = {0};
for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
int nSplitIndex = 1;
for (int k = 1; k < i; k++)
{
int nCost = recCost[j][j+k] + recCost[j+k][j+i] + a[j+i] - a
[j];
if (nCost < nMin)
... 阅读全帖 |
|
r*c
发帖数: 167 | 8 贴个pattern字符串有重复字符的解法， 是dek,cpp1等大牛的解法的扩展。
#include
#include
#include
#include
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN -2147483648
class MinWindowSolution
{
public:
struct TreeNode
{
TreeNode *parent;
int val;
vector children;
TreeNode(int i, TreeNode *p) : val(i), parent(p){}
};
void FindMinWindow_Tree(const vector& input , const vector&
query , int& nStart,... 阅读全帖 |
|
r*c
发帖数: 167 | 9 之前写了个C#的。思路都一样， use tree matching algorithm to determine the
candidate window.
//using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
class MinWindowSolution
{
class TreeNode
{
public TreeNode parent;
public int val;
public List children;
public TreeNode(int i, TreeNode p) { val = i; parent = p; children =
new List(); }
};
public void FindMinWindow_Tree(int[] input, int[] query, out int nS... 阅读全帖 |
|
x*****0
发帖数: 452 | 10 The question is:
Check if a binary tree is a valid binary search tree.
I guess I can pass the definition of the binary search tree in this forum. :
-). I know this is a very basic question and have a lot of solutions with O(
N) time complexity and O(1) space complexity.
Since I'm practicing how to use bottom-up traversal skill, Let's restrict
the answer must be bottom-up traversal algorithm.
The following is my idea.
Using "min" and "max" to represent the minimum value of left sub-tree and
maxim... 阅读全帖 |
|
w*******p
发帖数: 253 | 11 Run slab mode analysis first (no ridge shape), find the 1st order mode Nref
of slab mode.
When you simulate the slab with ridge, use the above index as the Nmin to
make sure the slab mode will not be included. |
|
w*******p
发帖数: 253 | 12 It doesn't matter that much, you can the width which is close to your real s
ituation.
Use this 0th mode of the slab as Nmin when you simulate ridge structure, the
simulation will only show the fundamental mode of the ridge structure. |
|
w*******p
发帖数: 253 | 13 1. This Neff is ok to be used as Nmin when you calculate ridge structure.
2. Marcatili has a famous paper on this topic, you may want to read it. The formular is for approximate calculation, not accurate. I am not sure if Rsoft uses very fine meshes near boundaries, if you say "the width can be up to 2.5um", you really want to make sure you are in the middle of some safe region, which allows calculation/process tolerance. For example, if the Rsoft calculation and formular give you different sing |
|
