一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 479|回复: 2
收起左侧

[算法题] 求大牛指点leetcode的部分题目。

[复制链接] |试试Instant~ |关注本帖
ryuichist 发表于 2015-3-10 08:26:46 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
如题,现在leetcode开始刷第一次,做了50个左右了。说实话真的很辛苦,很多时候死活想不出。
求大牛,大婶一起讨论以下的几个问题
#12, integer to roman
#13, roman to integer
#81, search in rotated sorted array,题目看不懂
#80, remove duplicated from sorted array ii,题目没看懂

希望大婶不吝赐教!!!!可以在这里讨论,也可以加我QQ 10805529,感激不尽!
askyfeng 发表于 2015-3-13 12:52:19 | 显示全部楼层
编程这个东西吧,我觉得一个是靠积累,也就是说写了很多程序之后本能地对一些算法有了了解,但是这个过程相当慢,而刷题就是加快了这个进程。但刷题说到底是属于信息输出的,很多人觉得刷题不难或者大多数题不难是因为他们本身有一定的积累。

所以如果你基础差,积累比较少的话,我建议先看一些algorithm的书,至少把积累经典的程序题弄清楚,比如dynamic,greedy,brute force, np-hard, dfs,还有一些数据结构,例如hashmap,set,tree,linkedlist,stack之类的。这些基本的搞定了,然后才能谈得上输出。

你所提的12、13题,其实都没有什么算法和数据结构在里面,你需要处理的就是枚举一些corner cases,细心一点,在纸上写清楚就可以了。这些是属于brute force的题目。

81题是binary search的变形,其实就是比binary search多几个判断。除了和mid比较,还需要增加和left或者right的比较。

80题是把超过两个的数去掉,这个去掉是指用后面的数来覆盖需要去掉的数就可以了,你不需要修改array的长度,因此,你必须输出修改后的array的长度来给出结束点。

这些其实都是比较intuitive的题,都不太涉及到算法,lz多练练就好了,没有人天生会的。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

askyfeng 发表于 2015-3-13 12:58:51 | 显示全部楼层
付上我自己的代码,可能不是最好的,仅供参考。

12. 其实这一题用switch 和StringBuilder会更快

public String intToRoman(int num) {
        if( num<1 || num>3999 )
            return "ERROR!";
            
        String[] roman = {"I", "V", "X", "L", "C", "D", "M"};
        int value = num;
        String result = "";
        
        int i = 1;
        while(value>0){
            int bit = value%10;
            if( bit == 9 )
                result = roman[2*i-2]+roman[2*i] + result;
            else if ( bit ==4 )
                result = roman[2*i-2]+roman[2*i-1] + result;
            else if (bit==5)
                result = roman[2*i-1] + result;
            else if ( bit > 0){
                for( int j=0; j<(bit%5); j++ )
                    result = roman[2*i-2] + result;
                if ( bit > 5 ){
                    result = roman[2*i-1] + result;
                }
            }
            value = value/10;
            i++;
        }
        return result;
    }

13.
public int romanToInt(String s) {
        
        HashMap<Integer, Integer> scale = new HashMap<Integer, Integer>();
        scale.put((int)'I', 1);
        scale.put((int)'V', 5);
        scale.put((int)'X', 10);
        scale.put((int)'L', 50);
        scale.put((int)'C', 100);
        scale.put((int)'D', 500);
        scale.put((int)'M', 1000);
        
        int result = 0;
        int carrier = 1;
        for( int i=s.length(); i>0 ; i-- ){
            if( i<s.length() && scale.get((int)(s.charAt(i-1)))<scale.get((int)(s.charAt(i))))
                result -= carrier*scale.get((int)(s.charAt(i-1)));
            else
                result += carrier*scale.get((int)(s.charAt(i-1)));
        }
        return result;
    }

81. 这里有duplicate,所以每次遇到duplicate的时候移位一下,知道数不一样了就好

public boolean search(int[] A, int target) {
                if( A==null || A.length==0 )
                        return false;
               
                int left = 0, right = A.length-1;
                while(left<A.length-1 && A[left]==A[left+1])
                        left++;
                while(right>left && A[right]==A[right-1])
                        right--;
                        
                return exist(A, target, left, right);
    }
       
        public boolean exist(int[] A, int target, int left, int right){
                if( left>right )
                        return false;
                if( A[left]==target || A[right]==target)
                        return true;
               
                int mid = (left+right)/2;
                if( target==A[mid] )
                        return true;
                if(  (A[left]>A[mid] && (target<A[mid] || target>A[left])) || (A[left]<target && target<A[mid]) ){
                        while( mid>left && A[mid]==A[mid-1])
                                mid--;                       
                        return exist(A, target, left+1, mid-1);
                }else{
                        while( mid<right && A[mid]==A[mid+1])
                                mid++;
                        return exist(A, target, mid+1, right-1);
                }               
        }

80. 这题就是有两个指针,一个指向当前存放的地址,一个指向当前搜索到的位置
public int removeDuplicates(int[] A) {
                if( A==null )
                        return 0;
                if( A.length<3)
                        return A.length;
               
                int res = 1;
                int pre = 1;
                for( int i=1; i<A.length; i++){
                        if( A[i]==A[i-1]){
                                pre++;
                        }else
                                pre = 1;
                       
                        if( pre<3 ){
                                A[res] = A[i];
                                res++;
                        }
                }
        
                return res;
    }
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 20:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表