Arrays Strings¶
Table of Contents¶
- 624. Maximum Distance in Arrays (Medium)
- 280. Wiggle Sort (Medium) 👑
- 1056. Confusing Number (Easy) 👑
- 1427. Perform String Shifts (Easy) 👑
- 161. One Edit Distance (Medium) 👑
- 186. Reverse Words in a String II (Medium) 👑
- 1055. Shortest Way to Form String (Medium) 👑
624. Maximum Distance in Arrays¶
from typing import List
# Array
def maxDistance(arrays: List[List[int]]) -> int:
mn, mx = float("inf"), float("-inf")
res = 0
for arr in arrays:
res = max(res, arr[-1] - mn, mx - arr[0])
mn = min(mn, arr[0])
mx = max(mx, arr[-1])
return res
arrays = [[1, 2, 3], [4, 5], [1, 2, 3]]
print(maxDistance(arrays)) # 4
280. Wiggle Sort 👑¶
from typing import List
def wiggleSort(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
for i in range(n - 1):
if i % 2 == 0:
if nums[i] > nums[i + 1]:
nums[i], nums[i + 1] = nums[i + 1], nums[i]
else:
if nums[i] < nums[i + 1]:
nums[i], nums[i + 1] = nums[i + 1], nums[i]
num = [3, 5, 2, 1, 6, 4]
wiggleSort(num)
print(num) # [3, 5, 1, 6, 2, 4]
#include <iostream>
#include <vector>
using namespace std;
void wiggleSort(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0) {
if (nums[i] > nums[i + 1]) swap(nums[i], nums[i + 1]);
} else {
if (nums[i] < nums[i + 1]) swap(nums[i], nums[i + 1]);
}
}
}
int main() {
vector<int> nums = {3, 5, 2, 1, 6, 4};
wiggleSort(nums);
// 3 5 1 6 2 4
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
1056. Confusing Number 👑¶
def confusingNumber(n: int) -> bool:
rotate_map = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}
original = str(n)
rotated = ""
for ch in reversed(original):
if ch not in rotate_map:
return False
rotated += rotate_map[ch]
return rotated != original
if __name__ == "__main__":
print(confusingNumber(6)) # True
print(confusingNumber(89)) # True
print(confusingNumber(11)) # False
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool confusingNumber(int n) {
static const unordered_map<char, char> rotationMap = {
{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
string numStr = to_string(n);
string rotated;
rotated.reserve(numStr.size());
for (int i = numStr.size() - 1; i >= 0; --i) {
char currentDigit = numStr[i];
auto it = rotationMap.find(currentDigit);
if (it == rotationMap.end()) {
return false;
}
rotated.push_back(it->second);
}
return rotated != numStr;
}
};
int main() {
Solution sol;
cout << boolalpha; // Print boolean values as true/false
cout << sol.confusingNumber(6) << endl; // true
cout << sol.confusingNumber(89) << endl; // true
cout << sol.confusingNumber(11) << endl; // false
cout << sol.confusingNumber(25) << endl; // false
cout << sol.confusingNumber(916) << endl; // true
cout << sol.confusingNumber(101) << endl; // false
return 0;
}
1427. Perform String Shifts 👑¶
"""
- Calculate the net shift direction and amount by combining all operations, then apply a single rotation to the string using slicing.
"""
from typing import List
def stringShift(s: str, shift: List[List[int]]) -> str:
total_shift = 0
for direction, amount in shift:
if direction == 0:
total_shift -= amount
else:
total_shift += amount
total_shift %= len(s)
if total_shift == 0:
return s
if total_shift > 0:
return s[-total_shift:] + s[:-total_shift]
else:
total_shift = abs(total_shift)
return s[total_shift:] + s[:total_shift]
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string stringShift(string s, vector<vector<int>>& shift) {
int total_shift = 0;
for (const auto& op : shift) {
if (op[0] == 0) {
total_shift -= op[1];
} else {
total_shift += op[1];
}
}
int n = s.length();
total_shift =
((total_shift % n) + n) % n; // Handle negative shift properly
if (total_shift == 0) {
return s;
}
return s.substr(n - total_shift) + s.substr(0, n - total_shift);
}
};
int main() {
Solution solution;
string s1 = "abc";
vector<vector<int>> shift1 = {{0, 1}, {1, 2}};
cout << "Input: s = \"abc\", shift = [[0,1],[1,2]]" << endl;
cout << "Output: " << solution.stringShift(s1, shift1) << endl;
string s2 = "abcdefg";
vector<vector<int>> shift2 = {{1, 1}, {1, 1}, {0, 2}, {1, 3}};
cout << "Input: s = \"abcdefg\", shift = [[1,1],[1,1],[0,2],[1,3]]" << endl;
cout << "Output: " << solution.stringShift(s2, shift2) << endl;
return 0;
}
161. One Edit Distance 👑¶
class IsOneEditDistance:
def traverse(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
# ensure s is the shorter one
if m > n:
return self.traverse(t, s)
# len difference > 1
if n - m > 1:
return False
for i in range(m):
if s[i] == t[i]:
continue
if m == n:
return s[i + 1 :] == t[i + 1 :]
else:
return s[i:] == t[i + 1 :]
return m + 1 == n
if __name__ == "__main__":
sol = IsOneEditDistance()
assert sol.traverse("ab", "acb") is True
assert sol.traverse("cab", "ad") is False
assert sol.traverse("1203", "1213") is True
186. Reverse Words in a String II 👑¶
from typing import List
class reverseWords:
def left_right_pointers(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
n = len(s)
s.reverse()
left = 0
while left < n:
if s[left] == " ":
left += 1
continue
# detect the word boundary
right = left
while right < n and s[right] != " ":
right += 1
# reverse the word
l, r = left, right - 1
while l < r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
left = right
if __name__ == "__main__":
sol = reverseWords()
s = ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s"]
sol.left_right_pointers(s)
assert s == ["i", "s", " ", "s", "k", "y", " ", "t", "h", "e"]