[leetcode] rotation series (array, matrix, linked list, function, string)

【Leetcode】 The topics in the rotation series are summarized as follows ：

Rotation series problems

189. Rotation array

1. Title Description

leetcode link ：189. Rotation array

2. Thought analysis

according to k To rotate the array , The space complexity is required to be O(1), So you need to reverse the original array , So you can reverse the entire array first , Put the front k A reversal , Then put the back n-k A reversal .

It should be noted that ：k Greater than nums.length The situation of , Need to use k Yes nums.length modulus .

3. Reference code

class Solution {
    
    public void rotate(int[] nums, int k) {
    
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    public void reverse(int[] nums, int start, int end) {
    
        while (start < end) {
    
            int tmp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = tmp;
        }
    }
}

Interview questions 01.07. Rotation matrix

1. Title Description

leetcode link ： Interview questions 01.07. Rotation matrix

2. Thought analysis

3. Reference code

The finger of the sword Offer 24. Reverse a linked list

1. Title Description

leetcode link ： The finger of the sword Offer 24. Reverse a linked list

2. Thought analysis

Method 1 ： Iterative method （ Double pointer ）

Method 2 ： recursive

Use recursion to traverse the linked list , When the tail node is crossed, the recursion is terminated , Modify the of each node during backtracking next Reference point .

3. Reference code

Method 1 ： Iterative method （ Double pointer ）

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode dumpy = null;
        while (head != null) {
    
            ListNode tmp = head.next;
            head.next = dumpy;
            dumpy = head;
            head = tmp;
        }
        return dumpy;
    }
}

Method 2 ： recursive

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        if(head==null || head.next==null){
    
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

61. Rotate the list

1. Title Description

leetcode link ：61. Rotate the list

2. Thought analysis

3. Reference code

396. Rotation function

1. Title Description

leetcode link ：396. Rotation function

2. Thought analysis

3. Reference code

796. Rotate string

1. Title Description

leetcode link ：796. Rotate string

2. Thought analysis

3. Reference code