文档章节

[java实现]常见算法之字符串操作

o
 osc_gu9d45li
发布于 2019/04/09 19:54
字数 1099
阅读 12
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

一、字符串反转

把一个句子中的打次进行反转,比如“how are you” ,变为 “you are how”

// 字符串反转
public class StringTest {

    // 字符反转的方法
    private void swap(char[] c, int front, int end) {

        if (front > end || end >= c.length) {
            return;
        }

        while (front < end) {

            char tmp = c[front];
            c[front] = c[end];
            c[end] = tmp;

            front++;
            end--;
        }
    }

    // O(n)
    public String swapStr(String str) {

        char[] cArr = str.toCharArray();

        // 整个字符串的字符反转
        swap(cArr, 0, cArr.length - 1); // 反转整个字符串中的所有字母,how are you -> uoy era woh

        int begin = 0;

        // 对字符串中的每个单词反转,除了最后一单词
        for (int i = 0; i < cArr.length; i++) {

            if (cArr[i] == ' ') {
                swap(cArr, begin, i - 1);
                begin = i + 1;
            }
        }

        // 最后一个单词的反转
        swap(cArr, begin, cArr.length - 1);

        return new String(cArr);
    }

    public static void main(String[] args) {

        String str = "how are you";
        System.out.println(new StringTest().swapStr(str));
    }

}
View Code

 

二、判断字符串是否由相同的字符组成

判断连个字符串的字母个字母的个数是否一样,顺序可以不同, 如“aaaabc” 和“cbaaaa”是相同的

// 判断字符串是否由相同的字符组成
public class StringTest {

    // 方法一 可以死任意字符      O(nlogn)
    public boolean compareStr(String str1, String str2) {

        byte[] bs1 = str1.getBytes();
        byte[] bs2 = str2.getBytes();

        Arrays.sort(bs1);
        Arrays.sort(bs2);

        str1 = new String(bs1);
        str2 = new String(bs2);

        if (str1.equals(str2)) {
            return true;
        } else {
            return false;
        }
    }

    // 只能是ASCII码  方法二  O(n)
    public boolean compareStr2(String str1, String str2) {

        byte[] bs1 = str1.getBytes();
        byte[] bs2 = str2.getBytes();

        int bCount[] = new int[256];

        for (int i = 0; i < bs1.length; i++)
            bCount[bs1[i] ]++;
        for (int i = 0; i < bs2.length; i++)
            bCount[bs2[i] ]--;
        for (int i = 0; i < 256; i++) {

            if (bCount[i] != 0) {
                return false;
            }

        }
        return true;

    }

    public static void main(String[] args) {

        String str1 = "aaaabbc";
        String str2 = "cbaaaab";

        System.out.println(new StringTest().compareStr2(str1, str2));

    }

}
View Code

 

三、字符串中单词的统计

给定一段空格分开的字符串,判断单词的个数

// 字符串中单词的统计
public class StringTest {

    // O(n)
    public int wordCount(String str) {

        int word = 0;
        int count = 0;
        for (int i = 0; i < str.length(); i++) {

            if (str.charAt(i) == ' ')
                word = 0;
            else if (word == 0 ) {
                word = 1;
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {

        String str = "i am a good boy";

        System.out.println(new StringTest().wordCount(str));

    }

}
View Code

 

四、删除字符串中重复的字符

删除字符串中国重复的字符。如good -> god

// 删除字符串中重复的字符
public class StringTest {

    // O(n^2)
    public String removeDuplicate(String str) {

        char[] cs = str.toCharArray();
        int n = cs.length;

        for (int i = 0; i < n; i++) {

            if (cs[i] == '\0')
                continue;

            for (int j = i + 1; j < n; j++) {

                if (cs[j] == '\0')
                    continue;
                if (cs[i] == cs[j])
                    cs[j] = '\0';
            }
        }

        int be = 0;
        for (int i = 0; i < n; i++) {
            if (cs[i] != '\0')
                cs[be++] =cs[i];
        }
        
        return new String(cs, 0, be);
    }

    // 方法二: O(n)
    public String removeDuplicate2(String str) {

        char[] cs = str.toCharArray();
        int n = cs.length;
        
        int count[] = new int[256];
        for (int i = 0; i < cs.length; i++) {
            if (count[cs[i]] != 0)
                cs[i] = '\0';
            count[cs[i]]++;
        }

        int be = 0;
        for (int i = 0; i < n; i++) {
            if (cs[i] != '\0')
                cs[be++] = cs[i];
        }

        return new String(cs, 0, be);
    }

    public static void main(String[] args) {

        String str = "aaaabbc";

        System.out.println(new StringTest().removeDuplicate(str));

    }

}
View Code

 

五、按要求打印给定数组的排列情况

如1,2,2,3,4,5,要求第四位不为4,3和5不能相连

// 按要求打印数组的排列情况
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class StringTest {

    boolean visited[];
    String combination = "";
    int graph[][] = null;

    public void getAllCombination(int arr[]) {

        int n = arr.length;
        graph = new int[n][n];
        visited = new boolean[n];

        buildGraph(arr, graph);

        Set<String> set = new HashSet<>();

        for (int i = 0; i < n; i++) {
            depthFirstSearch(i, set, arr);
        }

        Iterator<String> iterator = set.iterator();

        while (iterator.hasNext()) {
            String string = (String) iterator.next();
            System.out.println(string);
        }
    }

    /**
     * 按照深度优先遍历 图,将符合要求的组合加入到set中,自动去重
     * 
     * @param start
     * @param set
     * @param arr
     */
    private void depthFirstSearch(int start, Set<String> set, int arr[]) {
        visited[start] = true;
        combination += arr[start];

        if (combination.length() == arr.length) {
            if (combination.indexOf("4") != 2) {
                set.add(combination);
            }
        }

        for (int j = 0; j < arr.length; j++) {
            if (graph[start][j] == 1 && visited[j] == false)
                depthFirstSearch(j, set, arr);
        }

        // 什么意思?
        combination = combination.substring(0, combination.length() - 1);
        visited[start] = false;
    }

    /**
     * 根据传入的数构建一个图,图中的 3,5 不能相连
     * 
     * @param arr
     * @param graph
     * @return
     */
    private int[][] buildGraph(int arr[], int[][] graph) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] == arr[j])
                    graph[i][j] = 0;
                else
                    graph[i][j] = 1;
            }
        }

        graph[3][5] = 0;
        graph[5][3] = 0;

        return graph;
    }

    public static void main(String[] args) {

        int arr[] = { 1, 2, 2, 3, 4, 5 };
        new StringTest().getAllCombination(arr);

    }

}
View Code

 

