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".

解题思路:

这一题其实是非常简单的，只需要将单词切分出来，然后倒序输出就行了。倒序可以直接反向遍历，或者使用一个栈结构都可以。Python中列表数据结构直接封装了倒序的函数，因此代码是非常简单的:

#!python
class Solution:
    # @param s, a string
    # @return a string
    def reverseWords(self, s):
        mys = s.strip().split()
        mys.reverse()
        return ' '.join(mys)

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:

\(["2", "1", "+", "3", " * "] -> ((2 + 1) * 3) -> 9\) \(["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6\)

解题思路:

这一题也是很简单的，就是一个基本的栈结构的应用问题，我想每一本讲到栈结构的算法书都会提到这个问题的。因为所有的操作符(operators)都是二元操作，所以可以从头到尾扫描整个输入串，如果是数字，就直接压入栈中，如果遇到操作符，就从栈中弹出两个操作数，根据当前的操作符进行运算，然后将计算结果压入栈中。最终栈中剩下的就是最终的计算结果.

Python代码如下:

#!python
class Solution:
    # @param tokens, a list of string
    # @return an integer
    def evalRPN(self, tokens):
        operators = {
                "+": lambda a,b: a+b,
                "-": lambda a,b: a-b,
                "*": lambda a,b: a*b,
                "/": lambda a,b: int(float(a)/b), 
                }

        stack = [] # use the list as a stack

        for token in tokens:
            try:
                stack.append(int(token))
            except ValueError:
                b = stack.pop(-1)
                a = stack.pop(-1)
                stacck.append(operators[token](a,b))

        return stack.pop(-1)

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.

解题思路:

这题很简单，我采用的是最笨的算法，就是遍历出所有的可能性。基本想法是遍历所有两个点的情况，分别计算形成的直线，两点确定一条直线嘛。直线可以用(k,b)来表示，其中k是斜率，b是截距.

具体代码如下所示:

#!python
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        slopes = dict()
        for i in range(len(points)):
            for j in range(len(points)):
                if i == j:
                    continue
                p = points[i]
                q = points[j]
                line = self.slope(p,q)
                if line not in slopes:
                    slopes[line] = set()
                slopes[line].add(i)
                slopes[line].add(j)
        values = [len(item) for item in slopes.values()]
        if len(values) == 0:
            return len(points)
        else:
            return max(values)

    def slope(self,p,q):
        delta_x = p.x - q.x
        delta_y = p.y - q.y
        if delta_x == 0:
            return  (None,p.x)
        else:
            k = float(delta_y) / delta_x
            b = p.y - p.x * k
            return (k,b)

Share on: Twitter ❄ Facebook ❄ Email

---

Comments

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

Comments

comments powered by Disqus

---