iT邦幫忙

8

[演算法][SQL]演算法挑戰系列(7)-Exchange Seats

  • 分享至 

  • xImage
  •  

HIHI!哈哈哈,其實每次打文章的時候,最難下手的就是開場了,要請大家原諒我這些詞窮XD,所以我決定今天就不拖台錢,直接進入正文...啊啊!對了,不然讓我再說個,先前我都是以MSSQL去解題,不過因為這次的題目只能以MySQL去提交答案,所以雖然看起來差不多,但我今天是使用MySQL哦!那接下來真的就正文了XD:

題目:Exchange Seats
難易度:中
題目內容:交換相鄰兩個學生的座位,如果最後一筆是奇數,該學生就不用和誰交換。
例如:
seat資料表

id student
1 Abbot
2 Doris
3 Emerson
4 Green
5 Jeames
換完位置後的結果:
id student
------------- -------------
1 Doris
2 Abbot
3 Green
4 Emerson
5 Jeames

我的想法是用子查詢來決定student的值,以下是解法:

/*(1) id不變,所以先直接SELECT*/
SELECT m.id ,
/*(2) 在子查詢中處理名字,配合IFNULL函數,
如果子查詢的名字是null那就回傳該id原本的學生*/
IFNULL(
/*(3) 先判斷id是單數還是雙數:用%取餘數,1是單數,2是雙數*/
(SELECT CASE m.id % 2 
 /*(4) 單數的話,就去用這次的id加上1去JOIN自己,取下一個id的學生名字*/
 WHEN 1 THEN (SELECT s.student FROM seat AS s WHERE s.id = m.id+1)
 /*(5) 雙數的話,就去用這次的id減1去JOIN自己,取上一個id的學生名字*/
 WHEN 0 THEN (SELECT s.student FROM seat AS s WHERE s.id = m.id-1) END)
,m.student) AS student
FROM seat AS m

這一題SQL意想不到居然會有統計成績,所以分享一下:
https://ithelp.ithome.com.tw/upload/images/20180615/20106935WowQdl8Qtv.jpg
另外我也看到另外不用子查詢的JOIN寫法:
原解答網址

/*(1)查詢欄位,
coalesce函數會回傳參數中第一個不為NULL的值,如果都是NULL會回傳NULL。
這裡用來控制student該不該交換,或維持原值*/
SELECT s1.id, coalesce(s2.student, s1.student) as student
FROM seat s1
/*(2)JOIN自己以取得對應的資料*/
LEFT JOIN seat s2
ON 
    /*(3)要取得的對應資料從這裡做控制,一樣用%來判斷單數雙數,
    如果是單數,就是取相減為1的資料,
    其實把算式移位一下就變成s1.id + 1 = s2.id,也就是下一筆資料。
    如果是雙數,就取被減後為1的資料,
    一樣把算式移位一下會變成s1.id - 1 = s2.id,也就是上一筆資料。*/
    (s1.id % 2 = 1 AND s2.id - s1.id = 1)
    OR 
    (s1.id % 2 = 0 AND s1.id - s2.id = 1)
/*最後依id做排序,其實我一開始也有放,
可是想說他預設都會以第一個欄位由小到大排序,最後就拿掉了。*/
ORDER BY s1.id

Okay,其實這一題算滿輕鬆解決的,以我解其他題目的速度來說算是快的了,一開始解題時都會陷入思考動手發現錯誤思考刪掉重做做其他事轉移注意力的無限循環XD,不過最近真的好很多了,我想每個禮拜這樣練習應該還是稍微能訓練到邏輯吧!哈哈!另一方面,我也一直在想這個系列可以開到多遠,不如就在最後幾篇的時候來個「全困難挑戰系列」吧!哈哈哈,還是很感謝大家這禮拜的觀看!如果文章中有任何問題,或是筆誤、能改進的地方都麻煩大大留言告訴我,我會盡快改修正的!謝謝大家/images/emoticon/emoticon41.gif


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
1
小魚
iT邦大師 1 級 ‧ 2018-06-15 21:35:34

又回到SQL了喔,先卡位。

神Q超人 iT邦研究生 5 級 ‧ 2018-06-15 21:45:54 檢舉

哈哈哈,對啊!想說這樣比較有新奇感XD
感謝秒捧場,期待大大的寫法/images/emoticon/emoticon37.gif

4
暐翰
iT邦大師 1 級 ‧ 2018-06-15 22:48:18

大大每周一挑戰又來了 /images/emoticon/emoticon12.gif

下面是我的解法
邏輯:
1.假如mod 0代表id要減1
2.假如mod 1代表id要加1
3.假如id是最大值的時候,要判斷mod是不是1,假如是不用修改id

set @maxid = (select max(id) maxid from seat);
select 
  case 
    when (T1.`id` % 2 = 0 ) then T1.`id` -1
    when ((T1.`id` % 2 = 0 ) and not (@maxid = T1.`id` ))  then T1.`id` +1
    else T1.`id`
  end `id`
  ,T1.`student`
