java简单算法总结

1、翻转字符串

function reverseString(str) {
    return str.split('').reverse().join('');
}
reverseString("hello");

2、阶乘算法

public static int factorialize(int num) {
    if (num <= 1) {
        return 1;
    } else {
        return num * factorialize(num-1);
    }

}

public static void main(String[] args) {
    System.out.println(factorialize(5));
}

3、回文算法

一、回文数

题目描述

判断一个正整数是不是回文数。 回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。

样例

11, 121, 1, 12321 这些是回文数。 23, 32, 1232 这些不是回文数。

解法

依次对num取余，采用临时参数reverse 记录转化后的数字，最后对比reverse与num是否相等即可

public boolean palindromeNumber(int num) {
        
       int reverse = 0,temp = num;
       while(temp>0){
       //  temp%10 取余 temp/10 取整
           reverse = reverse*10+temp%10;
           temp = temp/10;
       }
       return reverse==num;
    }

二、回文字符串

题目描述

给定一个字符串，判断其是否为一个回文串。只包含字母和数字，忽略大小写。 ###样例 "A man, a plan, a canal: Panama" 是一个回文。 "race a car" 不是一个回文。 ###解法 1、根据题目描述，只包含字母和数字，需要踢除空格，标点符号等特殊符号，并且统一需要将字符串转为大写或者小写

踢除空格，标点符号等特殊符号：我采用正则表达式：

s=s.replaceAll("\pP|\pS|\pZ", "")

说明： Unicode 编码并不只是为某个字符简单定义了一个编码，而且还将其进行了归类。 /pP 其中的小写 p 是 property 的意思，表示 Unicode 属性，用于 Unicode 正表达式的前缀。 大写 P 表示 Unicode 字符集七个字符属性之一：标点字符。 其他六个是 L：字母； M：标记符号（一般不会单独出现）； Z：分隔符（比如空格、换行等）； S：符号（比如数学符号、货币符号等）； N：数字（比如阿拉伯数字、罗马数字等）； C：其他字符

2、回文的定义是一个字符串顺着读和反着读都是一样的字符串，解法有很多，我这里提供一种 将字符串转为数组，记录头地址front和尾地址end，向中间扫描，front>end，结束扫描。

public boolean isPalindrome(String s) {
        if (s == null) {
            return false;
        }
        s = s.replaceAll("\pP|\pS|\pZ", "").toLowerCase();
        char[] arr = s.toCharArray();
        int front = 0, end = arr.length - 1;
        while (front < end) {
            if (arr[front++] != arr[end--]) {
                return false;
            }
        }
        return true;
    }

三、回文链表

题目描述

设计一种方式检查一个链表是否为回文链表 ###样例 1->2->1 就是一个回文链表。

解法

解法我这里有两中思路，一种是把整个链表反转，逐个比较，这个可能性能偏差，一种是找到链表的中间位置，反转中间节点之后的链表，然后和整个链表对比，如果 中间位置的链表到结尾了，说明该链表是回文链表，第一种相对比较简单，我这里提供第二种解法

/**
 * 定义链表类
 **/
 class ListNode{
		int val;
		ListNode next;
		ListNode(int x){
			val = x;
		}
	}
	/**
     * @param head a ListNode
     * @return a boolean
     */
    public boolean isPalindrome(ListNode head) {
   
        if(head==null){
    		return true;
    	}
    	//找到中间节点
    	ListNode middle = findMiddle(head);
    	//对中间节点之后的节点进行反转，重新赋值给middle链表，
    	middle= reverse(middle.next);
    	//两个链表的长度不一样，但是middle的节点比较少，也就是middle会先结束循环，如果middle.next还有节点就跳出循环，说明该链表不是回文链表，反之是回文链表。
    	while(head!=null&&middle!=null&&head.val==middle.val){
    		head = head.next;
    		middle = middle.next;
    	}
    	return middle==null;
    }
     // 找到两个链表的中间节点
     //当链表长度为奇数时，slow刚好是链表中间节点。fast在最后一个节点 。当链表长度为偶数时，slow的节点刚好到中间节点的前一个节点。fast在倒数第二个节点。slow.next就是下一个链表的头结点。
     public  ListNode findMiddle(ListNode head){
    	if(head==null){
    		return null;
    	}
    	ListNode slow = head,fast = head.next;
    	while(fast!=null&&fast.next!=null){
    		slow = slow.next;
    		fast = fast.next.next;
    	}
    	return slow;
    }
    //反转链表
    public  ListNode reverse(ListNode head){
    	ListNode prev = null,temp = null;
    	while(head!=null){
    		temp = head.next;
    		head.next = prev;
    		prev = head;
    		head = temp;
    	}
    	
    	return prev;
    }

花了好几个小时，终于写完了，撸起袖子就是干！