加载中…
个人资料
peking2
peking2
  • 博客等级:
  • 博客积分:0
  • 博客访问:186,238
  • 关注人气:160
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
个人简介
算法爱好者
分类
访客
加载中…
好友
加载中…
评论
加载中…
留言
加载中…
博文
(2013-10-22 14:50)
标签:

it

此站已关闭
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
看到有人问这道题的iterative解法,今天做了一下。我没有用stack,我是用queue来解的。

class Element{
    String str;
    int left;
    int right;
    
    public Element(String s, int l, int r){
        str=s;
        left=l;
        right=r;
    }
}

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> al=new ArrayList<String>();
        
        Queue<Element> q=new LinkedList<Element>();
        q.add(new Element('',0,0));
        wh
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
先总结一下
  • 设计模式的三个准则:中意与组合而不是继承, 依赖于接口而不是实现,高内聚低耦合
  • 设计模式分为creational, structural, behavioral。
  • GoF设计模式要解决的问题不少都是因为OO不承认全局变量和函数造成的。
  • GoF设计模式很多都是因为假设不能改变已有代码造成的,因此很多其实可以用refactoring的办法来解决。
  • GoF设计模式有一些本身就是反OO的,比如Singleton, Visitor。
  • GoF设计模式很多都是over design,考虑了太多的未来变化,因此设计变的非常复杂。这个与Ruby的设计准则'You Ain't Gonna Need It' 是相违背的。

下面是走马观花
  1. Strategy: OO不承认函数造成的
  2. Decrator: 就是平时常常提到的wrapper, 也属于中意与组合而不是继承
  3. Factory: 感觉是纯OO的东西。Factory method有两种,一种是effective Java里谈的,一种是GoF里谈的,我觉得都属于design pattern的范畴,但是要注意区分。因为平时所说的DP一般指GoF,但是我感觉前者可能更常用,所以这个比较容易confused。面试比较容易考到,感觉应该跟面试官说清
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
我觉得如果要解决我提到的几个迷惑就一定要把DP分层来理解。我把它分为三层,general DP, GoF DP (or OO DP), Java DP (or language specific DP)。我用Java DP是想更好的解释为什么Java如此重视DP的问题。

General DP:
什么是design pattern? 按照wiki的定义, design pattern is a general reusable solution to a commonly occurring problem within a given context in software design。基本的意思就是软件开
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
对于问题,为什么Java如此重视design pattern?我在学习DP之前的感觉是由Java的先天缺陷造成的。十几年前学Java的时候,没有吸引我的主要原因就是这门语言太死板,不够灵活。而我在后来学C#的时候则感觉很对胃口,简单而不失灵活性。那么我在学习DP的时候在wiki上看到了这句话,从而给我的感觉找到了一定的依据。
The design patterns may just be a sign of some missing features of a given programming language (Java or C++ for instance).

我们知道有三种编程方式,面向过程,面向对象和面向函数,那么我就拿我比较熟悉的C, Java, Scala作为三种编程方式的代表来说明一些问题。因为水平有限,理解不一定正确,但是我主要是给自己解惑产生的思考,能不能解你们
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
最早正式听说design pattern是以前的一个mentor建议我学习一下C++ design pattern,不过我没学。后来在CC150上第一次接触到design pattern了,但是也没仔细看。再后来在工作中亲眼见到了DP的Java代码,被狠狠的恶心了一下,因此对DP产生了不良印象。
 
一直觉得DP是OO里面的东西,但是又被某大神指出来DP跟OO半毛钱关系也没有,以为自己以前理解错了。最近大家在讨论王垠那篇关于DP的博客文章,又有大牛指出DP就是OO的东西就更糊涂了,因此感觉是应该看一下DP了,因为积攒的疑惑太多了。
所以我学习的出发点是解惑,主要是以下几个疑惑:
  1. 为什么有人说DP跟OO半毛钱关系也没有?
  2. 为什么有人说DP就是OO的东西?
  3. 为什么Java如此重视DP?

我主要看了《Design Patterns for Dummies》这本书,觉得可能会简单些,没有看经典的GoF。不过我感觉能明白意思就可以了,有时候结合wiki来理解。书还没看完,不过感觉可以先写点东西了,然后一边看一边写。现在就从CC150开始吧。

CC150第五版,第八章
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
今天做了做这道题,感觉有点意思。本身思路很简单,就是最短路径问题,因此可以用BFS+backtrack来解决,但是里边的细节比较多,写的时候要小心一些。

import collection.mutable.{Map, Queue}


object Solution {

    def main(args: Array[String]) {

        val Array(n,k)=readLine.split(' ').map(_.toInt)

        val start=readLine.split(' ').map(_.toInt-1).mkString(' ') //pegs and discs start from 0

        val end=readLine.split(' ').map(_.toInt-1).mkString(' ')

        

        val queu

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
这题我前不久在博客里做过(http://blog.sina.com.cn/s/blog_b9285de20101iwqt.html)。我博客里那题也就是Palindrome Partitioning II。

Leetcode这题算是原题的一个变形。我觉得一般有三种变形,解法各有不同。
1. 最后结果是一个整数,比如Palindrome Partitioning II。这个用DP来解
2. 最后求一个结果,比如最小切法。这个用DP+backtrack来解
3. 求所有的结果。这个一般用DFS来解。

Leetcode的这个变形属于第三种。我知道很多时候Leetcode都对DFS有一定的限制,使得DFS很难通过OJ。不过这题比较宽松,用没有任何优化的DFS也可以通过。(关于判断是不是Palindrome的优化,我的原帖有说明)

这题难度设为3,因为基本DFS可解。频率设为4,因为是典型的DFS。
II的难度设为4,因为两个DP混在一起了,频率设为3。

public class Solution {
   
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
在北美访问新浪博客非常不稳定,很多时候连不上,或者速度很慢。有网友找到一个好办法。
  1. Google http://blog.sina.com.cn/leetcode
  2. Click 'Translate this page'
  3. Select from 'Chinese' to 'Chinese'
  4. Click 'Translation'
You will be able to view all articles.


阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2013-03-01 13:15)
这题去年有大牛去Google面试碰到过,不过当时我连一维的都没做过,因此就不了了之了。这两天有人面Google又碰到了,因此就做了一下。

基本思路:用两个数据结构
1. visited matrix 表明已经用过的cell
2. PriorityQueue放目前的边界
PQ总是弹出最低的cell。得到最低的cell以后找没有访问过的邻居。如果邻居小的话,就可以装水了。把邻居放入PQ中作为新的边界(如果邻居低的话,用当前height代替邻居的高度)。这样一直到PQ为空。复杂度N*N*logN, 程序不是很复杂。

class waterContainer{

    p

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
  

新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有