from seat  T1
order by `id`;

LeetCode不能在前面宣告變數所以改成cross join

select 
  case 
    when (T1.`id` % 2 = 0 ) then T1.`id` -1
    when ((T1.`id` % 2 = 1) and not (@maxid = T1.`id` ))  then T1.`id` +1
    else T1.`id`
  end `id`
  ,T1.`student`
from seat  T1,(SELECT @maxid := (select max(id) maxid from seat)) T2
order by `id`

SQL Fiddle Demo 連結

神Q超人 iT邦研究生 5 級 ‧ 2018-06-16 20:24:02 檢舉

大大的解題方式很擅長宣告變數或是暫存的table呢!
如果用這種方式就不需要為了一個值在很多地方打相同的子查詢了!
以後我也來用看看/images/emoticon/emoticon37.gif

3
純真的人
iT邦大師 1 級 ‧ 2018-06-15 23:13:38

我先用MSSQL解題@@...

MySQL找時間~

declare @Tmp table(
	id int
	,name nvarchar(50)
)

insert into @Tmp
values(1,'Abbot')
,(2,'Doris')
,(3,'Emerson')
,(4,'Green')
,(5,'Jeames')

select *
from (
	select Row_Number()over(
		order by
		case when id % 2 = 0
		then id - 1
		else id + 1
		end
	) id
	,name
	from @Tmp
) as k
order by id

https://ithelp.ithome.com.tw/upload/images/20180615/20061369DVBJ7d3gaw.png

ok~~追求MySQL版@@~

這次直接用暐翰的語法來改XD

CREATE TABLE seat 
    (`id` int, `student` varchar(7))
;
    
INSERT INTO seat 
    (`id`, `student`)
VALUES
    (1, 'Abbot'),
    (2, 'Doris'),
    (3, 'Emerson'),
    (4, 'Green'),
    (5, 'Jeames')
;

set @i = 0;
select 
  @i := @i + 1 id
  ,T1.`student`
from seat  T1
order by (
  case 
  when (T1.`id` % 2 = 0 ) 
  then T1.`id` -1
  else T1.`id` +1
  end
);

http://sqlfiddle.com/#!9/23fdcf/53

看更多先前的回應...收起先前的回應...
暐翰 iT邦大師 1 級 ‧ 2018-06-15 23:34:16 檢舉

大大簡單明瞭/images/emoticon/emoticon12.gif
發現可以少一層子查詢,因為row_number已經幫忙排序

select Row_Number()over(
	order by
	case when id % 2 = 0
	then id - 1
	else id + 1
	end
) id
,name
from @Tmp

Test Link


