Daily Archives: January 30, 2015

[leetcode] Remove Duplicates from Sorted List

Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. tag: linked list 简单题,但要注意两点: 1. if 语句条件的判断顺序为从左到右,所以要把判断P为空放在左面先判断,然后再判断p->val == head->val 2. 在函数开始时,把head拷贝给re作为返回元素,head在操作中会被移动。当然,另一个好习惯是把head拷贝成p,然后操作p,最后返回head。 /** * Definition for singly-linked list. * struct ListNode […]

[leetcode] Regular Expression Matching

Regular Expression Matching Implement regular expression matching with support for ‘.’ and ‘*’. ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some […]

[leetcode] Pascal’s Triangle II

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 […]

[leetcode] Two Sum

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 […]

[leetcode] Convert Sorted List to Binary Search Tree

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 […]

[leetcode] Reverse Integer

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 […]