Pascal’s Triangle II Given an index k, return the kth row of the Pascal’s triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space? tags: array 动态规划中，如果我们只要某一行的规划矩阵的值，我们每必要存下整个矩阵，因为求解某一行的矩阵的值时我们只需要上一行矩阵的值（对于本题来说），所以我们只需记录上一行矩阵的值即可。 class Solution { public: vector<int> getRow(int rowIndex) { vector<int> row; row.push_back(1); if(rowIndex […]
Two Sum Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned […]
3Sum Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, […]
Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. tags: depth-first-search, linked list 版本一，每次取链表的中点作为root，左右分别递归调用。 我为了方便通过index取ListNode，便把list复制成了ector，却报出内存超出限额错误。尝试改进，不加vector，用时间换空间的方法。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int […]
Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. tag: string 9/23/2015 update Same algorithm as described as follows, but neater I think. class Solution { […]
Reverse Integer Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 click to show spoilers. Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this! If the integer’s […]
Min Stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) — Push element x onto stack. pop() — Removes the element on top of the stack. top() — Get the top element. getMin() — Retrieve the minimum element in the stack. […]
Binary Tree Preorder Traversal Given a binary tree, return the preorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? tag: stack 不能再简单的题了，先序遍历。 即使说不让用递归，也可以很好的解出来。做此题时需要知道一个思想，递归的本质其实就是进程内存中维护着一个栈。这在计算机系统概论，也就是Patt上的那门课上，他着重解释过。所以如果不让我们用递归的话，那就加个栈吧！ 为了比较速度，我把两种方法都贴上。应该是使用栈的方法更快。 版本一：使用递归 /** * Definition for binary […]
Pascal’s Triangle Given numRows, generate the first numRows of Pascal’s triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] tag: array 没什么算法技巧，了解帕斯卡三角的计算公式就好。不过也算是动态规划的一种吧。 1. A[i][j] = A[i – 1][j – 1] + A[i – 1][j] 2. A[i][1] = A[i][end] = 1 线性时间复杂度，常数空间复杂度。 class Solution { […]
Single Number Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? tag: hash table, bit manipulation 异或有一个很神奇的属性，可以把奇数个元素挑出来。本质是因为： 1. 异或具有交换性 A^B = B^A 2. 0与一个数异或等于它本身 所以该数列中，可以看成把出现两次的元素交换在临近位置，异或之后为0，最后剩下0与出现一次的元素异或，为该元素本身。 一次AC。 […]
