0%

题目

原题页面:https://leetcode.com/problems/string-to-integer-atoi/
本文地址:</string-to-integer-atoi/>
题目类型:Easy
难度评价:Math, String
类似题目:(E) Reverse Integer, (H) Valid Number

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes:
It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char *</code> argument, please click the reload button to reset your code definition.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

阅读全文 »

题目

原题页面:https://leetcode.com/problems/validate-binary-search-tree/
本文地址:</validate-binary-search-tree/>
题目类型:Medium
难度评价:Tree, Depth-first Search
类似题目:(M) Binary Tree Inorder Traversal

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means?

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

阅读全文 »

Question

I’ve always wondered this - why can’t you declare variables after a case label in a switch statement? In C++ you can declare variables pretty much anywhere (and declaring them close to first use is obviously a good thing) but the following still won’t work:

1
2
3
4
5
6
7
8
9
10
switch (val)
{
case VAL:
// This won't work
int newVal = 42;
break;
case ANOTHER_VAL:
...
break;
}

The above gives me the following error (MSC):

initialization of ‘newVal’ is skipped by ‘case’ label

This seems to be a limitation in other languages too. Why is this such a problem?

阅读全文 »

题目

原题页面:https://leetcode.com/problems/decode-ways/
本文地址:</decode-ways/>
题目类型:Dynamic Programming, String
难度评价:Medium

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12",
it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

阅读全文 »

题目

原题页面:https://leetcode.com/problems/wildcard-matching/
本文地址:</wildcard-matching/>
题目类型:Dynamic Programming, Backtracking, Greedy, String
难度评价:Hard
类似题目: (H) Regular Expression Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the **entire** input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
阅读全文 »

题目

原题页面:https://leetcode.com/problems/regular-expression-matching/
本文地址:</regular-expression-matching/>
题目类型:Dynamic Programming, Backtracking, String
难度评价:Hard
类似题目:(H) Wildcard 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 examples:
isMatch(“aa”,“a”) → false
isMatch(“aa”,“aa”) → true
isMatch(“aaa”,“aa”) → false
isMatch(“aa”, “a*”) → true
isMatch(“aa”, “.") → true
isMatch(“ab”, ".
”) → true
isMatch(“aab”, “cab”) → true

阅读全文 »

题目

原题页面:https://leetcode.com/problems/remove-element/
本文地址:</remove-element/>
题目类型:Array, Two Pointers
难度评价:Easy
类似题目:(E) Remove Linked List Elements, (E) Move Zeroes

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

阅读全文 »

题目

原题页面:https://leetcode.com/problems/permutations/
本文地址:</permutations/>
题目类型:Backtracking
难度评价:Medium
类似题目:(M) Next Permutation, (M) Permutations II, (M) Permutation Sequence, (M) Combinations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

阅读全文 »

题目

原题页面:https://leetcode.com/problems/lru-cache/
本文地址:</lru-cache/>
题目类型:Design
难度评价:Hard

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

阅读全文 »

题目

原题页面:https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
本文地址:</best-time-to-buy-and-sell-stock/>
题目类型:Array Dynamic Programming
难度评价:Medium

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

阅读全文 »