aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_manhattan_dist_k_change.c39
-rw-r--r--max_manhattan_dist_k_change.py35
-rw-r--r--partition_arr_max_diff_k.c32
-rw-r--r--partition_arr_max_diff_k.py34
4 files changed, 140 insertions, 0 deletions
diff --git a/max_manhattan_dist_k_change.c b/max_manhattan_dist_k_change.c
new file mode 100644
index 0000000..70e735a
--- /dev/null
+++ b/max_manhattan_dist_k_change.c
@@ -0,0 +1,39 @@
+// 3443. Maximum Manhattan Distance After K Changes
+#include "leetcode.h"
+
+/*
+ * you are given a sing 's' consisting of the characters 'N', 'S', 'E', and
+ * 'W', where 's[i]' indicates movements in an infinite grid, where each letter
+ * is a move of 1 unit in that cardinal direction. initially, you are at the
+ * origin '(0, 0)'. you can change at most 'k' characters to any of the four
+ * directions. find the maximum manhattan distance from the origin that can be
+ * achieved at any time while performing the movements in order.
+ */
+
+int maxDistance(char *s, int k) {
+ const char dir[4][2] = {{'N', 'E'}, {'N', 'W'}, {'S', 'E'}, {'S', 'W'}};
+ int ans = 0;
+ for (int i = 0; i < 4; i++) {
+ bool set[1 << (CHAR_BIT - 1)] = {0};
+ set[dir[i][0]] = set[dir[i][1]] = true;
+ int curr_dist = 0, curr_k = k;
+ for (int j = 0; s[j] != '\0'; j++) {
+ if (!set[s[j]] && !(curr_k >= 1)) {
+ curr_dist--;
+ continue;
+ }
+ if (!set[s[j]])
+ curr_k--;
+ curr_dist++;
+ if (curr_dist > ans)
+ ans = curr_dist;
+ }
+ }
+ return ans;
+}
+
+int main() {
+ char *s1 = "NWSE", *s2 = "NSWWEW";
+ printf("%d\n", maxDistance(s1, 1)); // expect: 3
+ printf("%d\n", maxDistance(s2, 3)); // expect: 6
+}
diff --git a/max_manhattan_dist_k_change.py b/max_manhattan_dist_k_change.py
new file mode 100644
index 0000000..5bb0ee2
--- /dev/null
+++ b/max_manhattan_dist_k_change.py
@@ -0,0 +1,35 @@
+# 3443. Maximum Manhattan Distance After K Changes
+
+"""
+you are given a sing 's' consisting of the characters 'N', 'S', 'E', and
+'W', where 's[i]' indicates movements in an infinite grid, where each letter
+is a move of 1 unit in that cardinal direction. initially, you are at the
+origin '(0, 0)'. you can change at most 'k' characters to any of the four
+directions. find the maximum manhattan distance from the origin that can be
+achieved at any time while performing the movements in order.
+"""
+
+
+class Solution(object):
+ def maxDistance(self, s, k):
+ """
+ :type s: str
+ :type k: int
+ :rtype: int
+ """
+ ans = 0
+ for i in [{"N", "E"}, {"N", "W"}, {"S", "E"}, {"S", "W"}]:
+ curr_dist, curr_k = 0, k
+ for j in s:
+ curr_dist += 1
+ curr_k -= j not in i
+ else:
+ curr_dist -= 1
+ ans = max(ans, curr_dist)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxDistance(s="NWSE", k=1))
+ print(obj.maxDistance(s="NSWWEW", k=3))
diff --git a/partition_arr_max_diff_k.c b/partition_arr_max_diff_k.c
new file mode 100644
index 0000000..4a1e3aa
--- /dev/null
+++ b/partition_arr_max_diff_k.c
@@ -0,0 +1,32 @@
+// 2294. Partition Array Such That Maximum Difference Is K
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'k'. you may partition
+ * 'nums' into one or more subsequences such that each element in 'nums' appears
+ * in exactly one of the subsequences. return the minimum number of subsequences
+ * needed such that the difference between the maximum and minimum values in
+ * each subsequence is at most 'k'. a subsequence is a sequence that can be
+ * derived from another sequence by deleting some or no elements without
+ * changing the order of the remaining elements.
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int partitionArray(int *nums, int numsSize, int k) {
+ qsort(nums, numsSize, sizeof(int), cmp);
+ int ans = 1, j = 0;
+ for (int i = 1; i < numsSize; i++)
+ if (nums[i] - nums[j] > k) {
+ ans++;
+ j = i;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {3, 6, 1, 2, 5}, n2[] = {1, 2, 3}, n3[] = {2, 2, 4, 5};
+ printf("%d\n", partitionArray(n1, ARRAY_SIZE(n1), 2)); // expect: 2
+ printf("%d\n", partitionArray(n2, ARRAY_SIZE(n2), 1)); // expect: 2
+ printf("%d\n", partitionArray(n3, ARRAY_SIZE(n3), 0)); // expect: 3
+}
diff --git a/partition_arr_max_diff_k.py b/partition_arr_max_diff_k.py
new file mode 100644
index 0000000..555cdf9
--- /dev/null
+++ b/partition_arr_max_diff_k.py
@@ -0,0 +1,34 @@
+# 2294. Partition Array Such That Maximum Difference Is K
+
+"""
+you are given an integer array 'nums' and an integer 'k'. you may partition
+'nums' into one or more subsequences such that each element in 'nums' appears
+in exactly one of the subsequences. return the minimum number of subsequences
+needed such that the difference between the maximum and minimum values in
+each subsequence is at most 'k'. a subsequence is a sequence that can be
+derived from another sequence by deleting some or no elements without
+changing the order of the remaining elements.
+"""
+
+
+class Solution(object):
+ def partitionArray(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ nums.sort()
+ ans, j = 1, 0
+ for i in range(len(nums)):
+ if nums[i] - nums[j] > k:
+ ans += 1
+ j = i
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.partitionArray(nums=[3, 6, 1, 2, 5], k=2))
+ print(obj.partitionArray(nums=[1, 2, 3], k=1))
+ print(obj.partitionArray(nums=[2, 2, 4, 5], k=0))