六、输出字符串的所有组合

给定一个字符串,输出该字符串中字符的所有组合

// 输出字符串的所有组合

public class StringTest {

    public void combineRecursive(char[] c, int begin, int len, StringBuffer sb) {

        if (len == 0) {
            System.out.print(sb + " ");
            return;
        }

        if (begin == c.length)
            return;
        sb.append(c[begin]);
        combineRecursive(c, begin + 1, len - 1, sb);
        sb.deleteCharAt(sb.length() - 1);
        combineRecursive(c, begin + 1, len, sb);

    }

    public static void main(String[] args) {

        String s = "abc";
        char[] cs = s.toCharArray();
        StringBuffer sb = new StringBuffer();

        for (int j = 1; j < cs.length; j++) {
            new StringTest().combineRecursive(cs, 0, j, sb);
        }
    }

}
View Code
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Netty那点事(三)Channel与Pipeline

Channel是理解和使用Netty的核心。Channel的涉及内容较多,这里我使用由浅入深的介绍方法。在这篇文章中,我们主要介绍Channel部分中Pipeline实现机制。为了避免枯燥,借用一下《盗梦空间》的...

黄亿华
2013/11/24
2W
22
访问安全控制解决方案

本文是《轻量级 Java Web 框架架构设计》的系列博文。 今天想和大家简单的分享一下,在 Smart 中是如何做到访问安全控制的。也就是说,当没有登录或 Session 过期时所做的操作,会自动退回到...

黄勇
2013/11/03
3.5K
8
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
4.2K
3
Flappy Bird(安卓版)逆向分析(一)

更改每过一关的增长分数 反编译的步骤就不介绍了,我们直接来看反编译得到的文件夹 方法1:在smali目录下,我们看到org/andengine/,可以知晓游戏是由andengine引擎开发的。打开/res/raw/at...

enimey
2014/03/04
6.1K
18
浅入浅出Android(003):使用TextView类构造文本控件

基础: TextView是无法供编辑的。 当我们新建一个项目MyTextView时候,默认的布局(/res/layout/activity_main.xml)中已经有了一个TextView: <TextView 运行效果如下: 修改其文本内容...

樂天
2014/03/22
679
1

没有更多内容

加载失败,请刷新页面

加载更多

SQL 语句大全

点击上方“掌上编程”,选择“置顶或者星标” 优质文章第一时间送达! 一、基础 「1、说明:创建数据库」 CREATE DATABASE database-name    「2、说明:删除数据库」 drop database ...

GeneralMa
昨天
0
0
山东创睦网络科技有限公司:使用Python爬取全球新冠肺炎疫情数据

使用Python爬取全球新冠肺炎疫情数据 导入所需库包 获取实时数据的url 正式编写程序 查看输出结果 导入所需库包 在获取数据之前,我们需要先安装好所需的包requests和pandas: 1.如果是使用p...

osc_qv1fwke0
11分钟前
0
0
如何1年获得别人3年的工作经验(深度好文)

最近有同学问我,为什么你的工作年限不长,技术却这么厉害,我笑了笑,啥也没说。 我不是不想回答,是不知道怎么回答。在他们的定位可能就是,每方面都懂一点,遇到问题能够快速解决,就是比...

zhang_rick
今天
0
0
新基建带动行业

什么是“新基建”? 什么是“新基建”? 根据央视发布的信息来看,其涵盖了5G基站建设、新能源汽车充电桩、大数据中心、人工智能、工业互联网,特高压,城际以及城轨交通,涉及了七大领域和相...

osc_anefoz50
11分钟前
0
0
怕入错行?这群技术人写了本“择业指南”

计算机专业好找工作吗?哪些方向是当前的主流和热门方向呢? 计算机专业的你是不是还在为职业发展纠结犹豫呢? 刚经历完高考选专业的你是不是还在迷茫徘徊呢? 那么福利来啦! 《软件技术职业...

阿里云云栖号
11分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部