AK leetcode 流浪計劃 - 數組反轉

2021-03-02 彬彬魔坊

一、簡介二、基本操作步驟三、作用四、反轉模板交換元素的方法模板總結1 反轉數組區間2 反轉數組區間中的特定元素五、牛刀小試練習1 反轉字符串題目大意題目解析AC代碼練習2 反轉鍊表題目大意題目解析思路AC代碼練習3 反轉字符串中的元音字母題目大意題目解析AC代碼練習4 反轉字符串中的單詞 III題目大意題目解析AC代碼六、代碼模板七、總結八、實戰訓練代碼基礎訓練題AK leetcode

一、簡介

數組反轉是比較基礎的模擬性操作。局部反轉操作可以抽象出來模板。原理不難理解，實現也簡單。主要是利用對撞雙指針思想，不過還是有一些細節要注意。裡面的2數交換，以及查找需要交換的數據步驟，在很多題目中都有用到（如快速排序中查找交換數據）。需要通過練習達到熟練地步，不至於到用時卡在細節上。

為了避免眼高手低，所以總結出來供大家參與練習。

二、基本操作步驟

定義arr為目標數組，[i,j]為反轉的區間。

採用對撞雙指針法進行。

step 1判斷 i<j，如果成立直接結束算法

step 2 i一直增加，直到找到需要反轉的元素

step 3 j一直減少，直到找到需要反轉的元素

step 4 判斷i<j , 並執行交換，跳轉至step 1

step 5 結束

三、作用四、反轉模板

反轉模板主要包括2部分：尋找要交換的2個元素，然後交換元素。

交換元素的方法

交換原元素有2種方法：臨時變量法和異或法。前者適用於任何類型，後者只能適用於數字，字符等可以異或運算的類型。

