leeym
BAN USER<pre lang="" line="1" title="CodeMonkey21978" class="run-this">#include <stdio.h>
void print_layer_top_right(int a[], int x1, int y1, int x2, int y2, int x = 0);
void print_layer_bottom_left(int a[], int x1, int y1, int x2, int y2, int x = 0);
/*
* 1 2 3 4 5
* 6 7 8 9 10
* 11 12 13 14 15
* 16 17 18 19 20
*/
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
print_layer_top_right(arr, 0, 0, 4, 3);
printf("\n");
}
void print_layer_top_right(int a[], int x1, int y1, int x2, int y2, int x)
{
if (!x1 && !y1 && !x)
x = x2 + 1;
for (int i = x1; i <= x2; i++)
printf(" %d", a[y1 * x + i]);
for (int j = y1 + 1; j <= y2; j++)
printf(" %d", a[j * x + x2]);
if (x2 > x1)
print_layer_bottom_left(a, x1, y1 + 1, x2 - 1, y2, x);
}
void print_layer_bottom_left(int a[], int x1, int y1, int x2, int y2, int x)
{
if (!x1 && !y1 && !x)
x = x2 + 1;
for (int i = x2; i >= x1; i--)
printf(" %d", a[y2 * x + i]);
for (int j = y2 - 1; j >= y1; j--)
printf(" %d", a[j * x + x1]);
if (y2 > y1)
print_layer_top_right(a, x1 + 1, y1, x2, y2 - 1, x);
}
</pre><pre title="CodeMonkey21978" input="yes">
</pre>
#include <stdio.h>
int main()
{
int nums[] = { 3, 2, 8, 9, -25, 5, 8, 4, 4, -3, 5, 3, -10 };
int start = 0, end = 0, max = 0, sum = 0, s = 0, e = 0;
for (; e < sizeof(nums) / sizeof(nums[0]); ++e) {
sum += nums[e];
if (sum > max) { // if sum is greater than max, update start/end/max
max = sum;
start = s;
end = e;
} else if (sum < 0) { // if sum is less than 0, reset it to 0
s = e + 1;
sum = 0;
}
}
printf("Start:%d End:%d Max:%d\n", start, end, max);
}
I think it should be 3a2b2c3a2d.
#include <string>
std::string compress(std::string src)
{
std::string dst;
char c = NULL;
int d = 0;
for (int i = 0; i < src.length(); ++i) {
if (src[i] != c) {
if (d) {
dst += '0' + d;
dst += c;
}
c = src[i];
d = 1;
} else {
++d;
}
}
if (d) {
dst += '0' + d;
dst += c;
}
return dst;
}
std::string decompress(std::string src)
{
std::string dst;
char c;
int d;
for (int i = 0; i < src.length(); ++i) {
d = atoi(&src[i]);
c = src[++i];
for (int j = 0; j < d; ++j)
dst += c;
}
return dst;
}
int main()
{
std::string str1 = "aaabbccaaadd";
std::string str2 = compress(str1);
std::string str3 = decompress(str2);
printf("[%s] -> [%s] -> [%s]\n", str1.c_str(), str2.c_str(), str3.c_str());
}
Output:
[aaabbccaaadd] -> [3a2b2c3a2d] -> [aaabbccaaadd]
Node *merge(Node *h1, Node *h2)
{
Node *head = NULL, *prev = NULL, *curr = NULL;
Node *c1 = h1, *c2 = h2;
while (c1 || c2) {
if (c2 == NULL) {
curr = c1;
c1 = c1->next;
} else if (c1 == NULL) {
curr = c2;
c2 = c2->next;
} else if (c1->value <= c2->value) {
curr = c1;
c1 = c1->next;
} else {
curr = c2;
c2 = c2->next;
}
if (prev) {
if (prev->value == curr->value)
continue;
else
prev->next = curr;
}
if (head == NULL)
head = curr;
prev = curr;
}
return head;
}
Node *preorder_next(Node *n, Node *target, bool &found)
{
if (n == NULL)
return NULL;
if (found)
return n;
if (n == target)
found = true;
Node *next = preorder_next(n->left, target, found);
if (next == NULL)
next = preorder_next(n->right, target, found);
return next;
}
Breadth-first search
#include <queue>
using namespace std;
struct Node {
int value;
struct Node *left;
struct Node *right;
Node(int v): value(v), left(NULL), right(NULL) {}
};
void bfs(Node *head)
{
queue<Node *>q;
q.push(head);
while (!q.empty()) {
Node *c = q.front();
q.pop();
printf(" %d", c->value);
if (c->left)
q.push(c->left);
if (c->right)
q.push(c->right);
}
printf("\n");
}
int main()
{
Node *n1 = new Node(1);
Node *n2 = new Node(2);
Node *n3 = new Node(3);
Node *n4 = new Node(4);
Node *n5 = new Node(5);
Node *n6 = new Node(6);
Node *n7 = new Node(7);
Node *n8 = new Node(8);
Node *n9 = new Node(9);
/*
* 4
* / \
* 3 7
* / \ / \
* 8 2 9 6
* / \
* 1 5
*/
n4->left = n3;
n4->right = n7;
n3->left = n8;
n3->right = n2;
n7->left = n9;
n7->right = n6;
n9->right = n5;
n8->left = n1;
// 4 3 7 8 2 9 6 1 5
Node *head = n4;
bfs(n4);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/*
* tokenize() is based on strsep()
* The only difference is how they handle the empty fields.
*/
bool match(char *c, const char *delim)
{
unsigned int len = strlen(delim);
for (unsigned int i = 0; i < len; i++) {
if (*c == *(delim + i))
return true;
}
return false;
}
char *tokenize(char **stringp, const char *delim)
{
char *p = *stringp;
// If *stringp is initially NULL, strsep() returns NULL.
if (*stringp == NULL)
return NULL;
unsigned int len = strlen(*stringp);
for (unsigned int i = 0; i < len; i++) {
/*
* locates, in the string referenced by *stringp, the
* first occurrence of any character in the string delim
* and replaces it with a '\0'
*/
if (match(p + i, delim)) {
*(p + i) = '\0';
for (unsigned int j = 1; j < len - i - 1; j++) {
/*
* The location of the next non-delimiter character after
* the delimiter character (or NULL, if the end of the
* string was reached) is stored in *stringp.
*/
if (!match(p + i + j, delim)) {
*stringp = (p + i + j);
break;
}
}
break;
}
}
if (*stringp == p)
*stringp = NULL;
// The original value of *stringp is returned.
return p;
}
int main()
{
char *token, *string, *tofree;
tofree = string = strdup("abc def ,ghi");
assert(string != NULL);
while ((token = tokenize(&string, " ,")) != NULL) {
printf("%s\n", token);
}
free(tofree);
}
#include <stdio.h>
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
Node(int v) : value(v), left(NULL), right(NULL) {}
} Node;
Node *sortedArrayToBST(int arr[], int start, int end)
{
if (start > end)
return NULL;
int mid = (start + end) / 2;
Node *node = new Node(arr[mid]);
node->left = sortedArrayToBST(arr, start, mid - 1);
node->right = sortedArrayToBST(arr, mid + 1, end);
return node;
}
Node *sortedArrayToBST(int arr[], int n)
{
return sortedArrayToBST(arr, 0, n - 1);
}
void preorderTraversal(Node *n)
{
if (n == NULL)
return;
printf(" %d", n->value);
preorderTraversal(n->left);
preorderTraversal(n->right);
}
void inorderTraversal(Node *n)
{
if (n == NULL)
return;
inorderTraversal(n->left);
printf(" %d", n->value);
inorderTraversal(n->right);
}
void postorderTraversal(Node *n)
{
if (n == NULL)
return;
postorderTraversal(n->left);
postorderTraversal(n->right);
printf(" %d", n->value);
}
int main(int argc, char **argv)
{
int sortedArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
Node *root = sortedArrayToBST(sortedArray, sizeof(sortedArray) / sizeof(sortedArray[0]));
printf("Inorder:");
inorderTraversal(root);
printf("\n");
printf("Preorder:");
preorderTraversal(root);
printf("\n");
printf("Postorder:");
postorderTraversal(root);
printf("\n");
}
Output:
Inorder: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Preorder: 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15
Postorder: 1 3 2 5 7 6 4 9 11 10 13 15 14 12 8
#include <stdlib.h>
#include <string>
int main()
{
std::string input[] = {
"When riding your bicycle backwards down a one-way street, if the",
"wheel falls of a canoe, how many ball bearings does it take to fill",
"up a water buffalo?",
"Hello Howard.",
};
for(unsigned int i = 0; i < sizeof(input) / sizeof(input[0]); i++) {
// we can take an array of size 256 (assuming all the 256 character can be present in the line).
unsigned int m = 0;
unsigned int f[256];
bzero(f, sizeof(unsigned int) * 256);
// now while reading each line we can increase the count of the character in the array.
for(unsigned int j = 0; j < input[i].length(); j++) {
char c = input[i][j];
if (!isalpha(c))
continue;
f[c]++;
// Find out the max count when scanning the characters in the string at the same time
if (f[c] > m)
m = f[c];
}
// Print char if its count equals to max count, followed by space and count
for(unsigned int c = 0; c < 256; c++)
if (f[c] == m)
printf("%c", c);
printf(" %d\n", m);
}
}
Pseudo code:
1. Two pointers start from head
2. One pointer advances one while the other advances two.
3.1 If two pointers meet, there is a loop
3.2 If pointer reachs the end, there is no loop
4. Find out how many nodes in the loop, say k.
5. Reset one pointer to the head, and the other pointer to head + k.
6. Move both pointers at the same pace, they will meet at loop starting node
7. Move one pointer till its next node is the loop starting node. It's the loop ending node
8. Set the next node of the loop ending node to fix the loop
9. Print the list
#include <stdio.h>
struct Node {
int value;
struct Node* next;
Node(int v): value(v), next(NULL) {}
};
struct List {
Node* head;
List(): head(NULL) {}
void push_back(Node *node) {
if (head == NULL) {
head = node;
return;
}
Node *cur = head;
while(cur->next != NULL) {
cur = cur->next;
}
cur->next = node;
}
};
int main()
{
List l;
// HEAD->1->2->3->'4'->5->6->7->'4'->5->6->7->'4'->5->6->7-> ...
l.push_back(new Node(1));
l.push_back(new Node(2));
l.push_back(new Node(3));
Node *four = new Node(4);
l.push_back(four);
l.push_back(new Node(5));
l.push_back(new Node(6));
l.push_back(new Node(7));
l.push_back(four);
Node *p1 = NULL, *p2 = NULL;
while(1) {
if (p1 == NULL && p2 == NULL) {
// 1. Two pointers start from head
p1 = l.head;
p2 = l.head;
} else {
// 3.1 If two pointers meet, there is a loop
if (p1 == p2)
break;
}
// 3.2 If pointer reachs the end, there is no loop
if (p2->next == NULL || p2->next->next == NULL) {
printf("There is no loop in the list.\n");
return 0;
}
// 2. One pointer advances one while the other advances two.
p1 = p1->next;
p2 = p2->next->next;
}
// 4. Find out how many nodes in the loop, say k.
unsigned int k = 1;
p2 = p2->next;
while (p1 != p2) {
p2 = p2->next;
k++;
}
printf("There are %d nodes in the loop of the list.\n", k);
// 5. Reset one pointer to the head, and the other pointer to head + k.
p1 = l.head;
p2 = l.head;
for (unsigned int i = 0; i < k; i++)
p2 = p2->next;
// 6. Move both pointers at the same pace, they will meet at loop starting node
while(p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
printf("node %d is the loop starting node.\n", p1->value);
// 7. Move one of the pointer till its next node is the loop starting node.
// It's the loop ending node
p2 = p2->next;
while(p2->next != p1)
p2 = p2->next;
printf("node %d is the loop ending node.\n", p2->value);
// 8. Set the next node of the loop ending node to fix the loop
p2->next = NULL;
// 9. Print the list
Node *cur = l.head;
printf("The list without loop is: ");
while(cur != NULL) {
printf("%d ", cur->value);
cur = cur->next;
}
printf("\n");
}
Output:
$ ./remove-loop-from-linked-list
There are 4 nodes in the loop of the list.
node 4 is the loop starting node.
node 7 is the loop ending node.
The list without loop is: 1 2 3 4 5 6 7
#include <stdio.h>
#include <stdlib.h>
#include <deque>
#include <set>
// calculate the actual index after offset
inline int offset(int idx, unsigned int num, unsigned int k)
{
return (num + idx - k) % num;
}
// binary search variation
bool binarySearch(std::deque<int>&a, int target, int k, int left, int right)
{
while (1) {
int center = (left + right) / 2;
int _left = offset(left, a.size(), k);
int _right = offset(right, a.size(), k);
int _center = offset(center, a.size(), k);
int min = a[_left];
int max = a[_right];
int val = a[_center];
if (val == target) {
return true;
} else if (left == right) {
return false;
} else if (val > target) {
right = center - 1;
} else if (val < target) {
left = center + 1;
}
}
}
// dump the deque
void dump(std::deque<int>&a)
{
for (unsigned int i = 0; i < a.size(); i++) {
printf("%d ", a[i]);
}
printf("\n");
}
// rotate the deque
void rotate(std::deque<int>&a, int k)
{
if (k > 0) { // shift to the left
for (int i = 0; i < k; i++) {
int b = a.front();
a.pop_front();
a.push_back(b);
}
} else { // shift to the right
for (int i = 0; i > k; i--) {
int b = a.back();
a.pop_back();
a.push_front(b);
}
}
}
int main(int argc, char **argv)
{
if (argc < 4) {
printf("usage: %s target offset [elements ...]\n", argv[0]);
return 1;
}
int target = atoi(argv[1]);
int k = atoi(argv[2]);
// unsorted elements in set will become sorted elements in deque
std::set<int>s;
for (unsigned int i = 3; i < argc; i++) {
s.insert(atoi(argv[i]));
}
std::deque<int>a;
for(std::set<int>::iterator it = s.begin(); it != s.end(); it++) {
a.push_back(*it);
}
printf("Sorted array: ");
dump(a);
rotate(a, k);
printf("Rotated array: ");
dump(a);
bool exists = binarySearch(a, target, k, 0, a.size() - 1);
printf("%d is%s in the array\n", target, exists ? "" : " NOT");
}
$ ./rotated-sorted-array 33 2 3 7 34 76 33 12
Sorted array: 3 7 12 33 34 76
Rotated array: 12 33 34 76 3 7
33 is in the array
$ ./rotated-sorted-array 31 -1 3 7 34 76 33 12
Sorted array: 3 7 12 33 34 76
Rotated array: 76 3 7 12 33 34
31 is NOT in the array
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned int charsum(char *str)
{
unsigned int x = 0;
unsigned int i;
for(i = 0; i < strlen(str); i++)
x += str[i];
return x;
}
int anagram(char *str1, char *str2)
{
return charsum(str1) == charsum(str2);
}
int main(int argc, char**argv)
{
if (argc != 3)
{
printf("usage: %s str1 str2\n");
exit(1);
}
int x = anagram(argv[1], argv[2]);
printf("%s and %s are%s anagrams.\n", argv[1], argv[2], x ? "" : " NOT");
}
$ ./anagram abcdefg bdagfce
abcdefg and bdagfce are anagrams.
$ ./anagram foo bar
foo and bar are NOT anagrams.
#include <stdio.h>
#include <stdlib.h>
#include <vector>
std::vector<unsigned int>pascal(unsigned int i)
{
if (i == 1) {
std::vector<unsigned int>v;
v.push_back(1);
return v;
}
if (i == 2) {
std::vector<unsigned int>v;
v.push_back(1);
v.push_back(1);
return v;
}
std::vector<unsigned int>p = pascal(i - 1);
std::vector<unsigned int>r;
r.push_back(1);
for (unsigned int j = 1; j < i - 1; j++) {
r.push_back(p[j - 1] + p[j]);
}
r.push_back(1);
return r;
}
int main(int argc, char **argv)
{
if (argc != 2) {
printf("usage: %s n\n", argv[0]);
exit(1);
}
unsigned int n = atoi(argv[1]);
for(unsigned int i = 1; i <= n; i++) {
std::vector<unsigned int>v = pascal(i);
for (unsigned int j = 0; j < i; j++) {
printf("%d ", v[j]);
}
printf("\n");
}
}
$ ./pascal-triangle 6
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Vector is a wrapper to std::vector with length(), get(i), and reverse(i,j)
#include <vector>
template <typename T>
class Vector
{
public:
Vector(T t[], unsigned int n) {
for(unsigned int i = 0; i < n; i++) {
v.push_back(t[i]);
}
}
size_t length() {
return v.size();
}
T get(unsigned int i) {
if (i >= length())
std::__throw_out_of_range;
return v[i];
}
void reverse(unsigned int i, unsigned int j) {
if (i == j)
return;
v[i] = get(i) ^ get(j);
v[j] = get(i) ^ get(j);
v[i] = get(i) ^ get(j);
}
protected:
std::vector<T>v;
};
void quicksort(Vector<int>&v, unsigned int left = 0, unsigned int right = 0)
{
if (right == 0 || right >= v.length() - 1)
right = v.length() - 1;
int pivot = v.get(right);
unsigned int j = left;
for (unsigned int i = left; i <= right - 1; i++) {
if (v.get(i) < pivot)
v.reverse(i, j++);
}
v.reverse(j, right);
if (left < j - 1)
quicksort(v, left, j - 1);
if (j + 1 < right)
quicksort(v, j + 1, right);
}
int main()
{
int a[] = {9, 27, 35, -8, 7, -3, 4, 12};
Vector<int>v(a, sizeof(a) / sizeof(a[0]));
quicksort(v);
for(unsigned int i = 0; i < v.length(); i++)
printf("%d ", v.get(i));
printf("\n");
}
Output:
-8 -3 4 7 9 12 27 35
Based on Eric Xu's comment:
#include <stdio.h>
#include <stdlib.h>
#include <vector>
unsigned int gcd(unsigned int a, unsigned int b)
{
while(a != 0 && b != 0)
{
if (a > b) {
a -= b;
} else {
b -= a;
}
}
return a + b;
}
unsigned int lcm(std::vector<unsigned int>&num)
{
if (num.empty())
{
printf("unable to calculate LCM for empty vector\n");
exit(1);
}
else if (num.size() == 1)
{
return num.back();
}
else
{
unsigned int a = num.back();
num.pop_back();
unsigned int b = num.back();
num.pop_back();
unsigned int x = a * b / gcd(a, b);
num.push_back(x);
return lcm(num);
}
}
int main()
{
std::vector<unsigned int>num;
num.push_back(10);
num.push_back(9);
num.push_back(15);
printf("%d\n", lcm(num));
}
<pre lang="" line="1" title="CodeMonkey68729" class="run-this">#include <stdio.h>
- leeym June 26, 2011void merge(int A[], unsigned int lA, int B[], unsigned int lB)
{
int i = 0, j = 0, k = 0;
while (k < lA) {
while (A[i] < 0)
i++;
if (i == lA)
A[k++] = B[j++];
else if (j == lB)
A[k++] = A[i++];
else if (A[i] < B[j])
A[k++] = A[i++];
else
A[k++] = B[j++];
}
}
int main()
{
int A[] = { -1, -1, 8, 19, -1, -1, -1, 31, -1, 38, 65, -1, 85, -1, -1, 110, 150, -1};
int B[] = {24, 51, 90, 130, 140, 180, 190, 220, 250, 260};
int i = 0;
merge(A, sizeof(A) / sizeof(int), B, sizeof(B) / sizeof(int));
while (i < (sizeof(A) / sizeof(int))) {
printf("[%d]", A[i]);
i++;
}
printf("\n");
}
</pre><pre title="CodeMonkey68729" input="yes">
</pre>