骨骼现场两道

bhlpku 发表于 2020-12-6 07:12
第一题的解法看的不太明白。如果这样做最坏情况下的时间复杂度不是O(n^2) 吗

第一题应该可以严格O(n)
请看我楼上的回复

何曾渡光 发表于 2020-12-6 08:55
如果有调换这两个，如果没有选择第一个调换，然后更新map

请问这句是什么意思呀，会存在调换一次只减 ...

是啊，当两个字符串是  acb 和abd 时候，不就是调换成 abc 这样dif -1

flyingforce 发表于 2020-12-6 11:20
是啊，当两个字符串是  acb 和abd 时候，不就是调换成 abc 这样dif -1

啊是这个意思 我理解错题了以为是t和s里的字符相互调换。。 谢谢！

第二题怎么用递归做呢？等一个大神的答案

试着写了第一题，欢迎指正。顺便求米。

1. # coding: utf-8
   
2. """
   
3. 1. 给两个长度一样string S和T，如果在同一个位置上，两个string的字符不同，就是一个diff。
   
4. 比如“abc”和"abd"，最后一个字符分别是'c'和'd'，这两个string的diff就是1。
   
5. 现在我们要在S里交换两个字符的位置，使把S和T之间的diff尽量减到最小，
   
6. 返回两个被交换的字符的位置。面试官应该要求的是O（n）
   
7. """
   
8. 
   
9. class Solution:
   
10.     def swap_idx(self, S, T):
    
11.         assert len(S) == len(T)
    
12.         dct = {}
    
13. 
    
14.         # delta_diff == 2
    
15.         for idx, (s, t) in enumerate(zip(S, T)):
    
16.             if s != t:
    
17.                 key = f'{s}{t}'
    
18.                 key_swap = f'{t}{s}'
    
19.                 if key_swap in dct:
    
20.                     return (dct[key_swap], idx)
    
21.                 dct[key] = idx
    
22. 
    
23.         # delta_diff == 1
    
24.         dct1 = {}
    
25.         for idx, (s, t) in enumerate(zip(S, T)):
    
26.             if s != t:
    
27.                 if t in dct1:
    
28.                     return (dct1[t], idx)
    
29.             dct1[s] = idx
    
30.         return (None, None)
    
31. 
    
32. 
    
33. ######################################################################
    
34. # Tests
    
35. ######################################################################
    
36. import unittest
    
37. 
    
38. class Test(unittest.TestCase):
    
39.     def test_1(self):
    
40.         s = 'abcd'
    
41.         f = 'abdc'
    
42.         sol = Solution()
    
43.         # cd <-> dc
    
44.         self.assertEqual(
    
45.             sol.swap_idx(s, f),
    
46.             (2, 3)
    
47.         )
    
48. 
    
49.     def test_2(self):
    
50.         s = 'abcefdxad'
    
51.         f = 'abdefcxcb'
    
52.         sol = Solution()
    
53.         # cd <-> dc
    
54.         self.assertEqual(
    
55.             sol.swap_idx(s, f),
    
56.             (2, 5)
    
57.         )
    
58. 
    
59.     def test_3(self):
    
60.         s = 'abcexxxyyy'
    
61.         f = 'abxcxxxyyy'
    
62.         sol = Solution()
    
63.         # cd <-> dc
    
64.         self.assertEqual(
    
65.             sol.swap_idx(s, f),
    
66.             (2, 3)
    
67.         )
    
68. 
    
69.     def test_4(self):
    
70.         s = 'abcd'
    
71.         f = 'abef'
    
72.         sol = Solution()
    
73.         # cd <-> dc
    
74.         self.assertEqual(
    
75.             sol.swap_idx(s, f),
    
76.             (None, None)
    
77.         )
    
78. if __name__ == '__main__':
    
79.     unittest.main(verbosity=2)

复制代码

第一题就是bulls and cows的变体而且变更简单了。第二题的话BFS不一定是对。应该用递归，但是感觉写起来狠费劲啊。

这个第二相当有难度啊。  先问一下，每次更改一个char， 我感觉整个表达式的结果都要重新计算啊？ 有什么更好的办法吗？  另外用recursive， 感觉就是DFS啊， 就算找到结果，怎么能保证结果是最短的？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题怎么做啊？递归怎么写？

flyingforce 发表于 2020-12-6 06:58
前面一道题简单， 维护一个 Map  对象，保存所有没有找到match的t 的character以及位置， 任何时候看到一个 ...

你的思路应该是解决二元关系的？如果是A&B&C|D这种呢？分情况讨论肯定不行吧我想。