diff options
-rw-r--r-- | largest_divisible_subset.c | 28 | ||||
-rw-r--r-- | max_diff_change_int.c | 44 | ||||
-rw-r--r-- | max_diff_change_int.py | 35 | ||||
-rw-r--r-- | partition_equal_subset_sum.c | 37 | ||||
-rw-r--r-- | partition_equal_subset_sum.py | 25 | ||||
-rw-r--r-- | sum_subset_xor.c | 23 | ||||
-rw-r--r-- | sum_subset_xor.py | 22 |
7 files changed, 142 insertions, 72 deletions
diff --git a/largest_divisible_subset.c b/largest_divisible_subset.c index f540528..6d36c45 100644 --- a/largest_divisible_subset.c +++ b/largest_divisible_subset.c @@ -10,14 +10,14 @@ int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } -int *largestDivisibleSubset(int *nums, int nums_size, int *return_size) { - qsort(nums, nums_size, sizeof(int), cmp); - int *idx = malloc(nums_size * sizeof(int)); - int *cnt = malloc(nums_size * sizeof(int)); +int *largestDivisibleSubset(int *nums, int numsSize, int *returnSize) { + qsort(nums, numsSize, sizeof(int), cmp); + int *idx = (int *)malloc(numsSize * sizeof(int)); + int *cnt = (int *)malloc(numsSize * sizeof(int)); int max = 1, max_idx = 0, tmp; idx[0] = -1; cnt[0] = 1; - for (int i = 1; i < nums_size; i++) { + for (int i = 1; i < numsSize; i++) { idx[i] = -1; cnt[i] = 1; for (int j = i - 1; j >= 0; j--) @@ -33,25 +33,25 @@ int *largestDivisibleSubset(int *nums, int nums_size, int *return_size) { max_idx = i; } } - *return_size = max; - int *ans = malloc(max * sizeof(int)); + *returnSize = max; + int *ans = (int *)malloc(max * sizeof(int)); for (int i = max - 1; i >= 0; i--) { ans[i] = nums[max_idx]; max_idx = idx[max_idx]; } - free(idx), free(cnt); + free(idx); + free(cnt); return ans; } int main() { - int n1[] = {1, 2, 3}, n2[] = {1, 2, 4, 8}; - int rs1[] = {}, rs2[] = {}; - int *lds1 = largestDivisibleSubset(n1, ARRAY_SIZE(n1), rs1); - int *lds2 = largestDivisibleSubset(n2, ARRAY_SIZE(n2), rs2); - for (int i = 0; i < 2; i++) + int n1[] = {1, 2, 3}, n2[] = {1, 2, 4, 8}, rs1, rs2; + int *lds1 = largestDivisibleSubset(n1, ARRAY_SIZE(n1), &rs1); + int *lds2 = largestDivisibleSubset(n2, ARRAY_SIZE(n2), &rs2); + for (int i = 0; i < rs1; i++) printf("%d ", lds1[i]); // expect: 1 2 printf("\n"); - for (int i = 0; i < 4; i++) + for (int i = 0; i < rs2; i++) printf("%d ", lds2[i]); // expect: 1 2 4 8 printf("\n"); free(lds1), free(lds2); diff --git a/max_diff_change_int.c b/max_diff_change_int.c new file mode 100644 index 0000000..e272359 --- /dev/null +++ b/max_diff_change_int.c @@ -0,0 +1,44 @@ +// 1432. Max Difference You Can Get From Changing an Integer +#include "leetcode.h" + +/* + * you are given an integer 'num'. you will apply the following steps exactly + * two times: pick a digit 'x (0 <= x <= 9)', pick another digit 'y (0 <= y <= + * 9)'. the digit 'y' can be equal to 'x'. replace all occurences of 'x' in the + * decimal representation of 'num' by 'y'. the new integer cannot have any + * leading zeros. also the new integer cannot be 0. let 'a' and 'b' be the + * results of applying the operations to 'num' the first and second times + * respectively. return the max difference between 'a' and 'b'. + */ + +int maxDiff(int num) { + char order[10], x, y; + sprintf(order, "%d", num); + int i; + for (i = 0; order[i] && order[i] == '9'; i++) + ; + if (order[i]) { + x = order[i]; + for (; order[i]; i++) + if (order[i] == x) + order[i] = '9'; + } + int a = atoi(order); + sprintf(order, "%d", num); + for (i = 0; order[i] && (order[i] == '0' || order[i] == '1'); i++) + ; + if (order[i]) { + x = order[i]; + y = (order[0] != '1') + '0'; + for (; order[i]; i++) + if (order[i] == x) + order[i] = y; + } + int b = atoi(order); + return a - b; +} + +int main() { + printf("%d\n", maxDiff(555)); // expect: 888 + printf("%d\n", maxDiff(9)); // expect: 8 +} diff --git a/max_diff_change_int.py b/max_diff_change_int.py new file mode 100644 index 0000000..fbf9fb0 --- /dev/null +++ b/max_diff_change_int.py @@ -0,0 +1,35 @@ +# 1432. Max Difference You Can Get From Changing an Integer + +""" +you are given an integer 'num'. you will apply the following steps exactly +two times: pick a digit 'x (0 <= x <= 9)', pick another digit 'y (0 <= y <= +9)'. the digit 'y' can be equal to 'x'. replace all occurences of 'x' in the +decimal representation of 'num' by 'y'. the new integer cannot have any +leading zeros. also the new integer cannot be 0. let 'a' and 'b' be the +results of applying the operations to 'num' the first and second times +respectively. return the max difference between 'a' and 'b'. +""" + + +class Solution(object): + def maxDiff(self, num): + """ + :type num: int + :rtype: int + """ + n = str(num) + maxn, minn = float("-inf"), float("inf") + for i in "0123456789": + for j in "0123456789": + next = n.replace(i, j) + if next[0] == "0" or int(next) == 0: + continue + maxn = max(maxn, int(next)) + minn = min(minn, int(next)) + return maxn - minn + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxDiff(num=555)) + print(obj.maxDiff(num=9)) diff --git a/partition_equal_subset_sum.c b/partition_equal_subset_sum.c index 91156f2..d71deb5 100644 --- a/partition_equal_subset_sum.c +++ b/partition_equal_subset_sum.c @@ -7,26 +7,37 @@ * or false otherwise */ -bool is_subset_sum(int *nums, int numsSize, int sum) { - bool dp[numsSize + 1][numsSize + 1]; - for (int i = 0; i <= numsSize; i++) - dp[i][0] = true; - for (int i = 1; i <= sum; i++) - dp[0][i] = false; - for (int i = 1; i <= numsSize; i++) - for (int j = 1; j <= sum; j++) - dp[i][j] = nums[i - 1] <= j ? dp[i - 1][j - nums[i - 1]] || dp[i - 1][j] - : dp[i - 1][j]; - return dp[numsSize][sum]; +bool memo(int *nums, int **dp, int sum, int idx, int n) { + if (!sum) + return true; + if (idx >= n) + return false; + if (dp[idx][sum] != -1) + return dp[idx][sum]; + bool pick = false, no_pick = false; + if (nums[idx] <= sum) + pick = memo(nums, dp, sum - nums[idx], idx + 1, n); + no_pick = memo(nums, dp, sum, idx + 1, n); + return dp[idx][sum] = (pick || no_pick); } bool canPartition(int *nums, int numsSize) { int sum = 0; for (int i = 0; i < numsSize; i++) sum += nums[i]; - if ((sum % 2)) + if (sum & 1) return false; - return is_subset_sum(nums, numsSize, sum / 2); + int **dp = (int **)malloc(numsSize * sizeof(int *)); + for (int i = 0; i < numsSize; i++) { + dp[i] = (int *)malloc(((sum >> 1) + 1) * sizeof(int)); + for (int j = 0; j < ((sum >> 1) + 1); ++j) + dp[i][j] = -1; + } + bool ans = memo(nums, dp, sum >> 1, 0, numsSize); + for (int i = 0; i < numsSize; i++) + free(dp[i]); + free(dp); + return ans; } int main() { diff --git a/partition_equal_subset_sum.py b/partition_equal_subset_sum.py index 7f563b7..3f63a5c 100644 --- a/partition_equal_subset_sum.py +++ b/partition_equal_subset_sum.py @@ -13,13 +13,24 @@ class Solution(object): :type nums: List[int] :rtype: bool """ - total_sum = sum(nums) - if total_sum & 1: - return False - half_sum, dp = total_sum // 2, 1 - for n in nums: - dp |= dp << n - return dp & 1 << half_sum + n = len(nums) + dp = [[-1 for _ in range(((sum(nums) >> 1) + 1))] for _ in range(n)] + + def memo(sm, idx): + if sm == 0: + return True + if idx >= len(nums): + return False + if dp[idx][sm] != -1: + return True if dp[idx][sm] == 1 else False + pick, no_pick = False, False + if nums[idx] <= sm: + pick = memo(sm - nums[idx], idx + 1) + no_pick = memo(sm, idx + 1) + dp[idx][sm] = 1 if pick or no_pick else 0 + return True if dp[idx][sm] == 1 else False + + return False if (sum(nums) & 1) else memo(sum(nums) >> 1, 0) if __name__ == "__main__": diff --git a/sum_subset_xor.c b/sum_subset_xor.c index cb51647..7c32618 100644 --- a/sum_subset_xor.c +++ b/sum_subset_xor.c @@ -8,26 +8,11 @@ * if 'a' can be obtained from 'b' by deleting some elements of 'b'. */ -void backtrack(int *nums, int numsSize, int tar, int idx, int *cnt) { - if (idx == numsSize) { - return; - } else { - for (int i = idx; i < numsSize; i++) { - tar ^= nums[i]; - *cnt += tar; - backtrack(nums, numsSize, tar, i + 1, cnt); - tar ^= nums[i]; - } - } -} - int subsetXORSum(int *nums, int numsSize) { - int ans = 0; - for (int i = 0; i < numsSize; i++) { - ans += nums[i]; - backtrack(nums, numsSize, nums[i], i + 1, &ans); - } - return ans; + int all = 0, mult = 1 << (numsSize - 1); + for (int i = 0; i < numsSize; i++) + all |= nums[i]; + return all * mult; } int main() { diff --git a/sum_subset_xor.py b/sum_subset_xor.py index deb88ed..0560197 100644 --- a/sum_subset_xor.py +++ b/sum_subset_xor.py @@ -1,4 +1,6 @@ # 1863. Sum of All Subset XOR Totals +from functools import reduce +from operator import or_ """ the xor total of an array is defined as the bitwise xor of all its elements @@ -14,25 +16,7 @@ class Solution(object): :type nums: List[int] :rtype: int """ - - def backtrack(nums, idx, tar, cnt): - if idx == len(nums): - cnt.append(tar[:]) - return - tar.append(nums[idx]) - backtrack(nums, idx + 1, tar, cnt) - tar.pop() - backtrack(nums, idx + 1, tar, cnt) - - cnt = [] - backtrack(nums, 0, [], cnt) - ans = 0 - for i in cnt: - total = 0 - for n in i: - total ^= n - ans += total - return ans + return reduce(or_, nums) << (len(nums) - 1) if __name__ == "__main__": |