趣味SQL: 力扣91. 解码方法

〇〇

加上实体化子查询的提示看看

〇〇

你的在duckdb也是0.6秒
D with recursive t(s,pos,s1) as (
> 475237961189389388191145248534732735845769521294614894148884461898335373734122464165638621'
> union all
> select t.s||chr(substr(s1,t.pos,n)::int+64)
>       ,t.pos+n,s1
>   from t
>       ,(values(1),(2))j(n)
> where pos+n<=length(s1)+1
>        and (n=1 and substr(s1,t.pos,1)>'0'
>             or n=2 and t.pos<=length(s1)-1 and substr(s1,t.pos,2) between '10' and '26'
>             )
> )
> select count(*) from t where t.pos=length(s1)+1;
┌──────────────┐
│ count_star() │
│    int64     │
├──────────────┤
│        34560 │
└──────────────┘
Run Time (s): real 0.586 user 0.992756 sys 0.071994

〇〇

newkid 发表于 2024-9-5 23:07
我自己写了这个，答案只有你的一半？而且花了二十几秒，你半秒钟就能出答案？VAR S VARCHAR2(100);exec :s: ...

t.s||chr(to_number(substr(:s,t.pos,n))+64)并没有用

newkid

〇〇 发表于 2024-9-6 12:43
t.s||chr(to_number(substr(:s,t.pos,n))+64)并没有用

修改了一下，又简化了一下，还是要超过半分钟，ORACLE这一局输惨了。


with
n as (select /*+ materialize */ 1 n from dual union all select 2 from dual)
,t(pos) as (
select 1 from dual
union all
select t.pos+n
  from t
      ,n
where pos+n<=length(:s)+1
       and to_number(substr(:s,t.pos,n)) between 1 and 26
)
select count(*) from t where t.pos=length(:s)+1;

  COUNT(*)
----------
     34560

Elapsed: 00:00:38.86


你贴个PG或者鸭子的执行计划?

〇〇

