aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--diagonal_traverse.c57
-rw-r--r--diagonal_traverse.py43
-rw-r--r--longest_subarr_ones.c25
-rw-r--r--longest_subarr_ones.py32
4 files changed, 145 insertions, 12 deletions
diff --git a/diagonal_traverse.c b/diagonal_traverse.c
new file mode 100644
index 0000000..802271d
--- /dev/null
+++ b/diagonal_traverse.c
@@ -0,0 +1,57 @@
+// 498. Diagonal Traverse
+#include "leetcode.h"
+
+/*
+ * given an 'm x n' matrix 'mat', return an array of all the elements of the
+ * array in a diagonal order.
+ */
+
+int *findDiagonalOrder(int **mat, int matSize, int *matColSize,
+ int *returnSize) {
+ int n = matSize * matColSize[0], row = 0, col = 0;
+ int *ans = (int *)malloc(n * sizeof(int));
+ *returnSize = n;
+ for (int i = 0; i < n; i++) {
+ ans[i] = mat[row][col];
+ if (!((row + col) % 2)) {
+ if (col == matSize - 1)
+ row++;
+ else if (!row)
+ col++;
+ else {
+ row--;
+ col++;
+ }
+ } else {
+ if (row == matColSize[0] - 1)
+ col++;
+ else if (!col)
+ row++;
+ else {
+ row++;
+ col--;
+ }
+ }
+ }
+ return ans;
+}
+
+int main() {
+ int m1i[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}},
+ m2i[2][2] = {{1, 2}, {3, 4}};
+ struct two_d_arr m1, m2;
+ two_d_arr_init(&m1, ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i);
+ two_d_arr_init(&m2, ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i);
+ int rs1, *fdo1 = findDiagonalOrder(m1.arr, m1.row_size, m1.col_size, &rs1);
+ int rs2, *fdo2 = findDiagonalOrder(m2.arr, m2.row_size, m2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", fdo1[i]); // expect: 1 2 4 7 5 3 6 8 9
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", fdo2[i]); // expect: 1 2 3 4
+ printf("\n");
+ free(fdo1);
+ free(fdo2);
+ two_d_arr_free(&m1);
+ two_d_arr_free(&m2);
+}
diff --git a/diagonal_traverse.py b/diagonal_traverse.py
new file mode 100644
index 0000000..d75deec
--- /dev/null
+++ b/diagonal_traverse.py
@@ -0,0 +1,43 @@
+# 498. Diagonal Traverse
+
+"""
+given an 'm x n' matrix 'mat', return an array of all the elements of the
+array in a diagonal order.
+"""
+
+
+class Solution(object):
+ def findDiagonalOrder(self, mat):
+ """
+ :type mat: List[List[int]]
+ :rtype: List[int]
+ """
+ if not mat or not mat[0]:
+ return []
+ m, n = len(mat), len(mat[0])
+ ans, row, col = [], 0, 0
+ for _ in range(m * n):
+ ans.append(mat[row][col])
+ if (row + col) % 2 == 0:
+ if col == n - 1:
+ row += 1
+ elif row == 0:
+ col += 1
+ else:
+ row -= 1
+ col += 1
+ else:
+ if row == m - 1:
+ col += 1
+ elif col == 0:
+ row += 1
+ else:
+ row += 1
+ col -= 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findDiagonalOrder(mat=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
+ print(obj.findDiagonalOrder(mat=[[1, 2], [3, 4]]))
diff --git a/longest_subarr_ones.c b/longest_subarr_ones.c
index 049ce33..dc9aa84 100644
--- a/longest_subarr_ones.c
+++ b/longest_subarr_ones.c
@@ -1,6 +1,5 @@
// 1493. Longest Subarray of 1's After Deleting One Element
-#include <math.h>
-#include <stdio.h>
+#include "leetcode.h"
/*
* given a binary array 'nums', you should delete one element from it. return
@@ -8,24 +7,26 @@
* resulting array. return 0 if there is no such subarray.
*/
-int longestSubarray(int *nums, int nums_size) {
- int n = nums_size, zero_cnt = 0, ans = 0, left = 0;
- for (int right = 0; right < n; right++) {
+int longestSubarray(int *nums, int numsSize) {
+ int left = 0, zeros = 0, ans = 0;
+ for (int right = 0; right < numsSize; right++) {
if (!nums[right])
- zero_cnt++;
- while (zero_cnt > 1) {
+ zeros++;
+ while (zeros > 1) {
if (!nums[left])
- zero_cnt--;
+ zeros--;
left++;
}
- ans = fmax(ans, right - left);
+ int length = right - left;
+ if (length > ans)
+ ans = length;
}
return ans;
}
int main() {
int n1[] = {1, 1, 0, 1}, n2[] = {0, 1, 1, 1, 0, 1, 1, 0, 1}, n3[] = {1, 1, 1};
- printf("%d\n", longestSubarray(n1, 4)); // expect: 3
- printf("%d\n", longestSubarray(n2, 9)); // expect: 5
- printf("%d\n", longestSubarray(n3, 3)); // expect: 2
+ printf("%d\n", longestSubarray(n1, ARRAY_SIZE(n1))); // expect: 3
+ printf("%d\n", longestSubarray(n2, ARRAY_SIZE(n2))); // expect: 5
+ printf("%d\n", longestSubarray(n3, ARRAY_SIZE(n3))); // expect: 2
}
diff --git a/longest_subarr_ones.py b/longest_subarr_ones.py
new file mode 100644
index 0000000..a4b3623
--- /dev/null
+++ b/longest_subarr_ones.py
@@ -0,0 +1,32 @@
+# 1493. Longest Subarray of 1's After Deleting One Element
+
+"""
+given a binary array 'nums', you should delete one element from it. return
+the size of the longest non-empty subarray containing only 1's in the
+resulting array. return 0 if there is no such subarray.
+"""
+
+
+class Solution(object):
+ def longestSubarray(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ left, zeros, ans = 0, 0, 0
+ for right in range(len(nums)):
+ if nums[right] == 0:
+ zeros += 1
+ while zeros > 1:
+ if nums[left] == 0:
+ zeros -= 1
+ left += 1
+ ans = max(ans, right - left)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.longestSubarray(nums=[1, 1, 0, 1]))
+ print(obj.longestSubarray(nums=[0, 1, 1, 1, 0, 1, 1, 0, 1]))
+ print(obj.longestSubarray(nums=[1, 1, 1]))