AK F.*ing leetcode 流浪计划之数组反转

LightningBilly · 2021 年2 月 5 日 07:15

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

数组反转是比较基础的模拟性操作。局部反转操作可以抽象出来模板。原理不难理解，实现也简单。主要是利用对撞双指针思想，不过还是有一些细节要注意。里面的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 反转字符串

题目链接力扣

题目大意

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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 反转链表

题目链接：力扣

题目大意

反转一个单链表。

示例:

输入: 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 反转字符串中的元音字母

题目链接：力扣

题目大意

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 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

题目链接：力扣

题目大意

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入：“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了。

反转字符串题目链接力扣
反转链表题目链接力扣
反转字符串中的元音字母题目链接力扣
反转字符串中的单词 III 题目链接力扣

AK leetcode

leetcode相关题目都在下面了，拿起武器挨个点名呗。

7. 整数反转题目链接力扣

92. 反转链表 II 题目链接力扣

206. 反转链表题目链接力扣

344. 反转字符串题目链接力扣

345. 反转字符串中的元音字母题目链接力扣

541. 反转字符串 II 题目链接力扣

557. 反转字符串中的单词 III 题目链接力扣

917. 仅仅反转字母题目链接力扣

1190. 反转每对括号间的子串题目链接力扣

剑指 Offer 24. 反转链表题目链接力扣

本期内容简单，主要注意代码细节的把握。没有大神进阶题目。

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

在这里插入图片描述

kingeasternsun · 2021 年2 月 6 日 01:37

557. 反转字符串中的单词 III

难度简单269

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入：“Let’s take LeetCode contest” 输出：“s’teL ekat edoCteeL tsetnoc”

提示：

在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

代码地址

go


func reverseWords(s string) string {

	in := []byte(s)
	start, end := 0, 0 //左开右闭
	for end <= len(in) {
		//遇到空格或边界
		if end == len(in) || in[end] == ' ' {
			reverse(in[start:end])
			end = end + 1
			start = end
		} else {
			end++
		}

	}

	return string(in)
}

func reverse(word []byte) {
	if len(word) <= 1 {
		return
	}
	for i, j := 0, len(word)-1; i < j; i, j = i+1, j-1 {
		word[i], word[j] = word[j], word[i]
	}
	return
}

rust

pub struct Solution;
impl Solution {
    pub fn reverse_words(s: String) -> String {
        let mut s = s.into_bytes();
        s.split_mut(|c|c == &(' ' as  u8)).for_each(| w|w.reverse());
        unsafe { String::from_utf8_unchecked(s) }

    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;

    #[test]
    fn it_works() {
        assert_eq!(Solution::reverse_words(String::from("Let's take LeetCode contest")),String::from("s'teL ekat edoCteeL tsetnoc"));
    }
}

kingeasternsun · 2021 年2 月 6 日 02:50

1528. 重新排列字符串

难度简单26

给你一个字符串 s 和一个 长度相同 的整数数组 indices 。

请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。

返回重新排列后的字符串。

原地替换法



func restoreString(s string, indices []int) string {
	in := []byte(s)

	for i := 0; i < len(in); i++ {

		//位置没变就不用动
		if indices[i] == i {
			continue
		}
		ch := in[i]
		nextID := indices[i]
		//如果下面的 for 循环用 indices[nextID] != nextID作为终止条件，这个就必须,不然就会出现重复处理的情况
		indices[i] = i
		for indices[nextID] != nextID { //判断条件就是 indices[nextID] != nextID
			//放入到 in的 nextIDn 位置上，并且把 in 在 nextIDn 位置上原来的value保存到ch
			in[nextID], ch = ch, in[nextID]
			// curID 赋给 indices[nextID] 标识已经更换过不用再动了，同时把 更新curID 为 indices[nextID]
			indices[nextID], nextID = nextID, indices[nextID]
		}

		//当前i的位置要用最新的ch来填充
		in[i] = ch
		indices[i] = i
	}

	return string(in)
}