花花酱 LeetCode 61. Rotate List

By zxi on October 28, 2020

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution: Find the prev of the new head

Step 1: Get the tail node T while counting the length of the list.
Step 2: k %= l, k can be greater than l, rotate k % l times has the same effect.
Step 3: Find the previous node P of the new head N by moving (l – k – 1) steps from head
Step 4: set P.next to null, T.next to head and return N

Time complexity: O(n) n is the length of the list
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* rotateRight(ListNode* head, int k) {

if (!head) return head;

int l = 1;

ListNode* tail = head;

while (tail->next) { tail = tail->next; ++l; }

k %= l;

if (k == 0) return head;

ListNode* prev = head;

while (--l > k) prev = prev->next;

ListNode* new_head = prev->next;

tail->next = head;

prev->next = nullptr;

return new_head;

}

};

Java

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

class Solution {

public ListNode rotateRight(ListNode head, int k) {

if (head == null) return null;

int l = 1;

ListNode tail = head;

while (tail.next != null) {

tail = tail.next;

++l;

}

k %= l;

if (k == 0) return head;

ListNode prev = head;

for (int i = 0; i < l - k - 1; ++i) {

prev = prev.next;

}

ListNode new_head = prev.next;

prev.next = null;

tail.next = head;

return new_head;

}

Python3

class Solution:

def rotateRight(self, head: ListNode, k: int) -> ListNode:

if not head: return head

tail = head

l = 1

while tail.next:

tail = tail.next

l += 1

k = k % l

if k == 0: return head

prev = head

for _ in range(l - k - 1): prev = prev.next

new_head = prev.next

tail.next = head

prev.next = None

return new_head

花花酱 LeetCode 48. Rotate Image

By zxi on October 2, 2019

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Solution: 2 Passes

First pass: mirror around diagonal
Second pass: mirror around y axis

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

const int n = matrix.size();

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

swap(matrix[i][j], matrix[j][i]);

for (int i = 0; i < n; ++i)

reverse(begin(matrix[i]), end(matrix[i]));

}

};

花花酱 LeetCode 396. Rotate Function

By zxi on March 16, 2018

Problem:

Given an array of integers A and let n to be its length.

Assume B_k to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 10⁵.

Example:

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

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution 1: Brute Force

Time complexity: O(n^2) TLE

Space complexity: O(1)

Solution 2: Math

F(K)          =               0A[K] + 1A[K+1] + 2A[K+2] + ... + (n-2)A[K-2] + (n-1)A[K-1]
F(K-1)        =     0A[K-1] + 1A[K] + 2A[K+1] + 3A[K+2] + ... + (n-1)A[K-2]
F(K) - F(K-1) = (n-1)A[K-1] - 1A[K] - 1A[K+1] - 1A[K+2] - ... -     1A[K-2]
              = (n-1)A[K-1] - (1A[K] + 1A[K+1] + ... + 1A[K-2] + 1A[K-1] - 1A[K-1])
              = nA[K-1] - sum(A)
compute F(0)
F(i)          = F(i-1) + nA[i-1] - sum(A)

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

const int n = A.size();

int sum = 0;

int f = 0;

for (int i = 0; i < n; ++i) {

sum += A[i];

f += i * A[i];

}

int ans = f;

for (int i = 0; i < n - 1; ++i) {

f = f + sum - n * A[n - i - 1];

ans = max(ans, f);

}

return ans;

}

};

花花酱 LeetCode 796. Rotate String

By zxi on March 10, 2018

题目大意：给你两个字符串A, B, 问能否通过旋转A得到B。

Problem:

https://leetcode.com/problems/rotate-string/description/

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1:

Input: A = 'abcde', B = 'cdeab'

Output: true

Example 2:

Input: A = 'abcde', B = 'abced'

Output: false

Note:

A and B will have length at most 100.

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

bool rotateString(string A, string B) {

if (A.length() != B.length()) return false;

for (int i = 1; i < A.length(); ++i)

if (check(A, B, i)) return true;

return false;

}

private:

bool check(const string& A, const string& B, int offset) {

for (int i = 0; i < A.length(); ++i)

if (A[(i + offset) % A.length()] != B[i])

return false;

return true;

}

};

Posts tagged as “rotate”

花花酱 LeetCode 61. Rotate List

Solution: Find the prev of the new head

C++

Java

Python3

花花酱 LeetCode 48. Rotate Image

Solution: 2 Passes

C++

花花酱 LeetCode 396. Rotate Function

Problem:

Solution 1: Brute Force

Solution 2: Math

花花酱 LeetCode 796. Rotate String