字符串翻转算法-JAVA

单词翻转

问题描述:

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变,句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如,输入“I am a student.”,则输出“student. a am I”。

算法分析

首先第一步反转.tneduts a ma I,然后以空格为界,逐个单词反转,最后输出student. a am I,时间复杂度O(n),空间复杂度O(1)

Java代码

/** * Created by billJiang on 2016/10/21. */
public class TestReverseString {

    public static void main(String[] args) {
        String str="I am a student.";
        char[] chars=str.toCharArray();

        //first reverse
        reverse(chars,0,chars.length-1);
        System.out.println(String.valueOf(chars));

        //second reverse
        int start=0,end;
        for (int i = 0; i <chars.length ; i++) {
            if(chars[i]==' '){
                end=i-1;
                reverse(chars,start,end);
                start=i+1;
            }else if(i==chars.length-1){
                reverse(chars,start,i);
            }
        }
        System.out.println(String.valueOf(chars));
    }

    public static void reverse(char[] chars,int start,int end){
        while(start<end){
            char temp=chars[start];
            chars[start++]=chars[end];
            chars[end--]=temp;
        }
    }
}

链表翻转

问题描述

给出一个链表和一个数k,比如,链表为1→2→3→4→5→6,
若k=2,翻转后 2→1→6→5→4→3,
若k=3,翻转后 3→2→1→6→5→4,
若k=4,翻转后 4→3→2→1→6→5,
用程序实现

算法分析

以第k-1个数字为界,拆分两部分,分别反转,时间复杂度O(n),空间复杂度O(1)

Java代码

以数组形式来表示链表

重新排序方式

import java.util.Scanner;

/** * Created by billJiang on 2016/10/20. */
public class TestLinkListReverse {
    public static void main(String[] args) {
        int[] num = {1, 2, 3, 4, 5, 6};
        System.out.println("Enter a number(1-6):");
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        if(k>num.length||k<1) {
            System.out.println("invalid number");
            return;
        }
        reverseArr(num,0,k-1);
        reverseArr(num,k,num.length-1);

        //result output
        for (int i = 0; i <num.length ; i++) {
            if(i<num.length-1)
                System.out.print(num[i]+"->");
            else
                System.out.print(num[i]);
        }

    }

    public static int[] reverseArr(int[] num,int start,int end){
        while(start<end){
            int temp=num[start];
            num[start++]=num[end];
            num[end--]=temp;
        }
        return num;
    }
}
相关文章
相关标签/搜索