|
|
l*****s
发帖数: 279 | 3 2nd question
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
assert(l.length == w.length && l.length == p.length);
if (l.length == 0) return Integer.MIN_VALUE;
return maxValueRecur(l, w, p, L, W, 0);
}
public static int maxValueRecur(int[] l, int[] w, int[] p, int L, int W,
int value) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
if (len == 1) {
if (l[0] > L || w[0]... 阅读全帖 |
|
l*****s
发帖数: 279 | 4 2nd question
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
assert(l.length == w.length && l.length == p.length);
if (l.length == 0) return Integer.MIN_VALUE;
return maxValueRecur(l, w, p, L, W, 0);
}
public static int maxValueRecur(int[] l, int[] w, int[] p, int L, int W,
int value) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
if (len == 1) {
if (l[0] > L || w[0]... 阅读全帖 |
|
s*****y
发帖数: 897 | 5 can you give me your input to test.
I extend your solution in finding kth smallest element without calling it
two times.
I test
1. {1} {2}
2. {1}, {2,3}
3, {1,2}, {3,4}
4 {1,2} {4,5,6}
#define MAX(A,B) ((A) > (B) ? (A):(B))
#define MIN(A,B) ((A) < (B) ? (A):(B))
static int A[] = {2};
static int B[] = {1};
/* Find the Kth smallest element of sorted array A and B */
double Find_Kth_Smallest(int A[], int len1, int B[], int len2, int k, bool
divide)
{
int i, j;
int Ai, Ai_1, Bj, Bj_1; /* Ai_... 阅读全帖 |
|
Q*******e
发帖数: 939 | 6 翻译成C.
void
addBinary(char *arr1, char *arr2)
{
int i,j;
int len1 = 0, len2 = 0, len3;
char tmp, carry=0;
char *arrR;
char *arrT1 = arr1;
char *arrT2 = arr2;
while (*arrT1++) len1++;
while (*arrT2++) len2++;
len3 = (len1 > len2) ? len1 : len2;
arrR = (char*) malloc(len3 + 2);
len1--; len2--;
len3 = 0;
while ((len1>=0) || (len2>=0) || carry) {
tmp = carry;
if (len1 >= 0) tmp += (arr1[len1--] - '0');
if (len2 >= 0) tmp += (... 阅读全帖 |
|
b******7
发帖数: 92 | 7 1. merger sort a single linked list
template
ListNode * mergeHelper(ListNode * left, ListNode * right)
{
assert(left != NULL && right != NULL);
ListNode * head = NULL;
if(left->val < right->val)
{
head = left;
left = left->next;
}
else
{
head = right;
right = right->next;
}
while( left != NULL && right != NULL)
{
if(left->val < right->val)
{
... 阅读全帖 |
|
b*****n
发帖数: 482 | 8 How to check the top 2 objects? It seem we can only look at the top
object.
Another question is we have to check N-1 chars from the top of the
stack, where N is the length of the str2. If there are multiple
characters in str2 that are the same as its last char (e.g. accccbc),
then even if str1 is the same as string 2, we have to do extra check 4
times whenever we meet a 'c' in str1.
My idea is to have a companion array recording the maximum matched index
of the char sequence in str1. If there is... 阅读全帖 |
|
k*j
发帖数: 153 | 9 贴一个从后往前的DPcode。与lz的解法大同小异
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len1 = strlen(s);
int len2 = strlen(p);
int i,j;
vector > result(len1+1,vector (len2+1,0));
result[len1][len2] = 1;
for(j = len2-1;j>=0;j--){
if(*(p+j+1)=='*'){
result[len1][j] = result[len1][j+2];
... 阅读全帖 |
|
w*********r
发帖数: 18 | 10 int strcmpi (const char* csz1, const char* csz2)
{
int retval=0;
char *p1=NULL, *p2=NULL;
if((csz1 !=NULL) && (csz2 !=NULL))
{ int len1=0, len2=0;
len1=strlen(csz1);
len2=strlen(csz2);
if （len1>0) {
p1= new char [len1+1];
memset(p1,0,len1+1);
strcpy(p1, csz1);
for (int i=0;i
p1[i]=toupper (p1[i]);
}
}
|
|
h***o
发帖数: 1494 | 11 int TransferString(char* str1, char* str2)
{
if(!str1||!str2)
return -1;
int len1=strlen(str1);
int len2=strlen(str2);
int** t=new int[len1+1][len2+1];
for(int i=0;i
t[i][0]=i;
for(int j=0;j
t[0][j]=j;
for(j=1;j
for(i=1;i
{
if(str1[i]==str2[j])
d[i][j]=d[i-1][j-1];
else
{
d[i][j]=d[i-1][j]>d[i][j-1]?d[i][j-1]:d[i-1][j];
d[i][j]=d[i][j... 阅读全帖 |
|
w******g
发帖数: 189 | 12 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个word list 和一个target word，要求输出在word list 里跟target
word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
======================
#include
#include
#include
#include
using namespace std;
//k=1
// word_list = ['dat', 'bat', 'batt', 'beetle']
// similar(query, word_list)
// similar('cat', word... 阅读全帖 |
|
w******g
发帖数: 189 | 13 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个word list 和一个target word，要求输出在word list 里跟target
word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
======================
#include
#include
#include
#include
using namespace std;
//k=1
// word_list = ['dat', 'bat', 'batt', 'beetle']
// similar(query, word_list)
// similar('cat', word... 阅读全帖 |
|
发帖数: 1 | 14 题目如下：
String s1 = "
waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";
s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
四个。
----------------------------------------------------------------------
这里有解答，但是测试后发现不对（http://www.1point3acres.com/bbs/thread-145290-1-1.html）
结果测试sln.findMatches("aaaaaa", "a+a-") ，出来结果为0，不对
另外System.out.println(sln.fin... 阅读全帖 |
|
s******t
发帖数: 2374 | 15 Mmmm....let me write one:
list1:
1-> 2-> 3->4
list2:
5->6->3->4
int countlen(Node node){
int counter = 0;
while(node!=null) {node=node->next; counter++;}
return counter;
}
Node goNstep(Node root, int n){
while(n-->0) root=root->next;
return root;
}
Node getCommon(Node root1, Node root2){
int len1 = countlen(root1);
int len2 = countlen(root2);
if(len1 > len2) root1 = goNstep(root1, len1-len2);
else root2 = goNstep(root2, len2-len1);
while(root1!=NULL){
if(root1 == root2) brea |
|
w******p
发帖数: 166 | 16 来自主题: JobHunting版 - 经典面试题 http://en.wikipedia.org/wiki/Multiplication_algorithm
an implementation of the "lattice mul":
#include
#include
void box(const char* v1, const char* v2)
{
size_t len1 = strlen(v1);
size_t len2 = strlen(v2);
size_t lres = len1 + len2;
char res[lres+1];
size_t i1, i2;
for (i1 = 0; i1 < lres; i1 ++)
res[i1] = 0;
res[lres] = '\0';
for (i1 = 0; i1 < len1; i1 ++)
for (i2 = 0; i2 < len2; i2 ++)
{
int int1 = (int) (v1[len1-1-i1... 阅读全帖 |
|
h*********3
发帖数: 111 | 17 多谢分享。
我觉得还是有2个问题：
1）一个corner case: a[]={1} b[]={2}, 找第一个最小的，你的j会变成-1,溢出了
2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
是不够的， 一个例子
a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的，你的程序似乎是返回 5 .
写了一个c的，欢迎指正。
int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
{
int m1,m2;
int l1=max(0,k-len2-1),r1=min(len1-1,k-1);
if ( k == 1 )
return min(arr1[0],arr2[0]);
m1 = l1 + (r1-l1)/2;
m2 = k-(m1+1)-1;
while ( arr1[m1] != arr2[m2] && m1 <= min(len1-1,k-1) && m1 >= max(0,k-len2-1))
{
i... 阅读全帖 |
|
p*g
发帖数: 141 | 18 private static String strMultiple(String s1, String s2) {
int len2 = s2.length();
String rv = "";
for (int i = 0; i < len2; i++) {
String part = strMultipleChar(s1, s2.charAt(i));
rv = rv + "0";
rv = strSum(part, rv);
}
return rv;
}
private static String strSum(String s1, String s2) {
StringBuilder sb = new StringBuilder();
int carryin = 0;
int len1 = s1.length();
int len2 = s2.len... 阅读全帖 |
|
p*****3
发帖数: 488 | 19 //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
const int M = 100;
bool isMatchDP(const char* str, const char* pattern)
{
if (NULL == str || NULL == pattern)
return false;
int len1 = strlen(str);
int len2 = strlen(pattern);
bool DP[M][M] = { false }; //DP[len1+1][len2+1]
DP[0][0] = true;
for (int i = 1; i <= len2; )
{
if (pattern[i] == '*')
{
DP[0][i] = DP[0][i-1];
DP[0][i+1] = DP[0][i];
i += 2;
... 阅读全帖 |
|
d**e
发帖数: 6098 | 20 为什么要用笨法子呢？
brute force应该没问题啊。我没具体验证，我想大概应该是这样，
从string_1的第一个char开始循环，比如index是i，和string_2的
第一个char开始比较，index是j，遇到相同，侧两个string的index
都增一，否则看是否得到最长的的substring，然后string_1的index
复位回i，j侧增一，直到j=length(string_2)，然后到下一热循环(i+1)
下面为伪码
int len1 = length(string_1)
int len2 = length(string_2)
int max_len = 0
int left_idx = -1
int right_idx = -1
for i = 0 to len1 - 1
loop
k = i
tmp_max_len = 0
for(j = 0; j < len2 - 1; )
if string_1[k] == string_2[j]
then
k++
j++
|
|
i**********e
发帖数: 1145 | 21 这题蛮有意思的，我刚写完。
其实 idea 挺容易明白，我说一次给你听就明白了，但是没图解释起来比较费劲。这题
最复杂的地方其实就是选择怎么把数据结构结合起来。
一开始我以为要用 dp，其实 greedy 就可以了。
总复杂度是 O(N lg M)，N 为 str 的长度，M 为 pattern 的长度。
主要原因有个 lg M 是因为 STL map 里的 find() 函数复杂度为 O(lg M).
我用的是 map + queue + hashtable （有点吓人呵呵，可能我想太复杂了）。
我暂时还没想到怎么提升到 O(N)，应该是利用一个更好的数据结构吧。如果有高人知
道怎么提升到 O(N)，请指点一下吧~
这是我做的 test cases:
第一行是 string 和 pattern，
第二行是函数 return 的 start and end position，然后是 shortest substring。
cabeca cae
3 5 eca
cfabeca cae
4 6 eca
cabefgecdaecf cae
9 11 aec
cabwefgewcw... 阅读全帖 |
|
s******e
发帖数: 108 | 22 A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;
int indexStart =0;
int indexMaxLen =0;
HashMap map = new HashMap();
HashMap indexmap = new HashMap();
for ... 阅读全帖 |
|
s******e
发帖数: 108 | 23 A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;
int indexStart =0;
int indexMaxLen =0;
HashMap map = new HashMap();
HashMap indexmap = new HashMap();
for ... 阅读全帖 |
|
q********c
发帖数: 1774 | 24 Basic idea is use bit map.
Assume the max of the two arrays is Max. If it's not given, it can be
found
in linear time.
int* merge(int* a, int len1, int* b, int len2)
{
int[] array = new int[Max];
for(int i = 0; i < len1; ++i)
{
array[a[i]] = 1;
}
for(int i = 0; i < len2; ++i)
{
if(array[b[i]] != 1)
{ array[b[i]] = 1; }
}
int num = 0;
for(int i = 0; i < Max; ++i)
{
if(array[i] == 1)
{ num++; }
}
int[] list = new list[num];
int j = 0;
for(int i = 0; ... 阅读全帖 |
|
g***9
发帖数: 159 | 25 也贴个完整代码，序列shift移位的方法，把前一半的正数和后一半的负数对调但各自
顺序不变，
这个记得是编程珠玑的里的貌似。。
#include
#include
#include
#include
using namespace std;
void MySortImpl(vector &v, int b, int e) {
if (b >= e) {
return;
}
int m = (b + e) / 2;
MySortImpl(v, b, m);
MySortImpl(v, m+1, e);
int i, j;
i = m+1;
while (i-1 >= b && v[i-1] > 0) i--;
j = m;
while (j+1 <= e && v[j+1] < 0) j++;
int len1 = m - i + 1;
int len2 = j - (m+1) + ... 阅读全帖 |
|
U***A
发帖数: 849 | 26 暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, map
string> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}
for(int i=pos1+1; i
string s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.ins... 阅读全帖 |
|
U***A
发帖数: 849 | 27 暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, map
string> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}
for(int i=pos1+1; i
string s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.ins... 阅读全帖 |
|
l*****a
发帖数: 14598 | 28 比较array1[k/2] array2[k/2]
if = ,return
if array1[k/2]>array2[k/2] , array2[0..k/2]are definitely in the k smallest
then choose k/2 smallest
from array1[0..len1-1-k/2] array2[k/2+1..len2-1]
...
pay attention the boundary of the array. |
|
r****m
发帖数: 70 | 29 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
r****m
发帖数: 70 | 30 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
s*****g
发帖数: 3527 | 31 泉州小吃还漏了清真馆。俺小时候在泉州每次走过中山路上的清真馆，闻着店里飘出的
香味，哈拉子总是流了一地。当时就想，以后长大有钱了一定要来大吃一次。这个清真
馆还在不在？
还有一种的早餐卖的东西，应该叫“ho3 len1 dao4”, 就是用某种豆磨碎了怎么给蒸
出来的。当时俺爷爷住在中山路上，每天早上都有人带一篓这个东西沿街卖。买一碗5
分钱（当时可是改革开放之前，5分钱很大的）来下稀饭，闻着可真香。吃起来也很好
吃。可惜现在都不知道到哪儿去吃了。
小步知道不知道这些，俺今年底可能回国，到时应该回去泉州一趟，事先了解一下。 |
|
