duangsuse::Echo

#algorithm #bing 二分查找 spiral sorted ndarray
最好把它转换为1d，再转换回来以获取 '1'的位置
#py #code

def unrot(a, out):
  while a.size:
    out.extend(a[0]); a=np.rot90(a[1:])

#难以用concat矩阵滚出螺旋
def rot(a, m):
  ia=np.reshape(range(len(a)), (m,-1))
  unrot(ia, ord:=[])
  return np.vectorize(lambda i:a[ord.index(i)] )(ia)

#make range(0,9) a spiral(cols=3)
[[0 1 2]
 [7 8 3]
 [6 5 4]]
a=rot([*range(0,9)], 3)
unrot(a, na:=[])

na[na.index(4)]=-1
print(a)
np.where(rot(na,3)==-1) #'4'=>[2,2]

def binary_search_matrix(matrix, target): 同理，可以是2d转1d
def binary_search_first_last(*a):
  import bisect
  left,right = (f(*a)for f in [bisect.bisect_left, bisect.bisect_right])
  # 如果右边界超出了数组范围，说明目标出现1次
  return (left, left if right == len(nums) else right - 1)

感觉很无语，居然为了无意义的“高性能”算法浪费2h ，还不如直接就用自己本来会的 a[ord.index(i)] 序号对应..

我发现2d.bisect 是以 (row=a[i])[0] 为线索再去 row.bisect ，这就更无聊了。Trie 前缀树至少还有 AC 的优化版(窄化为 KMP )，kD/quad 树至少还有切割公式，RB树有 std::(orderd_)map，但bisect 对Nd都只是Trie那样剪枝..
我觉得放在现实语境下就理所当然的策略，根本不该叫算法…

我很好奇除了用等价关系导入list里的算法，螺旋矩阵能怎么bisect，毕竟这东西本质就是list的重排序，它没啥性质可言

搜索发现这个螺旋数组是 [4,5,6,7,0,1,2] 这种螺旋(shift..) 好奇怪的条件啊：
左右两段中，一定是有一段有序的，另一段可能有序可能无序(有序，则一定有段首值<段尾值)
需要 if nums[mid] >= nums[start] 判断左面是否有序
看的我都糊涂了，它是说 '//'状数组二分会产生 '/ _/'状无序右侧；算法是相当于只优化了“左侧”，对另一侧继续拆.. 这过度解读题意了。还不如直接拿拐点切分list，各自bisect()

螺旋数组 LC#54 不知为何大家用的都是Excel式四向法.. 虽然我写2048.js 时也是用了4向线性扫描了
括号匹配 LC#20 可以用调用栈，我又试了2h. bing反而误导我 😭
测试

pairs = {'(':')', '[':']', '{':'}'}
def eat(s,c0):
  for c in s:
      # 如果是左括号，就把它压入栈中
      if c in pairs: eat(s,pairs[c])
      elif c==c0:return # 如果是右括号，左括号便与之匹配
      else: assert'','多余项而栈空'
  assert c0=='eof','栈尚不为空'

#394 字串“编码” ，晕了，这标题为何如此民科啊！我还以为是词表替换

decodeString('hello,2[wo]rld')
'hello,woworld'

decodeString=(s)=>s.replace(/(\d+)\[(\w+)\]/,
  (m,n,s)=>s.repeat(+n) )

本意是让你用 char 去累积 \d+[ ，累积[]里的字符，然后在 ']' 的时候输出repeat的文本，但这就是文本解析而已..

如你们所见，解法越简洁，我敲键盘的时间越少、敲脑门的时间越多……

Stack Overflow

Python: how to implement binary search in Double Dimensional Array

For one dimensional array, I can implement it by the following way:

def binary_search(a, key, low=0, high=None):
if high is None:
high = len(a) - 1

while low <= high:
m...

74 viewsedited 03:37