Reverse Words in a String Given an input string, reverse the string word by word. For example, Given s = “the sky is blue“, return “blue is sky the“. Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space. Clarification: What constitutes a word? A sequence of […]
Power of Two Given an integer, write a function to determine if it is a power of two. //can n be negative? //negative number is definitely not a power of two //1 is power of 2 //0 is not //1 2 4 8 16 32 64 .. class Solution { […]
Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. First, I thinked out an o(n^3) force solution. It’s workable at last. However, an o(n^2) solution exists which uses a hash table to store the slope […]
Insertion Sort List Sort a linked list using insertion sort. Basic question. //Should I solve this problem in place? //Contains duplicates values? /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution […]
Binary Tree Postorder Traversal Given a binary tree, return the postorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? Use two stacks to simulate recursion. stack st stores visiting nodes, […]
Reorder List Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes’ values. For example, Given {1,2,3,4}, reorder it to {1,4,2,3}. The algorithm is straightforward. First, divide the linked list into two parts equally. (left part may be longer than […]
Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. For example, given s = “catsanddog”, dict = [“cat”, “cats”, “and”, “sand”, “dog”]. A solution is […]
Word Break Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = “leetcode”, dict = [“leet”, “code”]. Return true because “leetcode” can be segmented as “leet code”. First, I […]
Single Number II Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? This is an extremely tricky problem. First, we consider each bit of the […]
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. OJ’s undirected graph serialization:Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider […]
