Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Weekly Contest 279 LeetCode Solution
Problem 1 – Sort Even and Odd Indices Independently Leetcode Solution
You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:
- Sort the values at odd indices of
numsin non-increasing order.- For example, if
nums = [4,1,2,3]before this step, it becomes[4,3,2,1]after. The values at odd indices1and3are sorted in non-increasing order.
- For example, if
- Sort the values at even indices of
numsin non-decreasing order.- For example, if
nums = [4,1,2,3]before this step, it becomes[2,1,4,3]after. The values at even indices0and2are sorted in non-decreasing order.
- For example, if
Return the array formed after rearranging the values of nums.
Example 1:
Input: nums = [4,1,2,3]
Output: [2,3,4,1]
Explanation:
First, we sort the values present at odd indices (1 and 3) in non-increasing order.
So, nums changes from [4,1,2,3] to [4,3,2,1].
Next, we sort the values present at even indices (0 and 2) in non-decreasing order.
So, nums changes from [4,1,2,3] to [2,3,4,1].
Thus, the array formed after rearranging the values is [2,3,4,1].
Example 2:
Input: nums = [2,1]
Output: [2,1]
Explanation:
Since there is exactly one odd index and one even index, no rearrangement of values takes place.
The resultant array formed is [2,1], which is the same as the initial array.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Sort Even and Odd Indices Independently Leetcode Solution in Python
def sortEvenOdd(self, A):
A[::2], A[1::2] = sorted(A[::2]), sorted(A[1::2])[::-1]
return A
Sort Even and Odd Indices Independently Leetcode Solution in Java
Counting Sort:
class Solution {
public int[] sortEvenOdd(int[] nums) {
int[] even = new int[101];
int[] odd = new int[101];
int length = nums.length;
for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
even[nums[i]]++;
} else {
odd[nums[i]]++;
}
}
int e = 0;
int o = 100;
for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
// check even
while (even[e] == 0) {
++e;
}
nums[i] = e;
even[e]--;
} else {
while(odd[o] == 0) {
--o;
}
nums[i] = o;
odd[o]--;
}
}
return nums;
}
}
Heap:
class Solution {
public int[] sortEvenOdd(int[] nums) {
PriorityQueue<Integer> even = new PriorityQueue<>((a, b)->(a - b));
PriorityQueue<Integer> odd = new PriorityQueue<>((a, b)->(b - a));
int length = nums.length;
for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
even.add(nums[i]);
} else {
odd.add(nums[i]);
}
}
for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
nums[i] = even.poll();
} else {
nums[i] = odd.poll();
}
}
return nums;
}
}
Sort Even and Odd Indices Independently Leetcode Solution in C++
class Solution {
public:
vector<int> sortEvenOdd(vector<int>& nums) {
int n = nums.size();
priority_queue<int> maxheap;
priority_queue <int, vector<int>, greater<int> > minheap;
// even fill (0,2,4,6....)
for(int i=0; i<n;){
minheap.push(nums[i]);
i = i+2;
}
// odd fill (1,3,5,7,....)
for(int i=1; i<n;){
maxheap.push(nums[i]);
i = i+2;
}
//
// nums.clear();
int i = 0;
while(i<n){
if(i%2==0){
nums[i] = minheap.top();
minheap.pop();
}
else{
nums[i] = maxheap.top();
maxheap.pop();
}
i++;
}
return nums;
}
};
Problem 2 – Smallest Value of the Rearranged Number Leetcode Solution
You are given an integer num. Rearrange the digits of num such that its value is minimized and it does not contain any leading zeros.
Return the rearranged number with minimal value.
Note that the sign of the number does not change after rearranging the digits.
Example 1:
Input: num = 310
Output: 103
Explanation: The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310.
The arrangement with the smallest value that does not contain any leading zeros is 103.
Example 2:
Input: num = -7605
Output: -7650
Explanation: Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567.
The arrangement with the smallest value that does not contain any leading zeros is -7650.
Constraints:
-1015 <= num <= 1015
Smallest Value of the Rearranged Number Leetcode Solution in Python
class Solution:
def smallestNumber(self, num: int) -> int:
s = sorted(str(abs(num)), reverse = num < 0)
non_zero = next((i for i, n in enumerate(s) if n != '0'), 0)
s[0], s[non_zero] = s[non_zero], s[0]
return int(''.join(s)) * (1 if num >= 0 else -1)
Smallest Value of the Rearranged Number Leetcode Solution in C++
long long smallestNumber(long long num) {
auto s = to_string(abs(num));
sort(begin(s), end(s), [&](int a, int b){ return num < 0 ? a > b : a < b; });
if (num > 0)
swap(s[0], s[s.find_first_not_of('0')]);
return stoll(s) * (num < 0 ? -1 : 1);
}
Smallest Value of the Rearranged Number Leetcode Solution in Java
class Solution {
public long smallestNumber(long num) {
if(num == 0){
return 0;
}
boolean isNegative = num < 0;
num = num < 0 ? num * -1 : num;
char[] c = String.valueOf(num).toCharArray();
Arrays.sort(c);
String str;
if(!isNegative){
int non = 0;
//if not negative we need to find out the first non-leading zero then swap with first zero
for(; non < c.length; non++){
if(c[non] != '0'){
break;
}
}
char temp = c[non];
c[non] = c[0];
c[0] = temp;
str = new String(c);
}else{
str = new String(c);
StringBuilder sb = new StringBuilder(str);
str = "-".concat(sb.reverse().toString());
}
return Long.valueOf(str);
}
}
Smallest Value of the Rearranged Number Leetcode Solution in JavaScript
var smallestNumber = function(num) {
let arr = Array.from(String(num));
if(num>0){
arr.sort((a,b)=>{
return a-b;
})
}
else{
arr.sort((a,b)=>{
return b-a;
})
}
for(let i=0;i<arr.length;i++){
if(arr[i]!=0){
[arr[0],arr[i]]=[arr[i],arr[0]];
break;
}
}
return arr.join("");
};
Problem 3 – Design Bitset Leetcode Solution
A Bitset is a data structure that compactly stores bits.
Implement the Bitset class:
Bitset(int size)Initializes the Bitset withsizebits, all of which are0.void fix(int idx)Updates the value of the bit at the indexidxto1. If the value was already1, no change occurs.void unfix(int idx)Updates the value of the bit at the indexidxto0. If the value was already0, no change occurs.void flip()Flips the values of each bit in the Bitset. In other words, all bits with value0will now have value1and vice versa.boolean all()Checks if the value of each bit in the Bitset is1. Returnstrueif it satisfies the condition,falseotherwise.boolean one()Checks if there is at least one bit in the Bitset with value1. Returnstrueif it satisfies the condition,falseotherwise.int count()Returns the total number of bits in the Bitset which have value1.String toString()Returns the current composition of the Bitset. Note that in the resultant string, the character at theithindex should coincide with the value at theithbit of the Bitset.
Example 1:
Input
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
Output
[null, null, null, null, false, null, null, true, null, 2, "01010"]
Explanation
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3); // the value at idx = 3 is updated to 1, so bitset = "00010".
bs.fix(1); // the value at idx = 1 is updated to 1, so bitset = "01010".
bs.flip(); // the value of each bit is flipped, so bitset = "10101".
bs.all(); // return False, as not all values of the bitset are 1.
bs.unfix(0); // the value at idx = 0 is updated to 0, so bitset = "00101".
bs.flip(); // the value of each bit is flipped, so bitset = "11010".
bs.one(); // return True, as there is at least 1 index with value 1.
bs.unfix(0); // the value at idx = 0 is updated to 0, so bitset = "01010".
bs.count(); // return 2, as there are 2 bits with value 1.
bs.toString(); // return "01010", which is the composition of bitset.
Constraints:
1 <= size <= 1050 <= idx <= size - 1- At most
105calls will be made in total tofix,unfix,flip,all,one,count, andtoString. - At least one call will be made to
all,one,count, ortoString. - At most
5calls will be made totoString.
Design Bitset Leetcode Solution in Java
class Bitset {
int size;
Set<Integer> one = new HashSet<>();
Set<Integer> zero = new HashSet<>();
public Bitset(int size) {
this.size = size;
for(int i=0;i<size;i++) zero.add(i);
}
public void fix(int idx) {
one.add(idx);
zero.remove(idx);
}
public void unfix(int idx) {
one.remove(idx);
zero.add(idx);
}
//swapping object's referrence is O(1)
public void flip() {
Set<Integer> s = one;
one = zero;
zero = s;
}
public boolean all() {
return one.size() == size;
}
public boolean one() {
return one.size()>=1;
}
public int count() {
return one.size();
}
public String toString() {
StringBuilder sb= new StringBuilder();
for(int i=0;i<size;i++) {
if(one.contains(i)) sb.append("1");
else if(zero.contains(i)) sb.append("0");
}
return sb.toString();
}
}
Design Bitset Leetcode Solution in C++
int a = 0, sz = 0, cnt = 0, isFlip = 0;
string s;
Bitset(int size) {
sz = size;
s = string(sz, '0');
}
void fix(int idx) {
if (s[idx] == '0' + isFlip) {
s[idx] = '1' + '0' - s[idx];
cnt++;
}
}
void unfix(int idx) {
if (s[idx] == '1' - isFlip) {
s[idx] = '1' + '0' - s[idx];
cnt--;
}
}
void flip() {
isFlip ^= 1;
cnt = sz - cnt;
}
bool all() {
return cnt == sz;
}
bool one() {
return cnt > 0;
}
int count() {
return cnt;
}
string toString() {
if (isFlip) {
string s2 = s;
for (auto& c: s2)
c = '0' + '1' - c;
return s2;
}
return s;
}
Design Bitset Leetcode Solution in Python
class Bitset(object):
def __init__(self, size):
self.a = 0
self.size = size
self.cnt = 0
def fix(self, idx):
if self.a & (1 << idx) == 0:
self.a |= 1 << idx
self.cnt += 1
def unfix(self, idx):
if self.a & (1 << idx):
self.a ^= 1 << idx
self.cnt -= 1
def flip(self):
self.a ^= (1 << self.size) - 1
self.cnt = self.size - self.cnt
def all(self):
return self.cnt == self.size
def one(self):
return self.a > 0
def count(self):
return self.cnt
def toString(self):
a = bin(self.a)[2:]
return a[::-1] + '0' * (self.size - len(a))
Design Bitset Leetcode Solution in Python 3
def __init__(self, size: int):
self.sz = size
self.bits = [False] * size
self.flipped = [True] * size
self.bitCount = 0
def fix(self, idx: int) -> None:
if not self.bits[idx]:
self.bits[idx] ^= True
self.flipped[idx] ^= True
self.bitCount += 1
def unfix(self, idx: int) -> None:
if self.bits[idx]:
self.bits[idx] ^= True
self.flipped[idx] ^= True
self.bitCount -= 1
def flip(self) -> None:
self.bits, self.flipped = self.flipped, self.bits
self.bitCount = self.sz - self.bitCount
def all(self) -> bool:
return self.sz == self.bitCount
def one(self) -> bool:
return self.bitCount > 0
def count(self) -> int:
return self.bitCount
def toString(self) -> str:
return ''.join(['1' if b else '0' for b in self.bits])
Problem 4 – Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution
You are given a 0-indexed binary string s which represents a sequence of train cars. s[i] = '0' denotes that the ith car does not contain illegal goods and s[i] = '1' denotes that the ith car does contain illegal goods.
As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations any number of times:
- Remove a train car from the left end (i.e., remove
s[0]) which takes 1 unit of time. - Remove a train car from the right end (i.e., remove
s[s.length - 1]) which takes 1 unit of time. - Remove a train car from anywhere in the sequence which takes 2 units of time.
Return the minimum time to remove all the cars containing illegal goods.
Note that an empty sequence of cars is considered to have no cars containing illegal goods.
Example 1:
Input: s = "1100101"
Output: 5
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end. Time taken is 1.
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2 + 1 + 2 = 5.
An alternative way is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
This also obtains a total time of 2 + 3 = 5.
5 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.
Example 2:
Input: s = "0010"
Output: 2
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
This obtains a total time of 3.
Another way to remove all the cars containing illegal goods from the sequence is to
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2.
Another way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the right end 2 times. Time taken is 2 * 1 = 2.
This obtains a total time of 2.
2 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.
Constraints:
1 <= s.length <= 2 * 105s[i]is either'0'or'1'.
Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in
public int minimumTime(String s) {
int n = s.length(), left = 0, res = n;
for (int i = 0; i < n; ++i) {
left = Math.min(left + (s.charAt(i) - '0') * 2, i + 1);
res = Math.min(res, left + n - 1 - i);
}
return res;
}
Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in C++
int minimumTime(string s) {
int n = s.size(), left = 0, res = n;
for (int i = 0; i < n; ++i) {
left = min(left + (s[i] - '0') * 2, i + 1);
res = min(res, left + n - 1 - i);
}
return res;
}
Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in Python
def minimumTime(self, s):
left, res, n = 0, len(s), len(s)
for i,c in enumerate(s):
left = min(left + (c == '1') * 2, i + 1)
res = min(res, left + n - 1 - i)
return res
Weekly Contest 279 LeetCode Solution Review:
In our experience, we suggest you solve this Weekly Contest 279 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 279 LeetCode Solution
Conclusion:
I hope this Weekly Contest 279 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
