phuocidi
BAN USERI use recursive to solve this one base on permutation. Since we can swap 2 consecutive characters in the given String, the program will concatenate the first letter with the rest.
If the given String has length of 0 or 1, then return. Otherwise, make a recursive call to the substring s[1:] . Then add back first character to all possible position
# Using python
def permutation(lst):
''' take a list of element and return a list of its permutation'''
if len(lst) == 0 or len(lst) == 1:
return [lst]
else:
outlst = []
for first in lst:
rest = list(lst)
rest.remove(first)
for restlst in permutation(rest):
outlst.append([first]+restlst)
return outlst
def perString(s):
lst = []
retLst =[]
for char in s:
lst.append(char)
ret = permutation(lst)
for word in ret:
show = ""
for char in word:
show += char
retLst.append(show)
return retLst
Result:
>>> perString('GUM')
['GUM', 'GMU', 'UGM', 'UMG', 'MGU', 'MUG']
there are 106-1 = 105 buildings distance from A to B or B to A.
when both meet, their total distance must equal 105. Hence we have this equation:
5P + 10P = 105
<=> P = 105/15 = 7
A passes 35 buildings,
B passes 70 buildings,
they met at building number 36.
At start : A-------------------------------B
when meet: ----------AB--------------------
public static boolean searchSum(int[] A) {
int sum = 0;
int halfsum = 0;
if (A.length <=2) {
return false;
}
else{
for(int i : A) {
sum += i;
}
if (sum % 2 != 0) return false;
else{
boolean res = false;
Arrays.sort(A);
halfsum = sum/2;
for (int j = 0; j < A.length-1; j++) {
int diff = halfsum - A[j];
int ret = Arrays.binarySearch(A, j+1, A.length, diff);
return (ret != -1);
}
return res;
}
}
}
Hi everyone,
I use Python for this question:
i and j are used as a pointer to the index number of characters in the given string.
###############################
def LCS(s):
i,j = 0,1
ret = ''
if len(s)==0 or len(s)==1:
return s
else:
ret = s[i:j]
while(j < len(s)):
if s[i] != s[j] or s[j]== s[:-1]:
# move both index to the next one
if j-i == 1:
i += 1
j += 1
else:
if len(ret) < (j-i): # if return string doesn't have maximum length
ret = s[i:j]
i += (j-i)
j += 1
else:
# find duplicated character, beginning character (is at i) remains the same while
# j moves to the next index to compare with character at i
j += 1
if len(ret) < (j-i):
ret = s[i:j]
return ret
- phuocidi April 09, 2015