Skip to content

Instantly share code, notes, and snippets.

View junjiah's full-sized avatar

Junjia He junjiah

30 followers · 15 following
View GitHub Profile
@junjiah
junjiah / GasStation.java
Last active January 3, 2016 16:08
solved "Gas Station" on LeetCode http://oj.leetcode.com/problems/gas-station/
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
size = gas.length;
if (size == 0) return -1;
int src = 0, dest = 0, balance = 0;
while (true) {
if (balance + gas[dest] - cost[dest] >= 0) {
balance += gas[dest] - cost[dest];
dest = next(dest);
if (dest == src) return src;
@junjiah
junjiah / RandomListCopy.java
Last active January 3, 2016 11:09
solved "Copy List with Random Pointer" on LeetCode (one-pass AC! reminds me of copying GC) http://oj.leetcode.com/problems/copy-list-with-random-pointer/
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
@junjiah
junjiah / single_number.cpp
Created January 16, 2014 09:44
solved "Single Number" I and II on LeetCode (XOR!) http://oj.leetcode.com/problems/single-number/ *and* http://oj.leetcode.com/problems/single-number-ii/
class Solution {
public:
// single number i
int singleNumber(int A[], int n) {
int result = 0;
for (int i; i<n ;++i)
result = (result ^ A[i]);
return result;
}
@junjiah
junjiah / word_break.cpp
Last active January 3, 2016 10:49
solved "Word Break" I and II on LeetCode (DP is easy, but second part's backtracking in iterative way is a bit tricky - dirty hack on stack) http://oj.leetcode.com/problems/word-break/ *and* http://oj.leetcode.com/problems/word-break-ii/
class Solution {
public:
// word break i
bool wordBreak(string s, unordered_set<string> &dict) {
if (dict.empty()) return false;
int maxSize = max_element(dict.begin(), dict.end(), sizeComp)->size();
int wordSize = s.size();
bool *dp = new bool[wordSize+1];
// init dp array
for (int i=1; i<=wordSize; ++i) dp[i] = false;
@junjiah
junjiah / linked_list_cycle.cpp
Last active January 2, 2016 16:19
solved "Linked List Cycle" I and II on LeetCode (the algorithm of fast runner and slow runner is awesome!! and the solution to the second is even more mind-blowing :) http://oj.leetcode.com/problems/linked-list-cycle/ *and* http://oj.leetcode.com/problems/linked-list-cycle-ii/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// GREAT algorithm! inspired by that discussion forum.
@junjiah
junjiah / insertion_sort_list.cpp
Last active January 2, 2016 11:09
solved 'Insertion Sort List' on LeetCode (1 compile error then AC, not bad :-) http://oj.leetcode.com/problems/insertion-sort-list/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
@junjiah
junjiah / sort_list.cpp
Last active January 2, 2016 08:59
solved 'Sort List' on LeetCode http://oj.leetcode.com/problems/sort-list/
/* Merge Sort for linked list is very effective */
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
@junjiah
junjiah / spiral_matrix_ii.cpp
Created January 1, 2014 09:02
solved 'Spiral Matrix II ' on LeetCode http://oj.leetcode.com/problems/spiral-matrix-ii/
class Solution {
public:
enum Direction {RIGHT, LEFT, DOWN, UP};
vector<vector<int> > generateMatrix(int n) {
// init
i = 0; j = 0; matrix_size = n;
result.clear();
vector<int> v;
Direction d = RIGHT;
for (int i=0; i<n; ++i) v.push_back(0);
@junjiah
junjiah / candy.cpp
Created December 25, 2013 05:45
solved 'Candy' on LeetCode (needs sorting, thusO(n^2)) http://oj.leetcode.com/problems/candy/
class Solution {
public:
int candy(vector<int> &ratings) {
int size = (int)ratings.size();
if (size == 0 || size == 1) return size;
vector<int> indices, candies;
for (int i=0; i<size; ++i) {
indices.push_back(i);
candies.push_back(1);
}
@junjiah
junjiah / MaxPoints.java
Last active January 1, 2016 03:19
solved 'Max Points on a Line' on LeetCode (TRICK: use strings to represent lines!) http://oj.leetcode.com/problems/max-points-on-a-line/
/*
reduced code from 120 lines to 40 lines:
no need to build classes like Line and Fraction!
it's enough to
1. represent lines using only slope since point i
is fixed
2. use string as the key of hashmap
*/
public class Solution {