【LeetCode】旋转→数组☛矩阵☛链表☛函数☛字符串

水深无声 2022-11-19 14:58 91阅读 0赞

## 【LeetCode】旋转数组、矩阵、链表、函数、字符串 ##

### 文章目录 ###

*   *  【LeetCode】旋转数组、矩阵、链表、函数、字符串
     *   *  旋转数组★★
         *  旋转矩阵★★
         *  反转链表★
         *  旋转链表★★
         *  旋转函数★★
         *  旋转字符串★

--------------------

### 旋转数组★★ ###

[Leetcode189. 旋转数组][Leetcode189.]

【**题目**】给定一个数组，将数组中的元素向右移动 *k* 个位置，其中 *k* 是非负数

【**示例**】

输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]

【**解题思路**】原地算法

class Solution {
        
        public void rotate(int[] nums, int k) {
        
            k %= nums.length;
            reverse(nums, 0, nums.length - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length - 1);
        }
    
        private void reverse(int[] nums, int left, int right){
        
            while(left < right){
        
                int temp = nums[left];
                nums[left++] = nums[right];
                nums[right--] = temp; 
            }
        }
    }

--------------------

### 旋转矩阵★★ ###

[LeetCode面试题 01.07. 旋转矩阵][LeetCode_ 01.07.]

【**题目**】给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像

【**示例**】

给定 matrix = 
    [
      [1,2,3],
      [4,5,6],
      [7,8,9]
    ],
    原地旋转输入矩阵，使其变为:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]

【**解题思路**】

方法一：每次交换菱形四个顶点

class Solution {
        
        public void rotate(int[][] matrix) {
        
            int start = 0, end = matrix.length - 1;
            while(start < end) {
        
                for(int i = 0; i < end - start; i++) {
        
                    int t = matrix[start][start + i];
                    matrix[start][start + i] = matrix[end - i][start];
                    matrix[end - i][start] = matrix[end][end - i];
                    matrix[end][end - i] = matrix[start + i][end];
                    matrix[start + i][end] = t;
                }
                start++;
                end--;
            }
        }
    }

方法二：递归版

class Solution {
        
        public void rotate(int[][] matrix) {
        
            f(matrix, 0, matrix.length - 1, matrix.length - 1);
        }
        public void f(int[][] matrix, int start, int end, int n) {
        
            if(start >= end) {
        
                return;
            }
            for(int i = 0; i < n; i++) {
        
                int t = matrix[start][start + i];
                matrix[start][start + i] = matrix[end - i][start];
                matrix[end - i][start] = matrix[end][end - i];
                matrix[end][end - i] = matrix[start + i][end];
                matrix[start + i][end] = t;
            }
            f(matrix, start + 1, end - 1, n - 2);
        }
    }

方法三：先按主对角线反转，再按中轴线反转

class Solution {
        
        public void rotate(int[][] matrix) {
        
            int n = matrix.length;
            for(int i = 0; i < n; i++) {
        
                for(int j = i + 1; j < n; j++) {
        
                    int t = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = t;
                }
            }
            for(int i = 0; i < n; i++) {
        
                for(int j = 0; j < n / 2; j++) {
        
                    int t = matrix[i][j];
                    matrix[i][j] = matrix[i][n - j - 1];
                    matrix[i][n - j - 1] = t;
                }
            }
        }
    }

--------------------

### 反转链表★ ###

[Leetcode剑指 Offer 24. 反转链表][Leetcode_ Offer 24.]

【**题目**】定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点

【**示例**】

输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

【**解题思路**】遍历头插法

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            ListNode dummy = new ListNode(-1);
            ListNode p = null;
            while(head != null) {
        
                p = head;
                head = head.next;
                p.next = dummy.next;
                dummy.next = p;
            }
            return dummy.next;
        }
    }

--------------------

### 旋转链表★★ ###

[LeetCode61. 旋转链表][LeetCode61.]

【**题目**】给定一个链表，旋转链表，将链表每个节点向右移动 *k* 个位置，其中 *k* 是非负数

【**示例**】

