Skip to content

Instantly share code, notes, and snippets.

View zhoutuo's full-sized avatar

Z.T. Yang zhoutuo

7 followers · 0 following
View GitHub Profile
@zhoutuo
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
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
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
zhoutuo / Divide two integers.cpp
Created February 16, 2013 00:19
Divide two integers without using multiplication, division and mod operator.
//
// main.cpp
// Divide_Two_Integers
//
// Created by Zhoutuo Yang on 2/15/13.
// Copyright (c) 2013 Zhoutuo Yang. All rights reserved.
//
#include <iostream>
using namespace std;
@zhoutuo
zhoutuo / Plus One.cpp
Created February 16, 2013 22:13
Given a number represented as an array of digits, plus one to the number.
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for(int i = 0; i < digits.size() / 2; ++i) {
swap(digits[i], digits[digits.size() - i - 1]);
}
@zhoutuo
zhoutuo / Merge Two Sorted Lists.cpp
Created February 16, 2013 22:26
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
@zhoutuo
zhoutuo / Next Permutation.cpp
Last active December 13, 2015 22:08
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left…
class Solution {
public:
void nextPermutation(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
bool found = false;
int left = -1;
int right = num.size();
for(int i = num.size() - 1; i >= 0; --i) {
int cur = num[i];
@zhoutuo
zhoutuo / Search insert position.cpp
Created February 19, 2013 00:00
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0
class Solution {
public:
int searchInsert(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int low = 0;
int high = n;
while(low < high) {
int middle = low + (high - low) / 2;
if(A[middle] == target) {
@zhoutuo
zhoutuo / Search for a Range.cpp
Created February 19, 2013 01:40
Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int low = low_bound(A, n, target);
int high = high_bound(A, n, target);
@zhoutuo
zhoutuo / Combination sum.cpp
Created February 19, 2013 06:22
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending orde…
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(candidates.begin(), candidates.end());
vector<int> curResult;
vector<vector<int> > results;
solve(candidates, target, results, 0, curResult);
return results;