// 臨時變量法
func swap(arr []int, i, j int) {
  temp := arr[i] // 保存arr[i]
  arr[i] = arr[j] // 上方保存誰的值就先改變誰的值，順序不能錯
  arr[j]=temp
}
// 異或法
func swap(arr []int, i, j int) {
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效，想想為什麼，臨時變量法就沒有這樣的麻煩
  if i==j {return} // 注意i==j時以下算法會失效
  
  arr[i] = arr[i]^arr[j] // 保存2者的異或
  arr[j] = arr[i]^arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
  arr[i] = arr[i]^arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 舉例說明
/*
arr[i]=1
arr[j]=2

arr[i] = 1^2
arr[j] = arr[i]^arr[j] = 1^2^2 = 1 // 此時arr[j]已經變成原來的arr[i]了
arr[i] = arr[i]^arr[j] = 1^2^1 = 2

*/
模板總結1 反轉數組區間
// 異或法
func swap(arr []type, i, j int) {
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效，想想為什麼，臨時變量法就沒有這樣的麻煩
  if i==j {return} // 注意i==j時以下算法會失效
  arr[i] = arr[i]^arr[j] // 保存2者的異或
  arr[j] = arr[i]^arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
  arr[i] = arr[i]^arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 反轉arr區間[i,j]
func reverse(arr []type, i, j int)  {
 for ;i<j; i, j = i+1, j-1 { // 每交換完一個都往裡移一個
   swap(arr, i, j)
  }
}
2 反轉數組區間中的特定元素
大致框架與上面的一致，不同的是需要判斷當前指針是否指到需要交換的元素，如果不是需要繼續移動。
func isNeedSwap(b type) bool {
 
}

// 異或法
func swap(arr []type, i, j int) {
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效，想想為什麼，臨時變量法就沒有這樣的麻煩
  if i==j {return} // 注意i==j時以下算法會失效
 arr[i] = arr[i] ^ arr[j] // 保存2者的異或
 arr[j] = arr[i] ^ arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
 arr[i] = arr[i] ^ arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 反轉arr區間[i,j]中的特定元素
func reverse(arr []type, i, j int) {
 for ; i < j; i, j = i+1, j-1 { // 每交換完一個都往裡移一個
  for ; i < j && !isNeedSwap(arr[i]); i++ { // 查找到第1個需要交換的元素
  }
  for ; i < j && !isNeedSwap(arr[j]); j-- { // 查找最後一個需要交換的元素
  }

  //if i < j {  // 這裡可以去除判斷，極端情況是 i==j 相當於沒有交換
   swap(arr, i, j)
  //}
 }
}

/*
可以看出前面的反轉數組是這個算法的特殊情況，
相當於isNeedSwap一直是true, 
所以裡面的for循環不起作用
*/
五、牛刀小試練習1 反轉字符串
題目連結 https://leetcode-cn.com/problems/reverse-string/
題目大意
編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。
不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。
你可以假設數組中的所有字符都是 ASCII 碼錶中的可列印字符。
示例 1：
輸入：["h","e","l","l","o"]輸出：["o","l","l","e","h"]示例 2：
輸入：["H","a","n","n","a","h"]輸出：["h","a","n","n","a","H"]
題目解析
沒有條件限制，只要調用模板1即可
func reverseString(s []byte)  {
    reverse(s, 0, len(s)-1)
}
AC代碼
// 異或法
func swap(arr []byte, i, j int) {
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效，想想為什麼，臨時變量法就沒有這樣的麻煩
  if i==j {return} // 注意i==j時以下算法會失效
  arr[i] = arr[i]^arr[j] // 保存2者的異或
  arr[j] = arr[i]^arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
  arr[i] = arr[i]^arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 反轉arr區間[i,j]
func reverse(arr []byte, i, j int)  {
 for ;i<j; i, j = i+1, j-1 {
        swap(arr, i, j)
    }
}

func reverseString(s []byte)  {
    reverse(s, 0, len(s)-1)
}
練習2 反轉鍊表
題目連結：https://leetcode-cn.com/problems/reverse-linked-list/
題目大意
反轉一個單鍊表。
示例:
輸入: 1->2->3->4->5->NULL輸出: 5->4->3->2->1->NULL進階:你可以迭代或遞歸地反轉鍊表。你能否用兩種方法解決這道題？
題目解析
解決這個問題的方法有很多，比如尾插法、遞歸法、數組反轉法。這裡我們就演示一下數組反轉法的應用。
思路
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
  arr := []int{}
  // 遍歷 head 並往arr中添加
  
  // 調用反轉數組方法(模板1)
  
  // 遍歷arr 依次更新到head鍊表中
}
AC代碼
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 異或法
func swap(arr []int, i, j int) {
 // 注意i==j時以下算法會失效
 // 注意i==j時以下算法會失效
 // 注意i==j時以下算法會失效，想想為什麼，臨時變量法就沒有這樣的麻煩
 if i == j {
  return
 } // 注意i==j時以下算法會失效
 arr[i] = arr[i] ^ arr[j] // 保存2者的異或
 arr[j] = arr[i] ^ arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
 arr[i] = arr[i] ^ arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 反轉arr區間[i,j]
func reverse(arr []int, i, j int) {
 for ; i < j; i, j = i+1, j-1 { // 每交換完一個都往裡移一個
  swap(arr, i, j)
 }
}


func reverseList(head *ListNode) *ListNode {
 arr := []int{}
 // 遍歷 head 並往arr中添加
 for temp := head; temp != nil; temp = temp.Next {
  // 注意：這裡temp一定要重新定義一個，後續head還有用
  arr = append(arr, temp.Val)
 }
 // 調用反轉數組方法(模板1)
 reverse(arr, 0, len(arr)-1)

 // 遍歷arr 依次更新到head鍊表中
 for temp, i := head, 0; i < len(arr); i, temp = i+1, temp.Next {
  // 注意：這裡temp一定要重新定義一個，後續head還有用
  temp.Val = arr[i]
 }

 return head
}

/*
[1,2,3,4,5]
[]
[1]
*/
練習3 反轉字符串中的元音字母
題目連結：https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
題目大意
編寫一個函數，以字符串作為輸入，反轉該字符串中的元音字母。
示例 1：
輸入："hello"輸出："holle"示例 2：
輸入："leetcode"輸出："leotcede"
提示：
元音字母不包含字母 "y" 。
題目解析
題目要求交換特定的字母，需要用到模板2.
元音字母有 aeiouAEIOU , 注意大寫字母也算的。
AC代碼
func isNeedSwap(b uint8) bool {
 lettersMap := map[uint8]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true, 'A': true, 'E': true, 'I': true, 'O': true, 'U': true}
 return lettersMap[b]
}

// 異或法
func swap(arr []uint8, i, j int) {
 if i==j {return}
 arr[i] = arr[i] ^ arr[j] // 保存2者的異或
 arr[j] = arr[i] ^ arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
 arr[i] = arr[i] ^ arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 反轉arr區間[i,j]中的特定元素
func reverse(arr []uint8, i, j int) {
 for ; i < j; i, j = i+1, j-1 { // 每交換完一個都往裡移一個
  for ; i < j && !isNeedSwap(arr[i]); i++ {
  }
  for ; i < j && !isNeedSwap(arr[j]); j-- {
  }

  swap(arr, i, j)
 }
}

func reverseVowels(s string) string {
 ans := []byte(s)
 reverse(ans, 0, len(s)-1)
 return string(ans)
}
練習4 反轉字符串中的單詞 III
題目連結：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
題目大意
給定一個字符串，你需要反轉字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。
示例：
輸入："Let's take LeetCode contest"輸出："s'teL ekat edoCteeL tsetnoc"
提示：
在字符串中，每個單詞由單個空格分隔，並且字符串中不會有任何額外的空格。
題目解析
題目的關鍵是如何查找單詞。
題目提示單詞之間只有一個空格，那我們就可以設置2個指針，一個指向前一個空格，然後再找一個空格。反轉空格之間的字符。再繼續向下查找空格。
AC代碼
// 異或法
func swap(arr []uint8, i, j int) {
 if i==j {return}
 arr[i] = arr[i] ^ arr[j] // 保存2者的異或
 arr[j] = arr[i] ^ arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
 arr[i] = arr[i] ^ arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 反轉arr區間[i,j]中的特定元素
func reverse(arr []uint8, i, j int) {
 for ; i < j; i, j = i+1, j-1 { // 每交換完一個都往裡移一個
  swap(arr, i, j)
 }
}

func reverseWords(s string) string {
 ans := []byte(s)

 for i,j:=-1, 0;j<=len(ans);j++ {
  if j==len(ans) || ans[j]==' ' { // 遇到空格或者結尾
   reverse(ans, i+1, j-1)
   i=j
  }
 }
 return string(ans)
}
六、代碼模板
func isNeedSwap(b type) bool {
 
}

// 異或法
func swap(arr []type, i, j int) {
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效
  // 注意i==j時以下算法會失效，想想為什麼，臨時變量法就沒有這樣的麻煩
  if i==j {return} // 注意i==j時以下算法會失效
 arr[i] = arr[i] ^ arr[j] // 保存2者的異或
 arr[j] = arr[i] ^ arr[j] // 將arr[j] 變成 原來arr[i]的值，arr[i]^arr[j]^arr[j] = arr[i],
 arr[i] = arr[i] ^ arr[j] // 現在arr[j]是原來的arr[i]，故arr[i]^arr[j]^arr[i] = arr[j]
}

// 反轉arr區間[i,j]
func reverseCommon(arr []type, i, j int)  {
 for ;i<j; i, j = i+1, j-1 { // 每交換完一個都往裡移一個
   swap(arr, i, j)
  }
}

// 反轉arr區間[i,j]中的特定元素
func reverseSpecial(arr []type, i, j int) {
 for ; i < j; i, j = i+1, j-1 { // 每交換完一個都往裡移一個
  for ; i < j && !isNeedSwap(arr[i]); i++ { // 查找到第1個需要交換的元素
  }
  for ; i < j && !isNeedSwap(arr[j]); j-- { // 查找最後一個需要交換的元素
  }

  //if i < j {  // 這裡可以去除判斷，極端情況是 i==j 相當於沒有交換
   swap(arr, i, j)
  //}
 }
}

/*
可以看出前面的反轉數組reverseCommon是這個算法的特殊情況，
相當於isNeedSwap一直是true, 
所以裡面的for循環不起作用
*/
七、總結
主要內容：
其中交換數據與查找特殊元素雖然簡單，但是細節多，現場思考容易出錯。平時多理解，總結好代碼在用到時可脫手而出。最好自己先完整寫幾題，感覺很熟練了，閉眼代碼框架就有了。可以直接調用模板。
筆者水平有限，有寫得不對或者解釋不清楚的地方還望大家指出，我會儘自己最大努力去完善。
下面我精心準備了leetcode幾個題目（首先AK F.*ing leetcode），給大家準備了一些題目，供大家練習參考。幹他F.*ing (Fighting?)。
八、實戰訓練代碼基礎訓練題
光說不練假把式，學完了怎麼也要實操一下吧，快快動用把剛才那4題A了。
反轉字符串 題目連結  https://leetcode-cn.com/problems/reverse-string/反轉鍊表 題目連結  https://leetcode-cn.com/problems/reverse-linked-list/反轉字符串中的元音字母 題目連結 https://leetcode-cn.com/problems/reverse-vowels-of-a-string/反轉字符串中的單詞 III 題目連結 https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/AK leetcode
leetcode相關題目都在下面了，拿起武器挨個點名唄。
7. 整數反轉 題目連結 https://leetcode-cn.com/problems/reverse-integer/
92. 反轉鍊表 II  題目連結 https://leetcode-cn.com/problems/reverse-linked-list-ii/
206. 反轉鍊表 題目連結  https://leetcode-cn.com/problems/reverse-linked-list/
344. 反轉字符串  題目連結  https://leetcode-cn.com/problems/reverse-string/
345. 反轉字符串中的元音字母  題目連結 https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
541. 反轉字符串 II  題目連結 https://leetcode-cn.com/problems/reverse-string-ii/
557. 反轉字符串中的單詞 III  題目連結 https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
917. 僅僅反轉字母  題目連結 https://leetcode-cn.com/problems/reverse-only-letters/
1190. 反轉每對括號間的子串   題目連結 https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/
劍指 Offer 24. 反轉鍊表  題目連結  https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
本期內容簡單，主要注意代碼細節的把握。沒有大神進階題目。
本人碼農，希望通過自己的分享，讓大家更容易學懂計算機知識。

相關焦點

  • AK leetcode 流浪計劃 - 回文串
    可以參考數組反轉普通情況func isPalindrome(s string) bool { for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { // 每判斷完一個都往裡移一個  if s[i] !
  • 整數反轉 | Leetcode題解
    題目描述:給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉請根據這個假設，如果反轉後整數溢出那麼就返回 0。難度：支持語言：JavaScript、Java、Python相關標籤相關企業思路 1:使用字符串在反轉並不是最好的選擇，因為還需要處理負號和0的情況，用數字運算方式反轉比較適合。
  • [LeetCode] 912. Sort an Array 數組排序
    題目給定了每個數字的範圍是 [-50000, 50000]，並不是特別大，這裡可以使用記數排序 Count Sort，在 LeetCode 中也有直接利用這個解法的題Sort Colors，建立一個大小為 100001 的數組 count，然後統計 nums 中每個數字出現的個數，然後再從0遍歷到 100000，對於每個遍歷到的數字i，若個數不為0，則加入 count 數組中對應個數的 i-50000
  • LeetCode刷題第三周【數組(簡單)】
    參考資料[1]Leetcode網站: https://leetcode-cn.com/[2]以上文字描述均來自 LeetCode數組模塊: https://leetcode-cn.com/tag/array/[3]刷題請點擊或見附錄：1539.
  • 初級樹狀數組 leetcode 練習題
    二、區域和檢索 - 數組可修改題意：給一個數組，有兩個操作。 1）求區間[l,r]的和。2）修改下標 i 的值為v。思路：題意是單點更新，求區間和。赤裸裸的樹狀數組模板題，直接套用即可。代碼：https://github.com/tiankonguse/leetcode-solutions/blob/master/problemset-new/003/00307-range-sum-query-mutable/range-sum-query-mutable.cc三、計算右側小於當前元素的個數題意：給一個數組，求每個位置右側比自己小的元素個數
  • leetcode:對撞指針系列
    leetcode-167:描述：給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等於目標數。
  • LeetCode
    一維數組的動態和連結：https://leetcode-cn.com/problems/running-sum-of-1d-array/給你一個數組 nums 。擁有最多糖果的孩子連結：https://leetcode-cn.com/problems/kids-with-the-greatest-number-of-candies/給你一個數組 candies 和一個整數 extraCandies ，其中 candies[i] 代表第 i 個孩子擁有的糖果數目對每一個孩子，檢查是否存在一種方案
  • LeetCode-7. Reverse Integer | 整數反轉
    Input: x = -123Output: -321Example 3:Input: x = 120Output: 21Example 4:Input: x = 0Output: 0Constraints:-231 <= x <= 231 - 1題解通過題目可以看出來，這道題是讓我們翻轉一個整數，比如123，個位是1十位是2百位是3，反轉後個位是
  • 【LeetCode】數組--旋轉數組(189)
    寫在前面關注較早的讀者可能知道現階段的LeetCode刷題將按照某一個特定的專題進行，之前的【貪心算法】已經結束，雖然只有三個題卻包含了簡單，中等，困難這三個維度，今天介紹的是第二個專題【數組
  • 笨方法刷 leetcode(一)
    最近在看leetcode，並且正在上面刷一些簡單級別的題目（不過說真的，這些題真的簡單嗎？？nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，並返回他們的數組下標。
  • 每天學一道leetcode:103. 二叉樹的鋸齒形層次遍歷
    前言歡迎閱讀小王同學的長篇連載文章之《每天學一道leetcode》。如果您從前做過這道題目，可以從小王同學的文章裡增強對該題目的記憶和印象，思考一下小王同學給出的思路和解法有沒有優化的空間。題目分析103題是leetcode中一道中等難度的題目，這道題目是二叉樹的層次遍歷的變形題。小王同學曾經分析過二叉樹的層次遍歷這道題目，地址在
  • [LeetCode] 918. Maximum Sum Circular Subarray 環形子數組的最大和
    假如沒有環形數組這一個條件，其實就跟之前那道 Maximum Subarray 一樣，解法比較直接易懂。這裡加上了環形數組的條件，難度就增加了一些，需要用到一些 trick。既然是子數組，則意味著必須是相連的數字，而由於環形數組的存在，說明可以首尾相連，這樣的話，最長子數組的範圍可以有兩種情況，一種是正常的，數組中的某一段子數組，另一種是分為兩段的，即首尾相連的，可以參見 大神 lee215 的帖子 中的示意圖。
  • ​LeetCode刷題實戰152:乘積最大子數組
    今天和大家聊的問題叫做 乘積最大子數組，我們先來看題面：https://leetcode-cn.com/problems/maximum-product-subarray/Given an integer array nums, find the contiguous subarray within an array (containing
  • 每日一道 LeetCode (2):整數反轉
    題目：整數反轉題目來源：https://leetcode-cn.com/problems/reverse-integer
  • Leetcode | 344. 反轉字符串
    (unsplash)題目編寫一個函數，其作用是將輸入的字符串反轉過來不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。你可以假設數組中的所有字符都是 ASCII 碼錶中的可列印字符。
  • LeetCode Weekly Contest 204 題解
    /blob/master/LeetCode/leetcode_detect-pattern-of-length-m-repeated-k-or-more-times.cpp題解：模擬或者是單純的數組題。
  • LeetCode-4.尋找兩個正序數組的中位數(Median of Two Sorted Arrays)
    尋找兩個正序數組的中位數給定兩個大小為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出這兩個正序數組的中位數，並且要求算法的時間複雜度為 O(log(m + n))。你可以假設 nums1 和 nums2 不會同時為空。
  • 【leetcode】 345. Reverse Vowels of a String && 1. Two Sum
    反轉字符串中的元音字母Write a function that takes a string as input and reverse only the vowels of a string.編寫一個函數，以字符串作為輸入，反轉該字符串中的元音字母。
  • 每天學一道leetcode:152.乘積最大子序列
    這道題同樣給了我們一個數組，讓我們在這個數組中尋找一個子數組，使得子數組內的元素的乘積最大。leetcode152題的題目描述從題目中給出的樣例可以知道，我們需要留意數組元素為負的情況，這個細節如果處理得不好，可能會對我們求解造成一些問題。
  • ​LeetCode刷題實戰34:在排序數組中查找元素的第一個和最後一個位置
    今天和大家聊的問題叫做在排序數組中查找元素的第一個和最後一個位置，我們先來看題面：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-arrayGiven an array of integers nums sorted