Tweet
Chủ đề: backtracking
-
Last edited by toannv; 21-07-2015, 17:23. -
Draft code nè các bạn
PHP Code:/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
char** letterCombinations(char* digits, int* returnSize) {
strcpy(digits,"23");
char tel[9][3] = {{' ',' ',' '},{' ',' ',' '},{'a','b','c'},{'d','e','f'},{'g','h','i'}};
int i,j,S1,S2;
S1 = digits[0] - '0';
S2 = digits[1] - '0';
/* Do chỉ có 23 nên dùng 2 vòng lặp , nếu là 873 thì sẽ 3 vòng lặp in ra tel[0][i], tel[1][j], tel[2][k] */
for (i=0; i<3; i++)
for (j=0; j<3 ;j++)
printf("%c%c ",tel[S1][j],tel[S2][j]);
return NULL;
}
-
Minh họa chuyển qua đệ qui
PHP Code:#include <stdio.h>
#include <string.h>
char tel[9][3] = {{' ',' ',' '},{' ',' ',' '},{'a','b','c'},{'d','e','f'},{'g','h','i'}};
char result[3];
void DeQui(char* digits,int n)
{
int i,j,S;
if (n<0)
{
printf("%s\n",result);
return;
}
S = digits[n] - '0';
for (i=0; i<3; i++)
{
result[n]=tel[S][i];
DeQui(digits,n-1);
}
}
main()
{
DeQui("23",1);
}
Comment
-
Accepted
PHP Code:class Solution {
public:
vector <string> res;
char l[100];
string t[8]= {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
string d;
int n;
vector<string> letterCombinations(string digits) {
d=digits;
n=digits.length();
if (digits!="")
back(0);
return res;
}
void save(string l)
{
res.push_back(l);
}
void back(int i)
{
for (int k=0; k<t[d[i]-50].size(); k++)
{
l[i]=t[d[i]-50][k];
if (i<n-1) back (i+1);
else save(l);
}
}
};
Comment
-
Code chưa submit, ae xem hộ
PHP Code:#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int slip_num(int num)
{
int temp = 0;
while (num/10!=0)
{
temp+=num%10;
temp*=10;
num = num/10;
}
temp+=num;
return temp;
}
void Try(int num,int size, char *result)
{
int letter [] = {97,100,103,106,109, 112,116,119};
int temp = num%10;
temp-=2;
for (int i = 0; i<letter[temp+1]- letter[temp]; i++)
{
result[size] = letter[temp]+i;
if(num/10!=0)
Try(num/10, size+1, result);
else
{
for (int k = 0; k<= size;k++)
printf("%c", result[k]);
printf("\n");
}
}
}
int main()
{
char digits[] = "\"456\"";
char *pch;
pch = digits+1;
strncpy(pch, digits+1,strlen(digits+1)-1);
pch[strlen(pch) ] = '\0';
int num = atoi(pch);
num = slip_num(num);
char result [10];
Try(num,0, result);
}
:beauty:PHP Code:input: 456
output:
gjm
gjn
gjo
gkm
gkn
gko
glm
gln
glo
hjm
hjn
hjo
hkm
hkn
hko
hlm
hln
hlo
ijm
ijn
ijo
ikm
ikn
iko
ilm
iln
ilo
--------------------------------
Process exited after 0.01157 seconds with return value 0
Press any key to continue . . .
Last edited by 14520981; 22-07-2015, 09:42.Share to be shared !
http://thientoan.infoComment
-
Bài N-Queens viết theo 2 cách
PHP Code:#include <stdio.h>
#include <string.h>
#define MAX 6
main()
{
int D[MAX],C1[MAX*2],C2[MAX*2];
int i0,i1,i2,i3,i4,i5;
for (i0=0; i0<MAX; i0++)
{
D[i0]=0;
C1[i0*2]=0;C1[i0*2+1]=0;
C2[i0*2]=0;C2[i0*2+1]=0;
}
for (i0=0; i0<MAX; i0++)
if ((D[i0]==0) && (C1[i0+0]==0) && (C2[i0-0+MAX]==0))
{
D[i0]=1; C1[i0+0]=1; C2[i0-0+MAX]=1;
for (i1=0; i1<MAX; i1++)
if ((D[i1]==0) && (C1[i1+1]==0) && (C2[i1-1+MAX]==0))
{
D[i1]=1; C1[i1+1]=1; C2[i1-1+MAX]=1;
for (i2=0; i2<MAX; i2++)
if ((D[i2]==0) && (C1[i2+2]==0) && (C2[i2-2+MAX]==0))
{
D[i2]=1; C1[i2+2]=1; C2[i2-2+MAX]=1;
for (i3=0; i3<MAX; i3++)
if ((D[i3]==0) && (C1[i3+3]==0) && (C2[i3-3+MAX]==0))
{
D[i3]=1; C1[i3+3]=1; C2[i3-3+MAX]=1;
for (i4=0; i4<MAX; i4++)
if ((D[i4]==0) && (C1[i4+4]==0) && (C2[i4-4+MAX]==0))
{
D[i4]=1; C1[i4+4]=1; C2[i4-4+MAX]=1;
for (i5=0; i5<MAX; i5++)
if ((D[i5]==0) && (C1[i5+5]==0) && (C2[i5-5+MAX]==0))
{
D[i5]=1; C1[i5+5]=1; C2[i5-5+MAX]=1;
printf("%d %d %d %d %d %d\n",i0,i1,i2,i3,i4,i5);
D[i5]=0; C1[i5+5]=0; C2[i5-5+MAX]=0;
}
D[i4]=0; C1[i4+4]=0; C2[i4-4+MAX]=0;
}
D[i3]=0; C1[i3+3]=0; C2[i3-3+MAX]=0;
}
D[i2]=0; C1[i2+2]=0; C2[i2-2+MAX]=0;
}
D[i1]=0; C1[i1+1]=0; C2[i1-1+MAX]=0;
}
D[i0]=0; C1[i0+0]=0; C2[i0-0+MAX]=0;
}
}
PHP Code:#include <stdio.h>
#include <string.h>
#define MAX 8
int D[MAX],C1[MAX*2],C2[MAX*2];
int result[MAX];
void DeQui(int n)
{
int i;
if (n==MAX)
{
for (i=0; i<MAX; i++) printf("%d ",result[i]);
printf("\n");
return;
}
for (i=0; i<MAX; i++)
if ((D[i]==0) && (C1[i+n]==0) && (C2[i-n+MAX]==0))
{
D[i]=1; C1[i+n]=1; C2[i-n+MAX]=1;
result[n]=i;
DeQui(n+1);
D[i]=0; C1[i+n]=0; C2[i-n+MAX]=0;
}
}
main()
{
int i0,i1,i2,i3,i4,i5;
for (i0=0; i0<MAX; i0++)
{
D[i0]=0;
C1[i0*2]=0;C1[i0*2+1]=0;
C2[i0*2]=0;C2[i0*2+1]=0;
}
DeQui(0);
}
Comment
-
không hiểu sao chỉ đổi biến res từ char thành string thì lại không ra đúng kết quả :cry:
PHP Code:string tel[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
class Solution {
public:
vector<string> result;
string res;
vector<string> letterCombinations(string digits)
{
int k = 0;
int n = digits[0] - '0' - 2;
if (n >= 0 && n <= 7)
{
if (n == 5 || n == 7)
k = 4;
else k = 3;
}
for (int i = 0; i < k; i++)
{
res[res.length()] = tel[n][i];
if (digits.length() > 1)
letterCombinations(&digits[1]);
else
result.push_back(res);
res[res.length() - 1] = '\0';
}
return result;
}
};
/*Input:
"2"
Output:
["","",""]
Expected:
["a","b","c"]*/
PHP Code:string tel[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
class Solution {
public:
vector<string> result;
char res[100];
vector<string> letterCombinations(string digits)
{
int k = 0;
int n = digits[0] - '0' - 2;
if (n >= 0 && n <= 7)
{
if (n == 5 || n == 7)
k = 4;
else k = 3;
}
for (int i = 0; i < k; i++)
{
res[strlen(res)] = tel[n][i];
if (digits.length() > 1)
letterCombinations(&digits[1]);
else
result.push_back(res);
res[strlen(res) - 1] = '\0';
}
return result;
}
};
//Accepted
Comment
Comment