文档章节

LintCode刷题之路(一)

StayY
 StayY
发布于 2016/11/21 12:11
字数 463
阅读 53
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

awk命令用法介绍

10月18日任务 9.6/9.7 awk 1.awk(上)(下) 1.awk 分段操作功能 指定分隔符,并把第一段打印出来,不会改动文件内容 将所有内容打印出来 awk 没有指定分隔符号,则会默认用空格或者空白字符...

hhpuppy
49分钟前
2
0
Spring Cloud Eureka Server高可用之:在线扩容

本文共 1591字,阅读大约需要 6分钟 ! 概述 业务微服务化以后,我们要求服务高可用,于是我们可以部署多个相同的服务实例,并引入负载均衡机制。而微服务注册中心作为微服务化系统的重要单元...

CodeSheep
今天
2
0
内网esxi主机上安装CoreOS虚拟机

CoreOS是一个为专门运行容器而设计的轻量级linux发行版,旨在通过轻量的系统架构和灵活的应用程序部署能力简化数据中心的维护成本和复杂度。它没有包管理工具,运行容器化应用以提供服务;默...

hiwill
今天
1
0
20181018 上课截图

![](https://oscimg.oschina.net/oscnet/49f66c08ab8c59a21a3b98889d961672f30.jpg) ![](https://oscimg.oschina.net/oscnet/a61bc2d618b403650dbd4bf68a671fabecb.jpg)......

小丑鱼00
今天
3
0
WinDbg

参考来自:http://www.cnit.net.cn/?id=225 SRV*C:\Symbols*http://msdl.microsoft.com/download/symbols ctrl + d to open dump_file Microsoft (R) Windows Debugger Version 6.12.0002.633......

xueyuse0012
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部