diff options
-rw-r--r-- | max_manhattan_dist_k_change.c | 39 | ||||
-rw-r--r-- | max_manhattan_dist_k_change.py | 35 | ||||
-rw-r--r-- | partition_arr_max_diff_k.c | 32 | ||||
-rw-r--r-- | partition_arr_max_diff_k.py | 34 |
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)) |