duckdb计划是个图形不好贴，pg的
-------------------------------------------------------------------------------------------------------------------------------
Aggregate  (cost=7.28..7.29 rows=1 width=8) (actual time=2625.088..2625.097 rows=1 loops=1)
   CTE b
     ->  Append  (cost=0.00..0.03 rows=2 width=4) (actual time=0.007..0.013 rows=2 loops=1)
           ->  Result  (cost=0.00..0.01 rows=1 width=4) (actual time=0.004..0.005 rows=1 loops=1)
           ->  Result  (cost=0.00..0.01 rows=1 width=4) (actual time=0.001..0.002 rows=1 loops=1)
   CTE a
     ->  Recursive Union  (cost=0.00..7.00 rows=11 width=100) (actual time=0.046..1987.013 rows=233076 loops=1)
           ->  CTE Scan on b  (cost=0.00..0.10 rows=1 width=100) (actual time=0.043..0.053 rows=1 loops=1)
                 Filter: (((x = 1) AND (substr('475237961189389388191145248534732735845769521294614894148884461898335373734122464165638621'::text, 1, x
) >= '1'::text) AND (substr('475237961189389388191145248534732735845769521294614894148884461898335373734122464165638621'::text, 1, x) <= '9'::text)) OR
((x = 2) AND (substr('475237961189389388191145248534732735845769521294614894148884461898335373734122464165638621'::text, 1, x) >= '10'::text) AND (sub
str('475237961189389388191145248534732735845769521294614894148884461898335373734122464165638621'::text, 1, x) <= '26'::text)))
                 Rows Removed by Filter: 1
           ->  Nested Loop  (cost=0.00..0.67 rows=1 width=100) (actual time=0.016..18.347 rows=2590 loops=90)
                 Join Filter: ((length(a_1.r) >= b_1.x) AND (((b_1.x = 1) AND (substr(a_1.r, 1, b_1.x) >= '1'::text) AND (substr(a_1.r, 1, b_1.x) <= '9
'::text)) OR ((b_1.x = 2) AND (substr(a_1.r, 1, b_1.x) >= '10'::text) AND (substr(a_1.r, 1, b_1.x) <= '26'::text))))
                 Rows Removed by Join Filter: 2590
                 ->  CTE Scan on b b_1  (cost=0.00..0.05 rows=1 width=4) (actual time=0.002..0.004 rows=2 loops=90)
                       Filter: ((x = 1) OR (x = 2))
                 ->  WorkTable Scan on a a_1  (cost=0.00..0.20 rows=10 width=68) (actual time=0.003..1.539 rows=2590 loops=180)
   ->  CTE Scan on a  (cost=0.00..0.25 rows=1 width=0) (actual time=1126.816..2614.145 rows=34560 loops=1)
         Filter: (r = ''::text)
         Rows Removed by Filter: 198516
Planning Time: 7.053 ms
Execution Time: 2648.193 ms
(21 rows)

newkid

回溯法, 半秒可以跑出来：

declare
   type tn is table of number index by pls_integer;
   v_len tn;
   v_pt number;
   v_cnt number :=0;
   v_pos number;
   v_max number :=length(:s);
begin
    v_pos :=1;
    v_pt :=1;
    v_len(v_pt):=0;
   while v_pt>0 loop
       v_pos := v_pos - v_len(v_pt);
      
       if v_len(v_pt)=2 then
          v_pt := v_pt-1;
       else
          v_len(v_pt):=v_len(v_pt)+1;
          if v_pos + v_len(v_pt)<=v_max+1 and to_number(substr(:s,v_pos,v_len(v_pt))) between 1 and 26 then
             if v_pos + v_len(v_pt)<=v_max then
                v_pos := v_pos + v_len(v_pt);
                v_pt := v_pt+1;
                v_len(v_pt):=0;
             else
                v_cnt := v_cnt+1;
                v_pt := v_pt-1;
             end if;
          else
             v_pt := v_pt-1;
          end if;
       end if;
   end loop;
   dbms_output.put_line('count='||v_cnt);
end;
/

count=34560

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.44

太久没写这种代码了，脑子都生锈了，调试了半天才跑对。

〇〇

sqlite跑你最新版本的sql也是半秒
sqlite> with recursive
   ...> n as (select /*+ materialize */ 1 n union all select 2)
   ...> ,t(pos,s) as (
(x1...> select 1 ,'475237961189389388191145248534732735845769521294614894148884461898335373734122464165638621'
(x1...> union all
(x1...> select t.pos+n,s
(x1...>   from t
(x1...>       ,n
(x1...> where pos+n<=length(s)+1
(x1...>        and cast(substr(s,t.pos,n) as int) between 1 and 26
(x1...> )
   ...> select count(*) from t where t.pos=length(s)+1;
34560
Run Time: real 0.485 user 0.470492 sys 0.008311

〇〇

改写了别人  https://github.com/halfrost/LeetCode-Go/blob/master/leetcode/0091.Decode-Ways/91.%20Decode%20Ways.go  的答案，很快
with recursive
t(pos,s,dp,dp0) as (
select 1 ,'475237961189389388191145248534732735845769521294614894148884461898335373734122464165638621',1,0
union all
select t.pos+1,s
,case when substr(s,t.pos,1)<>'0' then dp else 0 end + case when pos >1 and substr(s,t.pos-1,1)<>'0' and cast(substr(s,t.pos-1,2) as int) between 1 and 26 then dp0 else 0 end,dp
from t
where pos<=length(s)+1
)
select pos,dp,dp0 from t
where t.pos=length(s)+1;
91|34560|17280
Run Time: real 0.001 user 0.000733 sys 0.000000

newkid

我自己想了这个，既然只要计数，从后面往前找就快多了：

with t(pos,cnt,cnt2) as (
select length(:s),1,1 from dual
union all
select t.pos-1
      ,CASE WHEN substr(:s,t.pos-1,1)<>'0' THEN t.cnt ELSE 0 END
        +case when substr(:s,t.pos-1,2) between '10' and '26' then t.cnt2 else 0 end
      ,t.cnt
  from t
where t.pos>1  
)
select cnt from t where pos=1;

       CNT
----------
     34560

Elapsed: 00:00:00.02

newkid

回溯法写成递归PL/SQL函数，代码简化很多，但效率还是不如从后往前找：
declare
   function f_cnt(p_pos in number) return number as
   begin
      if p_pos = length(:s)+1 then
         return 1;
      end if;
      if  substr(:s,p_pos,1)='0' then
          RETURN 0;
      end if;
      if p_pos = length(:s) then
         return 1;
      end if;
      if substr(:s,p_pos,2) between '10' and '26' then
         return f_cnt(p_pos+1)+f_cnt(p_pos+2);
      else
         return f_cnt(p_pos+1);
      end if;
   end;
begin
   dbms_output.put_line('count='||f_cnt(1));
end;
/


count=34560

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.55