示例1：
    输入: 1->2->3->4->5->NULL, k = 2
    输出: 4->5->1->2->3->NULL
    示例2：
    输入: 0->1->2->NULL, k = 4
    输出: 2->0->1->NULL

【**解题思路**】

*  求链表长度，对k取余
 *  找到分隔的位置
 *  连接

class Solution {
        
        public ListNode rotateRight(ListNode head, int k) {
        
            if(head == null || head.next == null) return head;
            int len = 0;
            ListNode p = head;
            while(p != null) {
        
                len++;
                p = p.next;
            }
            k %= len;
            if(k == 0) return head;
            k = len - k;
            p = head;
            while(k > 1) {
        
                p = p.next;
                k--;
            }
            ListNode newHead = p.next;
            p.next = null;
            p = newHead;
            while(p.next != null) {
        
                p = p.next;
            }
            p.next = head;
            return newHead;
        }
    }

--------------------

### 旋转函数★★ ###

[LeetCode396. 旋转函数][LeetCode396.]

【**题目**】给定一个长度为 *n* 的整数数组 `A` ，

假设 `Bk` 是数组 `A` 顺时针旋转 *k* 个位置后的数组，我们定义 `A` 的“旋转函数” `F` 为：

`F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]`。

计算`F(0), F(1), ..., F(n-1)`中的最大值。

**注意:**  
可以认为 *n* 的值小于 105

【**示例**】

A = [4, 3, 2, 6]
    F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
    F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
    F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
    F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
    所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26

【**解题思路**】

见递推公式

class Solution {
        
        public int maxRotateFunction(int[] A) {
        
            if(A == null || A.length == 0) return 0;
            int N = A.length;
            //递推公式 f[0] = f[0]
            //f[i] = f[i - 1] - sum(A) + A[i - 1] * N
            int[] f = new int[N];
            int sum = 0;
            for(int i = 0; i < N; i++) {
        
                sum += A[i];
                f[0] += i * A[i];
            }
    
            int res = f[0];
            for(int i = 1; i < N; i++) {
        
                f[i] = f[i - 1] - sum + A[i - 1] * N;
                res = Math.max(res, f[i]);
            }
            return res;
        }
    }

--------------------

### 旋转字符串★ ###

[LeetCode796. 旋转字符串][LeetCode796.]

【**题目**】给定两个字符串, A 和 B。

A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = ‘abcde’，在移动一次之后结果就是’bcdea’ 。如果在若干次旋转操作之后，A 能变成B，那么返回True

【**示例**】

示例 1:
    输入: A = 'abcde', B = 'cdeab'
    输出: true
    
    示例 2:
    输入: A = 'abcde', B = 'abced'
    输出: false

【**解题思路**】

方法一：暴力模拟法

class Solution {
        
        public boolean rotateString(String A, String B) {
        
            if(A.equals(B)) return true;
            if(A.equals("") || B.equals("") || A.length() != B.length()) return false;
            char begin = B.charAt(0);
            StringBuffer a = new StringBuffer(A);
            for(int i = 0; i < a.length(); i++){
        
                if(a.charAt(0) == begin){
        
                    if(a.toString().equals(B)) return true;
                }
                char c = a.charAt(0);
                a = a.delete(0, 1);
                a.append(c);
            }
            return false;
        }
    }

方法二：题目可以转化为`A+A中是否包含B`

public boolean rotateString(String A, String B) {
        
        return A.length() == B.length() && (A + A).matches("^[A-Za-z]*" + B + "[A-Za-z]*$");
    }

public boolean rotateString(String A, String B) {
        
        return A.length() == B.length() && (A + A).contains(B);
    }

[Leetcode189.]: https://leetcode-cn.com/problems/rotate-array/
[LeetCode_ 01.07.]: https://leetcode-cn.com/problems/rotate-matrix-lcci/
[Leetcode_ Offer 24.]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[LeetCode61.]: https://leetcode-cn.com/problems/rotate-list/
[LeetCode396.]: https://leetcode-cn.com/problems/rotate-function/
[LeetCode796.]: https://leetcode-cn.com/problems/rotate-string/