Monthly Archives: January 2015


[leetcode] Palindrome Number

Palindrome Number Determine whether an integer is a palindrome. Do this without extra space. Some hints: Could negative integers be palindromes? (ie, -1) If you are thinking of converting the integer to string, note the restriction of using extra space. You could also try reversing an integer. However, if you […]


[leetcode] Candy

Candy There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the […]


[leetcode] Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Some examples:

tags: stack 经典题,今天刚在数据结构书上看到。维护一个栈。当遇到数字时,入栈。当遇到运算符时,弹出两个数字,进行运算,然后将结果压入栈中。栈中最后剩的数字便是结果。 需要注意的是减法和除法数字运算的顺序,后出栈的(operand1)作被减数或被除数,先出栈(operand2)的作减数或除数。 我用了一个抛异常的技巧,如果当前字符串无法转换成数字,stoi会抛出invalid_argument异常,由处理操作符的代码进行解决。 可能是抛异常的处理机制比较耗时间,我的代码运行速度竟然排在了C代码的后面。

     


[leetcode] Letter Combinations of a Phone Number

Letter Combinations of a Phone Number Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

Note: Although the above answer is in lexicographical order, your answer could be in […]


[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。

   


[leetcode] Excel Sheet Column Title

Excel Sheet Column Title Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:

Credits: Special thanks to @ifanchu for adding this problem and creating all test cases. tag: math 虽然此题被leetcode标为简单题,但感觉还是有难度的,需要脑筋急转弯,而不是考察数据结构。 此题关键在于,我们平常的计数法是0-25,但它是1-26.并且,后一位的Z表示的数的大小和前一位的A相同。 即:AZ = 1 * 26 + 26 A和Z都表示26,所以我们在做取余求各位的值时,如果余数为0,我们把它置为26,并向上一位借1,也即n–。在循环外面,如果n不等于0,我们需要把它也压入栈中,然后再把栈反转,得到最后的结果。

9/7/2015 […]


[leetcode] Regular Expression Matching

Regular Expression Matching Implement regular expression matching with support for ‘.’ and ‘*’.

tags: backtracking, dynamic programming, string 9/25/2015 update dynamic programming O(p*s*s)

  很有味道的一道题,看了tag才做出来。 考虑用递归构造一个在string域内包含全部可能的,正则表达式展开结果的树。如果展开到某一节点,发现无法匹配,则回溯。 效率很低,但我们不得不用深搜考虑所有可能的情况。估计工业上的正则表达式匹配也用的是这样的方案把。 记string长度为m,正则表达式长度为n。则最坏情况下的时间复杂度为m^n(感觉,待论证)。

   


[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 动态规划中,如果我们只要某一行的规划矩阵的值,我们每必要存下整个矩阵,因为求解某一行的矩阵的值时我们只需要上一行矩阵的值(对于本题来说),所以我们只需记录上一行矩阵的值即可。