aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--largest_divisible_subset.c28
-rw-r--r--max_diff_change_int.c44
-rw-r--r--max_diff_change_int.py35
-rw-r--r--partition_equal_subset_sum.c37
-rw-r--r--partition_equal_subset_sum.py25
-rw-r--r--sum_subset_xor.c23
-rw-r--r--sum_subset_xor.py22
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__":