文档章节

LintCode刷题之路(一)

StayY
 StayY
发布于 2016/11/21 12:11
字数 463
阅读 62
收藏 0

在算法和数据结构上,我觉得我是一个彻彻底底的小白,开始刷题吧。

#阶梯训练

###1. 两个字符串是变位词

######写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

样例

给出 s = "abcd",t="dcab",返回 true.

给出 s = "ab", t = "ab", 返回 true.

给出 s = "ab", t = "ac", 返回 false.

首先看到这个题目 我们想到的就是字符串排序了,通过排序把字符调换成有顺序的字符串,再来比较。

所以就会出现以下代码

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        //先查看长度是否相等,不相等则返回false
        if(s.length() != t.length()){
            return false;
        }
        //转换成字符 然后排序
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();
        Arrays.sort(sChar);
        Arrays.sort(tChar);
        for(int i=0;i<s.length();i++){
            if(sChar[i]!=tChar[i]){
                return false;
            }
        }
        return true;
    }
};

由于以上是两个字符串之间的比较,所以就能很方便的这样用,但是如果是多个字符串数组又是怎么比较的呢,这个问题后面会有。

九章算法提供的答案是

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        if (s.length() != t.length()) {
           return false;
        }
        
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        for (int i = 0; i < t.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) {
                return false;
            }
        }
        return true;
    }
};

这个方法是用一个数组存放 把字符串中的字符用数组记录下来 先把第一个字符串的字符通过数组记录下来,数组中存在就+1,再用第二个数组的索引去减1,如果有小于0的值出现,就说明两个字符串不相等。

© 著作权归作者所有

共有 人打赏支持
StayY
粉丝 0
博文 38
码字总数 21515
作品 0
南昌
程序员
私信 提问
小米面经-技术岗(编程小白如何进阶)

先介绍下背景,我本科专业是硬件转软件方面,所以一开始算法基础比较差,没有做过系统设计,为了能得到好的面试机会,我一直都有努力准备,还在网上关注了各种能提高编程能力的攻略,我觉得打...

coderer
2017/05/08
0
0
鹅厂奋战历程简录

从开始准备到最后尘埃落定,和鹅厂总共纠缠了近10个月,所幸最终拿到Offer,也算万事完满。 2015.12 12月中旬,和一读研学长讨论今后出路。本觉得以自己的水平万不可眼界过高放眼鹅厂这种互联...

sun511230
2017/05/25
0
0
二战大众点评,斩获软件工程师 offer

先介绍一下自己,国内某985 CS专业学渣一名,高考考完刚被录取的时候,还立下了小目标说一定要去BAT,现在回过头想想……真是好有勇气啊。大学的前两年在平时翘翘课、窝在寝室里面打打游戏,...

wb596aedb820f7a
2017/07/16
0
0
快手 Android 工程师面经

看着我把简历投完之后弹出的“完成”字样,我就十分的激动了,我是一名应届毕业生,老老实实的那种,学过的知识我都一步一个脚印的复习的完了,Lintcode上该刷的题,也妥妥的完成了,但是一想...

Winnielyn
2017/07/18
0
0
【干货分享】面试小技巧

纪念一下第一份面试经历 美团面试主要就是分为笔试和面试,笔试以后我恬不知耻地去霸面了(其实也不觉得有什么恬不知耻,权当考察去了)但其实笔试完没多久后我就接到了约面试时间的电话了。...

路过全世界
2017/04/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

读取zookeeper上的dubbo注册信息

dubbo有自己的服务监听服务器,incubator-dubbo-ops-develop,github可以下载到,网上也有很多本地部署的例子,就想了下能不能自己监听dubbo的服务,于是写了如下代码。特别注意的是zookeep...

noob_chr
24分钟前
0
0
Java提高班(六)反射和动态代理(JDK Proxy和Cglib)

反射和动态代理放有一定的相关性,但单纯的说动态代理是由反射机制实现的,其实是不够全面不准确的,动态代理是一种功能行为,而它的实现方法有很多。要怎么理解以上这句话,请看下文。 一、...

王磊的博客
43分钟前
2
0
Ext grid 渲染

// 单元格字体颜色渲染function renderer_Meta_useStatus(value, cellmeta, record,rowIndex, columnIndex, store){ var color = ""; if("空闲"==value){ color = "green";......

MoksMo
53分钟前
5
0
log4j2在spring中的配置

<?xml version="1.0" encoding="UTF-8"?><!--日志级别以及优先级排序: OFF > FATAL > ERROR > WARN > INFO > DEBUG > TRACE > ALL --><!--Configuration后面的status,这个用于设置l......

TonyTaotao
58分钟前
4
0
java 中间变量缓存机制(i++,++i)

public class Test { public static void main(String[] args) { int i = 0; i = i ++ ; System.out.println(i); } } 答案是 0 如果是 i = ++......

shzwork
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部