Archive

Tag Archives: characters

Question

Write a program to right-rotate a string by m characters. Right-rotating a string means moving m characters at the left of string to the right. Is it required the time complexity is O(n) and helper memory size is O(1). For example, right-rotate “abcdefghi” by 3 characters gives “defghiabc”.

Solution

There are 2 ways to do it. The first one is that we divide the string into 2 parts (XY). X is the part to move to the right and Y is the one moving on to the left. Reverse them in place 2 times.

XY: "abcdefghi"
R(X) R(T): "cbaihgfed"
YX: "defghiabc"

Secondly we can swap character one by one. Let p0 at position 0, p1 at position m. Swap their characters repeatedly with moving both pointer right by 1.

abcdefghij
dbcaefghij
decabfghij
defabcghij
defgbcahij
defghcabij
defghiabcj
defghijbca  <- p1 doesn't move since it reaches the end
defghijacb
defghijabc
#include <iostream>

// reverse the string between start and end
void reverse_string(char* start_pointer, char* end_pointer)
{
	while (start_pointer < end_pointer) {
		char temp_char = *start_pointer;
		*start_pointer = *end_pointer;
		*end_pointer = temp_char;
		start_pointer++;
		end_pointer--;
	}
}

// solution 1
void left_rotate_string_1(char* string_pointer, int n)
{
	if (string_pointer == NULL) return;

	int length = strlen(string_pointer);
	if (n > length || n <= 0) return;

	char* first_start_pointer = string_pointer;
	char* first_end_pointer = string_pointer + n - 1;
	char* second_start_pointer = string_pointer + n;
	char* second_end_pointer = string_pointer + length - 1;
	reverse_string(first_start_pointer, first_end_pointer);
	reverse_string(second_start_pointer, second_end_pointer);
	reverse_string(first_start_pointer, second_end_pointer);
}

// solution 2
void left_rotate_string_2(char* string_pointer, int n)
{
	if (string_pointer == NULL) return;

	int length = strlen(string_pointer);
	if (n > length || n <= 0) return;

	char* pointer_1 = string_pointer;
	char* pointer_2 = string_pointer + n;
	char* pointer_end = string_pointer + length - 1;
	while (pointer_1 != pointer_2) {
		char temp_char = *pointer_1;
		*pointer_1 = *pointer_2;
		*pointer_2 = temp_char;
		if (pointer_1 != pointer_end) pointer_1++;
		if (pointer_2 != pointer_end) pointer_2++;
	}
}

// main
int main()
{
	char string_1[] = "abcdefghij";
	left_rotate_string_1(string_1, 3);
	printf("%sn", string_1); // defghijabc

	char string_2[] = "abcdefghij";
	left_rotate_string_2(string_2, 3);
	printf("%sn", string_2); // defghijabc
}

Question

Given a function prototype: int continumax(char *output_string,char *input_string). Implement it to find the longest consecutive digits. This function must return the length of the longest digits. The found longest digits should be written to the memory location that output_string is pointing. For example, if input_string is “abcd12345ed125ss123456789”, function returns 9 and output_string becomes “123456789”.

Solution

This question must be implemented in C/C++. Just skip letters, count the length and save the head position to a temp pointer.

Sample

#include <iostream>

int continumax(char *output_string, char *input_string)
{
	int max_length = 0;
	char *max_string = new char[sizeof(input_string)];

	while (true) {

		// skip all non-digit characters
		while (*input_string != 0 && (*input_string < '0' || *input_string > '9')) input_string++;
		if (*input_string == 0) break;

		// current char is digit
		int length = 0;
		char *temp_string = input_string;
		while (*input_string!=0 && *input_string >= '0' && *input_string <= '9') {
			length++;
			input_string++;
		}

		// check if this is longer
		if (length > max_length) {
			max_length = length;
			max_string = temp_string;
		}
	}

	// write maximum string to output and add null to end.
	int i;
	for (i = 0; i < max_length; i++) output_string[i] = max_string[i];
	output_string[i] = 0;

	return max_length;
}

int main()
{
	char input[] = "abcd12345ed125ss123456789";
	char *output = new char[sizeof(input)];
	int length = continumax(output, input);
	printf("Length: %dn", length);
	printf("Output: %sn", output);
}

Version 1.0.1 Changelog

  • Fixed music pausing bug
  • Fixed bug to open now playing with no song
  • Fixed bug such that music should stop after playing the last song
  • Fixed minor bug that now playing screen will be opened when notification is clicked
  • Fixed bug that the app crashed when back is pressed during song playing
$url = &quot;http://j-jis.com/&quot;;
$html = file_get_contents($url);
$html = preg_replace(&quot;/rn|n|t/&quot;, &quot;&quot;, $html); //remove unwanted characters
$html = iconv(&quot;Shift_JIS&quot;,&quot;UTF-8&quot;,$html); //convert encoding
echo $html;

Usually while we extract information from other websites, character encoding might not correct. For example, j-jis.com is encoded with Shift-JIS. Therefore if your MySQL charset is UTF-8, it causes incorrect information. To handle the changing of character encoding, we can use iconv in PHP.

$url = "http://j-jis.com/";
$html = file_get_contents($url);
$html = preg_replace("/rn|n|t/", "", $html); //remove unwanted characters
$html = iconv("Shift_JIS","UTF-8",$html); //convert encoding
echo $html;

Json has been an efficient way to handle information and message exchanges in web programming. For example, I usually use PHP to connect MySQL and retrieve information, then display as Json. So a webpage can “AJAX” the displayed Json to create a dynamic view on itself. However, while the information involves unicode characters, PHP turn them into unreadable codes. After google, I found the following is the best way to solve the problem.

$string = '你好嗎';
echo json_encode($string); //Output "u4f60u597du55ce"
echo preg_replace("#u([0-9a-f]+)#ie", "iconv('UCS-2', 'UTF-8', pack('H4', '1'))", json_encode($string)); // Output "你好嗎"

Thank you if you are using my extension. I am happy that so many people like my program. This is one of the most satisfying program I ever made. And also thank you those people on the internet who help me debug and give me suggestions. I like coding and I am also a perfectionism. I want my productions to be enhanced and improved with my greatest effort. This extension is originally called “Mail Checker (Gmail, Yahoo and Hotmail): Nicholas Workshop”. However google only allow 45 characters. T^T

Please note that i can’t make gmail checking on the popup windows as Google doesn’t allow it. And Yahoo Mail is quite unstable (after I access it will this extension millions times).Chrome cannot shrink the popup when the things inside is shrink. This is chrome’s problem I think.

Mail Checker: Nicholas Workshop
https://chrome.google.com/extensions/detail/bbpkoieffbjgocamogehnbghcpbpkcco
I know it has bugs, just tell me if you find any XD.
Please give comments.

%d bloggers like this: