Posts tagged as “swap”

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

By zxi on August 4, 2021

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Any two characters may be swapped, even if they are not adjacent.

Example 1:

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "111000" -> "101010"
The string is now alternating.

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = "1110"
Output: -1

Constraints:

1 <= s.length <= 1000
s[i] is either '0' or '1'.

Solution: Greedy

Two passes, make the string starts with ‘0’ or ‘1’, count how many 0/1 swaps needed. 0/1 swaps must equal otherwise it’s impossible to swap.

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

C++

// Author: Huahua

class Solution {

public:

int minSwaps(string s) {

auto count = [&](int m) {

vector<int> swaps(2);

for (int i = 0; i < s.length(); ++i, m ^= 1)

if (s[i] - '0' != m)

++swaps[s[i] - '0'];

return swaps[0] == swaps[1] ? swaps[0] : INT_MAX;

};

int ans = min(count(0), count(1));

return ans != INT_MAX ? ans : -1;

}

};

花花酱 LeetCode 1502. Can Make Arithmetic Progression From Sequence

By zxi on July 5, 2020

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

Solution 1: Sort and check.

Time complexity: O(nlog)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

sort(begin(arr), end(arr));

const int diff = arr[1] - arr[0];

for (int i = 2; i < arr.size(); ++i)

if (arr[i] - arr[i - 1] != diff) return false;

return true;

}

};

Java

// Author: Huahua

class Solution {

public boolean canMakeArithmeticProgression(int[] arr) {

Arrays.sort(arr);

int diff = arr[1] - arr[0];

for (int i = 2; i < arr.length; ++i)

if (arr[i] - arr[i - 1] != diff) return false;

return true;

}

python3

class Solution:

def canMakeArithmeticProgression(self, arr: List[int]) -> bool:

arr.sort()

diff = arr[1] - arr[0]

return all(i - j == diff for i, j in zip(arr[1:], arr[:-1]))

Solution 2: Rearrange the array

Find min / max / diff and put each element into its correct position by swapping elements in place.

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

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

const int n = arr.size();

const auto [loit, hiit] = minmax_element(cbegin(arr), cend(arr));

const auto [lo, hi] = pair{*loit, *hiit};

if ((hi - lo) % (n - 1)) return false;

const int diff = (hi - lo) / (n - 1);

if (diff == 0) return true;

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

if ((arr[i] - lo) % diff) return false;

const int idx = (arr[i] - lo) / diff;

if (idx != i) swap(arr[i--], arr[idx]);

}

return true;

}

};

花花酱 LeetCode 1187. Make Array Strictly Increasing

By zxi on September 7, 2019

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Solution: DP

Time complexity: O(mn)
Space complexity: O(mn) -> O(m + n)

C++

// Author: Huahua

class Solution {

public:

int makeArrayIncreasing(vector<int>& a, vector<int>& c) {

constexpr int kInf = 1e9;

int m = a.size();

// Sort b and make it only containing unique numbers.

sort(begin(c), end(c));

vector<int> b;

for (int i = 0; i < c.size(); ++i) {

if (!b.empty() && c[i] == b.back()) continue;

b.push_back(c[i]);

}

int n = b.size();

// min steps to make a[0~i] valid by keeping a[i]

vector<int> keep(m, kInf);

keep[0] = 0;

// swap[i][j] := min steps to make a[0~i] valid by a[i] = b[j]

vector<int> swap(n, 1);

for (int i = 1; i < m; ++i) {

int min_keep = kInf;

int min_swap = kInf;

vector<int> temp(n, kInf);

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

if (j > 0) min_swap = min(min_swap, swap[j - 1] + 1);

if (a[i] > b[j]) min_keep = min(min_keep, swap[j]);

if (a[i] > a[i - 1]) keep[i] = keep[i - 1];

if (b[j] > a[i - 1]) temp[j] = keep[i - 1] + 1;

temp[j] = min(temp[j], min_swap);

keep[i] = min(keep[i], min_keep);

}

temp.swap(swap);

}

int s = *min_element(begin(swap), end(swap));

int k = keep.back();

int ans = min(s, k);

return ans >= kInf ? -1 : ans;

}

};

花花酱 LeetCode 971. Flip Binary Tree To Match Preorder Traversal

By zxi on January 5, 2019

Given a binary tree with N nodes, each node has a different value from {1, ..., N}.

A node in this binary tree can be flipped by swapping the left child and the right child of that node.

Consider the sequence of N values reported by a preorder traversal starting from the root. Call such a sequence of N values the voyage of the tree.

(Recall that a preorder traversal of a node means we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child.)

Our goal is to flip the least number of nodes in the tree so that the voyage of the tree matches the voyagewe are given.

If we can do so, then return a list of the values of all nodes flipped. You may return the answer in any order.

If we cannot do so, then return the list [-1].

Example 1:

Input: root = [1,2], voyage = [2,1]
Output: [-1]

Example 2:

Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]

Example 3:

Input: root = [1,2,3], voyage = [1,2,3]
Output: []

Note:

1 <= N <= 100

Solution: Pre-order traversal

if root->val != v[pos] return [-1]
if root->left?->val != v[pos + 1], swap the nodes

c++

class Solution {

public:

vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {

vector<int> flips;

int pos = 0;

solve(root, voyage, pos, flips);

return flips;

}

private:

void solve(TreeNode* root, const vector<int>& voyage, int& pos, vector<int>& flips) {

if (!root) return;

if (root->val != voyage.at(pos)) {

flips.clear();

flips.push_back(-1);

return;

}

if (root->left && root->left->val != voyage.at(pos + 1)) {

swap(root->left, root->right);

flips.push_back(root->val);

}

++pos;

solve(root->left, voyage, pos, flips);

solve(root->right, voyage, pos, flips);

}

};

Python3

# Author: Huahua, 60 ms

class Solution:

def flipMatchVoyage(self, root, voyage):

self.pos = 0

self.flips = []

def solve(root):

if not root: return

if root.val != voyage[self.pos]:

self.flips = [-1]

return

if root.left and root.left.val != voyage[self.pos + 1]:

root.left, root.right = root.right, root.left

self.flips.append(root.val)

self.pos += 1

solve(root.left)

solve(root.right)

solve(root)

return self.flips

Posts tagged as “swap”

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

Solution: Greedy

C++

花花酱 LeetCode 1721. Swapping Nodes in a Linked List

Solution:

C++

花花酱 LeetCode 1502. Can Make Arithmetic Progression From Sequence

Solution 1: Sort and check.

C++

Java

python3

Solution 2: Rearrange the array

C++

花花酱 LeetCode 1187. Make Array Strictly Increasing

C++

花花酱 LeetCode 971. Flip Binary Tree To Match Preorder Traversal

Solution: Pre-order traversal

c++

Python3