-
-
Save mgabrielmarin/5c6f8b1a281a0a8a8bd64bc59248b6fa to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* Sliding window algorithm | |
| * | |
| * Implementation of the examples from: | |
| * https://leetcode.com/explore/interview/card/leetcodes-interview-crash-course-data-structures-and-algorithms/703/arraystrings/4502/ | |
| */ | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| // Find the longest sub-array that has | |
| // the sum of elements less or equal to 'k' | |
| int sw(int *a, int len, int k) { | |
| int curr = 0; | |
| int res = 0; | |
| for (int i = 0, j = 0; j < len; ++j) { | |
| curr += a[j]; | |
| while (curr > k) curr -= a[i++]; | |
| if (res < j - i + 1) res = j - i + 1; | |
| } | |
| return res; | |
| } | |
| // Find the longest sub-string that contains only | |
| // '1' by changing only one '0' to '1'. | |
| int sw2(char *s) { | |
| int c = 0, r = 0; | |
| int len = strlen(s); | |
| for (int i = 0, j = 0; j < len; ++j) { | |
| if (s[j] == '0') c++; | |
| while (c > 1) | |
| if (s[i++] == '0') c--; | |
| if (r < j - i + 1) r = j - i + 1; | |
| } | |
| return r; | |
| } | |
| // Given an array of positive integers nums and an integer k, | |
| // return the number of subarrays where the product of all | |
| // the elements in the subarray is strictly less than k. | |
| int sw3(int *a, int len, int k) { | |
| int curr = 1, res = 0; | |
| for (int i = 0, j = 0; j < len; ++j) { | |
| curr *= a[j]; | |
| while (curr >= k) curr /= a[i++]; | |
| res += j - i + 1; | |
| } | |
| return res; | |
| } | |
| // Given an integer array nums and an integer k, find the sum | |
| // of the subarray with the largest sum whose length is k. | |
| int sw4(int *a, int len, int k) { | |
| int curr = 0; | |
| int res = 0; | |
| for (int i = 0; i < k; ++i) { | |
| curr += a[i]; | |
| } | |
| res = curr; | |
| for (int i = k; i < len; ++i) { | |
| curr += a[i]; | |
| curr -= a[i-k]; | |
| if (res < curr) res = curr; | |
| } | |
| return res; | |
| } | |
| int main(void) { | |
| int a[6] = {3,2,1,3,1,1}; | |
| int r = sw(a, 6, 5); | |
| printf("%d\n", r); | |
| char *s = "1101100111"; | |
| r = sw2(s); | |
| printf("%d\n", r); | |
| int a2[4] = {10,5,2,6}; | |
| r = sw3(a2, 4, 100); | |
| printf("%d\n", r); | |
| int a3[7] = {3,-1,4,12,-8,5,6}; | |
| r = sw4(a3, 7, 4); | |
| printf("%d\n", r); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment