Giải bài trên CodeFights

#1

sortByHeight codefights python đã xong, Cám ơn bạn lala
Code của mình:

[details=sortByHeight]
def sortByHeight(a):
position = []
for i in range(0, len(a)):
if a[i] == -1:
position.append(str(i))
num = a.count(-1)
for i in range(0, num):
a.remove(-1)
a.sort()
for i in position:
a.insert(int(i), -1)
return a[/details]

Mình gặp lỗi khi giải hidden test ở bài này areSimilar: https://codefights.com/arcade/intro/level-4/xYXfzQmnhBvEKJwXP

Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements in one of the arrays.

Given two arrays a and b, check whether they are similar.

Example

For a = [1, 2, 3] and b = [1, 2, 3], the output should be
areSimilar(a, b) = true.

The arrays are equal, no need to swap any elements.

For a = [1, 2, 3] and b = [2, 1, 3], the output should be
areSimilar(a, b) = true.

We can obtain b from a by swapping 2 and 1 in b.

For a = [1, 2, 2] and b = [2, 1, 1], the output should be
areSimilar(a, b) = false.

Any swap of any two elements either in a or in b won’t make a and b equal.

Input/Output

[time limit] 4000ms (py)
[input] array.integer a

Array of integers.

Guaranteed constraints:
3 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ 1000.

[input] array.integer b

Array of integers of the same length as a.

Guaranteed constraints:
b.length = a.length,
1 ≤ b[i] ≤ 1000.

[output] boolean

true if a and b are similar, false otherwise.

Code của mình: (giải được 14/20 test)

def areSimilar(a,b):
  for i in range(len(a)):
    for j in range(i,len(a)):
      equal = True
      tmp = a[i]
      a[i] = a[j]
      a[j] = tmp
      for k in range(len(a)):
        if a[k] != b[k]:
          equal = False
          break
      if equal:
        return True
      a[j] = a[i]
      a[i] = tmp
  return False

Xin mọi người giúp đỡ và đưa ra giải thuật tốt hơn :smiley:

1 Like
#2
  • giới hạn của bài toán là bao nhiêu?
  • độ phức tạp của câu lệnh insert, remove là O(n), nên độ phức tạp của bài của bạn cỡ O(n2) có chạy dc không?
2 Likes
#3

Mình thay đổi một chút code của bạn nhé

def sortByHeight(a):
    position = []

    for i in range(0, len(a)):
        if a[i] == -1:
            position.append(i)
    num = a.count(-1)
    for i in range(0, num):
        a.remove(-1)
    a.sort()
    for i in position:
        a.insert(i, -1)
    return a

Mình dùng .append, không cần thiết phải dùng str() -> int() chưa kể nó còn gây ra lỗi như ở bài trên. Nếu muốn dùng thì bạn chỉ cần sửa position += str(i) thành position.append(str(i))
Mình ví dụ:
Nếu vị trí chữ số -1 < 10 thì không sao vì chỉ có 1 chữ số, nếu >= 10 thì ví dụ có -1 ở vị trí 11 thì position = ['1', '1']. Vậy nếu dùng for i in position: thì i sẽ nhận giá trị 1 hai lần chứ không phải là số 11. Bạn cứ thử với dùng code này cuối function của bạn để xem rõ hơn.

a = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 180, -1, -1, -1]
[a, num, position] = sortByHeight(a)
print(a, num, position)
1 Like
#4

cho code C# của mình hồi đó nè :joy:

int[] sortByHeight(int[] a) 
{
    var Output = new List<int>();
    foreach (var ahjhj in a)
        if (ahjhj>0)
            Output.Add(ahjhj);
    Output.Sort();
    for (int i=0;i<a.Count();i++)
        if (a[i]==-1) Output.Insert(i,-1);//thêm -1 vào vị trí i
    return Output.ToArray();
}
1 Like
#5

Cám ơn bạn, giờ mình với biết nó tách str(i) ra, mình nghĩ nó thêm vào luôn cơ.
Mình làm được rồi :smiley:

#6

Input/Output

[time limit] 4000ms (py)
[input] array.integer a

If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

Guaranteed constraints:
5 ≤ a.length ≤ 15,
-1 ≤ a[i] ≤ 200.

[output] array.integer

Sorted array a with all the trees untouched.

#7

Cám ơn bạn mặc dù mình chẳng hiểu gì :joy:

#8

À, thuật toán lúc đó mình đưa ra như thế này:

  • Tìm các số khác -1 ra trong mảng a và cho nó vào list Output
  • Sort cái Output đó
  • Duyệt mảng a, ở vị trí nào có -1 thì thêm -1 vào vị trí tương ứng ở Output
  • Xuất Output dưới dạng mảng.
1 Like
#9

Giúp mình bài tiếp theo với

#10

Cho code C# nè :joy:

bool areSimilar(int[] A, int[] B)
{
    var Difference = 0;//Số điểm khác biệt giữa A và B
    var First = 0;//2 biến này để lưu 2 vị trí mà A và B cần swap (nếu có)
    var Second = 0;
    for (int i = 0; i < A.Length; i += 1)
        if (A[i] != B[i])
        {
            Difference += 1;
            if (Difference == 1)
                First = i;
            else
                if (Difference == 2)
                    Second = i;
        }
    if (Difference == 0)
        return true;
    if (Difference != 2)
        return false;
    if (A[First] != B[Second])
        return false;
    if (A[Second] != B[First])
        return false;
    return true;
}
#11

Cho mình xin thuật toán với :smiley:

#12

Bạn tham khảo trên github xem. Tự đọc tự ngẫm :smile:

#13

Đề bài bảo là 2 mảng giống nhau hoặc đổi chỗ 1 cặp số mà giống nhau thì trả về true.
Cho một mảng, đổi chỗ 2 số khác nhau trong mảng đó thì sẽ ra mảng mới khác biệt với mảng ban đầu ở 2 (và chỉ 2) vị trí đó.

=> Ta có thuật toán:Đếm số điểm khác biệt giữa 2 mảng. Dùng 2 biến First và Second để lưu lại 2 vị trí đầu tiên mà 2 mảng khác nhau.

  • Nếu số khác biệt giữa 2 mảng là 0 thì trả về true
  • (>0) Nếu số khác biệt giữa 2 mảng khác 2 thì trả về false
  • (2) Nếu A[First] khác B[Second] hoặc A[Second] khác B[First] thì trả về false (vì nếu swap thì 2 mảng vẫn khác nhau)
  • Trả về true (vì 2 vị trí khác nhau đó thực ra là do đổi chỗ)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?