s*****y
发帖数: 897 | 1 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 | 2 翻译成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 | 3 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 | 4 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... 阅读全帖 |
|
发帖数: 1 | 5 题目如下：
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... 阅读全帖 |
|
p*g
发帖数: 141 | 6 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... 阅读全帖 |
|
k*j
发帖数: 153 | 7 贴一个从后往前的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];
... 阅读全帖 |
|
发帖数: 1 | 8
不明白；len2肯定是偶数， java里 len2/2+1和(len2+1)/2+1等于相同的整数，没有
区别啊；
另外把所有所有len2 / 2 + 1改成(len2+1)/2+1， 这里报了错index out of range
error
.....
for (int j = 0; j < len2 / 2; j++){
dp[i + 1][j + 1] = dp[i][j + 1];
..... |
|
h***o
发帖数: 1494 | 9 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... 阅读全帖 |
|
s******e
发帖数: 108 | 10 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 | 11 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 ... 阅读全帖 |
|
p*****3
发帖数: 488 | 12 //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;
... 阅读全帖 |
|
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... 阅读全帖 |
|
w******g
发帖数: 189 | 14 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个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... 阅读全帖 |
|
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... 阅读全帖 |
|
g***9
发帖数: 159 | 18 也贴个完整代码，序列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) + ... 阅读全帖 |
|
c********p
发帖数: 1969 | 19 我的跑不过的。。。
import java.util.*;
public class Solution {
public ArrayList> findLadders(String start, String end
, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
if(dict.isEmpty()){
return ret;
}
int len = 1;
int len2 = 0;
Queue q = new LinkedList();
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 20 这题蛮有意思的，我刚写完。
其实 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... 阅读全帖 |
|
d**e
发帖数: 6098 | 21 为什么要用笨法子呢？
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++
|
|
q********c
发帖数: 1774 | 22 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; ... 阅读全帖 |
|
U***A
发帖数: 849 | 23 暴力法行吗？
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 | 24 暴力法行吗？
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... 阅读全帖 |
|
p**r
发帖数: 5853 | 25 把代码里所有len2 / 2 + 1改成(len2+1)/2+1就可以了
programming |
|
w*********r
发帖数: 18 | 26 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]);
}
}
|
|
l*****a
发帖数: 14598 | 27 比较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. |
|
g**********y
发帖数: 14569 | 28 谢谢指出错误，我写边界条件总容易出错，还是考虑不周密。
arr2[],int len2,int k) |
|
s*****y
发帖数: 897 | 29 How about this one?
int Find_KthElement(int A[], int m, int B[], int n, int k)
{
if (k > m+n)
return 0;
if (m > n) {
return Find_KthElement(B,n,A,m,k);
}
int lo = 0;
int hi = min(m,k)-1;
while (lo < hi) {
int mid = lo + (hi-lo)/ 2;
int bIndex = k - mid - 2;
if (A[mid] < B[bIndex]) {
lo = mid +1;
} else {
hi = mid;
}
}
... 阅读全帖 |
|
j****2
发帖数: 3211 | 30 桑心的理由～，坠爱你滴len2似偶你肿么舍得偶难过。。。呜呜呜。。。喵娃纸都桑心
了，他娘桑心并狂了。。。 |
|
N****f
发帖数: 25759 | 31 古韵派和今韵派在诗词界争论也有些年头了；俺向来还是倾向今韵。诗词归根
结底是有声艺术，以吟诵为最终目的。古人诵诗必用古音，今人诵诗必用今音
——对俺来说就是京腔、国语、普通话。古体诗词妙处首先在于音律工整精致，
而今人依照古韵赋诗填词，读来反而不合音律，未免买椟还珠。古音中“店”与
“殿”、“针”与“真”不同韵，对现代汉语普通话来说已经没有意义。入声消失更是
给平仄、音韵带来极大冲击，李易安笔下，“黑”、“得”、“急”、“摘”本属同韵，
但今人如果照方抓药，读来反而不顺。
同理，俺对用各地方言赋诗填词绝不反对，平仄、韵律大可以一律以诵读发音
为标准。本朝毛太祖名句“黄洋界上炮声隆，报道敌军宵遁”的韵脚，就得用湘
音读来才算顺耳（len2、den4）。 |
|
M******8
发帖数: 10589 | 32 北方人，不知道藍荒伦（念len2）l、n、r不分。
老李，拿牛奶！
你让藍荒伦、特别是浮藍伦煉一遍。 |
|