PS.
小抱怨MySQL沒有Row_Number函數都只能模擬,超麻煩的 : (

哈~~我怕排序~會亂跳~

其實這有個陷阱~如果id是
1
3
5
7
9
以上方式就要用Row_Number()先排序過~再取餘數換位置@@...

暐翰 iT邦大師 1 級 ‧ 2018-06-16 13:07:48 檢舉

對,能這樣解
是因為ID照序號排下來

懷念的 Row_Number()
/images/emoticon/emoticon02.gif

暐翰
fysh711426

ok~我增加MySQL的寫法了XD

http://sqlfiddle.com/#!9/23fdcf/53

基本上要模擬Row_Number()只要把判斷把在Order by裡面~
前面多一個@i的累加~基本上是差不多的@@..

暐翰 iT邦大師 1 級 ‧ 2018-06-16 20:48:39 檢舉

這解法酷! 我沒想到

神Q超人 iT邦研究生 5 級 ‧ 2018-06-16 20:49:33 檢舉

ROW_NUMBER()來重新設定id的值,我完全沒想過耶/images/emoticon/emoticon32.gif
不愧是純真的人大大,只要是SQL果然難不倒XD
尤其是用ORDER BY來取代MYSQL沒有的ROW_NUMBER()真的把每個功能使用的很靈活!

神Q超人

其實我是專走VB系的@@..
不論是asp.net或者vb.net都是用vb語言開發的~

對C#語系不熟~但花時間來修改是沒有問題(可以對照)

基本上我慣用MSSQL沒有使用MySQL

一開始我是先使用暐翰的語法測試這樣行不行~

select 
   T1.`student`
from seat  T1
order by (
  case 
  when (T1.`id` % 2 = 0 ) 
  then T1.`id` -1
  else T1.`id` +1
  end
);

然後用MSSQL的Row_Number()概念去來套在MySQL

去Google找MySQL語法對於累加如何處理的方式~

才找到可以用@i := @i + 1來逐筆累加~

才變成這樣^^"

set @i = 0;
select 
  @i := @i + 1 id
  ,T1.`student`
from seat  T1
order by (
  case 
  when (T1.`id` % 2 = 0 ) 
  then T1.`id` -1
  else T1.`id` +1
  end
);

把判斷寫在 order by 好簡潔,這我也沒想到。 /images/emoticon/emoticon32.gif

神Q超人 iT邦研究生 5 級 ‧ 2018-06-17 13:54:41 檢舉

純真的人
我目前也都是用asp.net做開發,
不過我走的是C#路線的,雖然公司大部分的人都用VB/images/emoticon/emoticon16.gif
我的話沒辦法分那麼清楚,有時候要突然從C#轉成VB真的會搞混語法XD

所以那個寫法就是MySQL版的ROW_NUMBER()吧!
至少原理是一樣的XD,不過要在加上群組可能就又要再加入判斷之類的。

2
小碼農米爾
iT邦高手 1 級 ‧ 2018-06-16 10:07:40

這次寫的效能不是很好,每列都判斷 NULL 就慢了。 /images/emoticon/emoticon02.gif

SELECT CASE WHEN A.id%2=1 AND B.id IS NULL
            THEN A.id
            WHEN A.id%2=1
			THEN A.id+1
			ELSE A.id-1 END AS id,
	   A.student
FROM seat AS A
LEFT JOIN seat AS B ON B.id=A.id+1
ORDER BY id
神Q超人 iT邦研究生 5 級 ‧ 2018-06-16 20:52:16 檢舉

我發現樓上的所有大大都是在id上面處理!
是因為直接運算後再排序比較方便嗎XD
我看到題目的時候就直接把焦點都放在student
沒考慮過可以直接改變id!
以後我應該也要試著去發現不同的可能/images/emoticon/emoticon13.gif

哈哈哈,這應該是職業病吧,
看到奇偶數腦海中會不自覺地浮現 id % 2 = 1
所以很自然的從 id 開始下手,
當然您說的也是,直覺上會覺得改變 id 比較簡單。
/images/emoticon/emoticon37.gif

2
一級屠豬士
iT邦新手 2 級 ‧ 2018-06-17 01:16:41
create table ithelp180617 (
  id serial primary key
, student text not null  
);

insert into ithelp180617(student) values
('Abbot'), ('Doris'), ('Emerson'), ('Green'), ('James');

--
create or replace function change_seats (ids text[])
returns text[]
as $_$
declare
    rtn_arr text[] default '{}';
    arr_len integer;
    i integer;
    
begin
    arr_len := array_length(ids, 1);
    
    for i in 1..arr_len loop
        if (i % 2) = 0 then
            rtn_arr := array_append(rtn_arr, ids[i-1]);
        else
            rtn_arr := array_append(rtn_arr, ids[i+1]);
        end if;
    end loop;
    
    if rtn_arr[arr_len] is null then
        rtn_arr[arr_len] := ids[arr_len];
    end if;
    return rtn_arr;
end;
$_$ language plpgsql;

----

select unnest(change_seats(array_agg(student))) as "NewSeats"
  from ithelp180617;
  
 NewSeats 
----------
 Doris
 Abbot
 Green
 Emerson
 James
(5 筆資料列)

---------------
號碼不連號一樣能輕鬆處理

truncate table ithelp180617;

insert into ithelp180617(id, student) values
(99, 'Abbot'), (43, 'Doris'), (981, 'Emerson'), (567, 'Green'), (2, 'James');

select unnest(change_seats(array_agg(student))) as "NewSeats"
  from ithelp180617;

 NewSeats 
----------
 Doris
 Abbot
 Green
 Emerson
 James
(5 筆資料列)
神Q超人 iT邦研究生 5 級 ‧ 2018-06-17 13:37:09 檢舉

這是傳說中的PostgreSQL嗎!
他的處理方式有點像是T-SQL,
雖然有些地方不了解意思,但是應該是用迴圈來取目前讀到的行數來代替原本的id做是否要交換的判斷吧!

另外一種方式,不使用自定義函數.利用 generate_series(), array_agg(), 還有比較特殊的 unnest() WITH ordinality
來對應不連號的情境. WITH ordinality 會產生流水號.
供大家參考.

with t1(s) as (
select s
  from generate_series(1, (select count(*) from ithelp180617)) as g(s)
), t2(ordid) as (
select case 
            when (s % 2) = 0 then
               s - 1
            else
               s + 1
        end
  from t1
), t3 as (
select student, newid
  from (select array_agg(student) stdarr
                from ithelp180617) a
     , unnest(a.stdarr)           
  WITH ordinality b(student, newid)
), t4 as (
select t3.student
  from t2
  full outer join t3
    on t2.ordid = t3.newid
)
select student
  from t4
 where student is not null 
;    

 student 
---------
 Doris
 Abbot
 Green
 Emerson
 James
(5 筆資料列)
神Q超人 iT邦研究生 5 級 ‧ 2018-06-22 08:57:12 檢舉

這個我就有點吃力了XD
是先在t1generate_series幫他們補id號碼,
t2判斷id是奇數還偶數,偶數-1,奇數+1,做出ordld
t3應該是用流水號幫他們新編id,做出newold(這邊我非常不確定),
t4就是去比較ordoldnewold,如果一樣就換位置,
最後t5t4換位置的tableselect出來。

如果以上解釋有錯在麻煩大大了/images/emoticon/emoticon13.gif

我要留言

立即登入留言