zhoutuo’s gists

zhoutuo / Remove Duplicates from Sorted Array.cpp

Created February 15, 2013 16:44

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2].

-class Solution {
-public:
-    int removeDuplicates(int A[], int n) {
-        // Start typing your C/C++ solution below
-        // DO NOT write int main() function
-        int newLength = 0;
-        if(n == 0) {
-            return newLength;
-        }

zhoutuo / Merge k Sorted Lists.cpp

Created February 14, 2013 20:56

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	struct node {
	int index;

zhoutuo / Swap Nodes in Pairs.cpp

Created February 14, 2013 18:43

Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

zhoutuo / Generate Parentheses.cpp

Created February 13, 2013 03:25

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()"

	class Solution {
	public:
	vector<string> generateParenthesis(int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<string> result;

	calc(result, "", n, 0);

	return result;

zhoutuo / Remove Nth Node From End of List.cpp

Created February 13, 2013 02:51

Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass.

-/**
- * Definition for singly-linked list.
- * struct ListNode {
- *     int val;
- *     ListNode *next;
- *     ListNode(int x) : val(x), next(NULL) {}
- * };
- */
-class Solution {
-public:

zhoutuo / Longest Common Prefix.cpp

Created February 13, 2013 01:13

Write a function to find the longest common prefix string amongst an array of strings.

	class Solution {
	public:
	string longestCommonPrefix(vector<string> &strs) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	string prefix = "";

	if(strs.size() == 0) {
	return prefix;
	}

zhoutuo / Valid Parentheses.cpp

Created February 12, 2013 18:54

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

	class Solution {
	public:
	bool isValid(string s) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	stack<char> checker;

	for(int i = 0; i < s.length() ; ++i) {
	char cur = s[i];
	if(isLeft(cur)) {

zhoutuo / Reverse Linked List II.cpp

Last active December 12, 2015 10:19

Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

zhoutuo / Reverse Integer.cpp

Created February 11, 2013 05:48

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321

	class Solution {
	public:

	int lastDigit(int x) {
	return x % 10;
	}

	int reverse(int x) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() functio

zhoutuo / Add Two Numbers.cpp

Created February 11, 2013 02:53

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

Z.T. Yang zhoutuo