2.实现单例模式
静态内部类
class Singleton{
private Singleton(){}//私有构造方法,避免外部创建实例
private static class SingletonHolder
{
public static final Singleton instance= new Singleton();
}
public static Singleton getInstance()
{
return SingletonHolder.instance;
}
}
3.二维数组中的查找
public class FindInt {
public static boolean Find(int[][] array, int target) {
int rows = array.length;
int columns = array[0].length;
boolean found = false;
if (array != null && rows > 0 && columns > 0) {
int row = 0;
int column = columns - 1;
while (row <rows&&column>=0) {
int tempValue = array[row][column];
if (target > tempValue) {
row++;
} else if (target < tempValue) {
column--;
} else {
found = true;
break;
}
}
}
return found;
}
public static void main(String[] args) {
int [][] a = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
System.out.println(Find(a,14));
}
}
4.替换空格
先边里空格数，申请能容下的数组，用两个指针，一个在数组尾部，一个在字符串尾部，字符串尾部指针不段向前，一旦指向字符就复制字符到后面指针所在地址，遇到空格时，后面指针向前移动三格，当两个指针重合时结束。
public class Solution {
public String replaceSpace(StringBuffer str) {
for(int k=0; k<str.length(); k++) {
char index = str.charAt(k);
if(index == ' ')
str.replace(k, k+1, "%20");
}
return str.toString();
}
}
5.从尾到头打印链表
从头到尾遍历链表放入栈中。
import java.util.Stack;
class ListNode{
ListNode next=null;
int val;
ListNode(int val){
this.val=val;
}
}
public class PrintListFromTailToHead {
public static void printListFromTailToHead(ListNode listnode){
Stack<Integer> stack=new Stack<>();
while(listnode!=null){
stack.push(listnode.val);
listnode=listnode.next;
}
while(!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
}
public static void main(String[] args) {
ListNode a=new ListNode(1);
ListNode b=new ListNode(2);
ListNode c=new ListNode(3);
ListNode e=new ListNode(4);
ListNode f=new ListNode(5);
ListNode g=new ListNode(6);
a.next=b;
b.next=c;
c.next=e;
e.next=f;
f.next=g;
printListFromTailToHead(a);
}
}
7.两个栈实现队列
//两个栈实现一个队列
import java.util.Stack;
public class TwoStackQueue {
Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();
public void push(int node) {
in.push(node);
}
public int pop() throws Exception {
if (out.isEmpty())
while (!in.isEmpty())
out.push(in.pop());
if (out.isEmpty())
throw new Exception("queue is empty");
return out.pop();
}
}
9.斐波那契数列
下面方法避免了递归的重复计算
public class Fibo {
public static long fibo(int n){
if(n<=1) return n；
long FibN=0;
long Fibone=0;
long Fibtwo=1;
for(int i=2;i<=n;i++){
FibN=Fibone+Fibtwo;
Fibone=Fibtwo;
Fibtwo=FibN;
}
return FibN;
}
public static void main(String[] args) {
System.out.println(fibo(2));
}
}
10.二进制中1的个数
减1后与原整数做与运算，会把该整数最右边的一个1变成0。有多少个1就可以进行多少次操作，用count计数。
public class NumOf1 {
public static int NumOf1(int n) {
int count = 0;
while (n>0) {
count++;
n = (n-1)&n;
}
return count;
}
public static void main(String[] args) {
System.out.println(NumOf1(11));
}
}
13.在O(1)时间删除链表节点
得到要删除的节点的下一个节点，把下一个节点的内容复制到要删除的节点上覆盖原有的内容，再把下一个节点删除。就不需要遍历找该节点了。
15.查找链表倒数第K个节点
import org.junit.Test;
public class TheKthNodeFromTail {
@Test
public ListNode main(ListNode head,int k) {
ListNode listNode=head;
if(listNode==null||k<=0)
return null;
ListNode nodeA=head;
for(int i=1;i<k;i++) {
if (listNode != null) {
listNode=listNode.next;
}
else{
return null;
}
}
while(listNode.next!=null){
listNode=listNode.next;
nodeA=nodeA.next;
}
return nodeA;
}
}
16.反转链表
/*class ListNode{
ListNode next=null;
int val;
ListNode(int val){
this.val=val;
}
}*/
public class ReverseList {
public static ListNode reverselist(ListNode listNode){
ListNode Rhead=null;
ListNode now=listNode;
ListNode pre=null;
while(now!=null){
ListNode next=now.next;
if(next==null){
Rhead=now;
}
now.next=pre;
pre=now;
now=next;
}
return Rhead;
}
}
17.合并两个排序的链表
public class MergeListNode {
static ListNode Merge(ListNode head1,ListNode head2){
if(head1==null)
return head2;
if(head2==null)
return head1;
ListNode Mhead=null;
if(head1.val<head2.val){
Mhead=head1;
Mhead.next=Merge(head1.next,head2);
}
else{
Mhead=head2;
Mhead.next=Merge(head1,head2.next);
}
return Mhead;
}
public static void main(String[] args) {
ListNode a=new ListNode(1);
ListNode b=new ListNode(2);
ListNode c=new ListNode(3);
ListNode e=new ListNode(4);
ListNode f=new ListNode(5);
ListNode g=new ListNode(6);
a.next=c;
b.next=e;
c.next=f;
e.next=g;
System.out.println(Merge(a,b).val);
}
}
18.树的子结构
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
if (t == null && s == null) return true;
if (t == null || s == null) return false;
if (t.val != s.val) return false;
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}
19.二叉树的镜像
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}
25.二叉树和为某一值的路径 java
public void findPath(BinaryTreeNode root,int k){
if(root == null)
return;
Stack<Integer> stack = new Stack<Integer>();
findPath(root,k,stack);
}
public void findPath(BinaryTreeNode root,int k,Stack<Integer> path){
if(root == null)
return;
if(root.leftNode == null && root.rightNode == null){
if(root.value == k){
System.out.println("路径开始");
for(int i :path)
System.out.print(i+",");
System.out.print(root.value);
}
}
else{
path.push(root.value);
findPath(root.leftNode,k-root.value,path);
findPath(root.rightNode,k-root.value,path);
path.pop();
}
}
字符串的全排列
/**
* 参数array:给定字符串的字符数组
* 参数start:开始遍历字符与其后面各个字符将要进行交换的位置
* 参数end:字符串数组的最后一位
* 函数功能：输出字符串数字的各个字符全排列递归实现
*
*/
public class PermutationAll {
public static void main(String[] args){
String s = "abcd";
char[] array = s.toCharArray();
recursion(array,0,array.length-1);
}
public static void recursion(char[] array,int start,int end){
if(end <= 1)
return;
if(start == end){
for(int i = 0;i < array.length;i++)
System.out.print(array[i]);
System.out.println();
}
else{
for(int i = start;i <= end;i++){
swap(array,i,start);
recursion(array,start+1,end);
swap(array,i,start);
}
}
}
//交换数组m位置和n位置上的值
public static void swap(char[] array,int m,int n){
char temp = array[m];
array[m] = array[n];
array[n] = temp;
}
}
31.连续子数组最大和（动态规划）
设置两个变量，一个currentMax用来记录数组相加之和，一个sumMax用来记录最大的子数组和，一旦currentMax大于sumMax，就更新sumMax使它等于currentMax；初始值都赋予数组的第一个元素的值；
public static int maxsubarr(int[] array)
{
if(array == null || array.length == 0)
return 0;
int Max = array[0];
int preSum = array[0];//保存子数组相加之和
//从头开始遍历相加数组中的元素
for (int i = 1; i < array.length; i++)
{
//若是相加之和一旦小于零，子数组从新开始，否则相加
preSum=preSum < 0? array[i]:preSum + array[i];
//sumMax保存最大的子数组的和
Max=Math.max(Max,preSum);
}
return Max;
}
之字型打印二叉树
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/**
* Z字型打印二叉树
*/
public class PrintBintreeByZ {
@Test
public void print() {
TreeNode root=new TreeNode(1);
TreeNode b=new TreeNode(2);
TreeNode c= new TreeNode(3);
TreeNode d=new TreeNode(4);
TreeNode e=new TreeNode(5);
root.left=b;
root.right=c;
b.left=d;
c.right=e;
List<List> listall = new ArrayList<>();
Stack<TreeNode> nowStack = new Stack<>();
nowStack.push(root);
boolean flag=false;
while (!nowStack.isEmpty()) {
flag=!flag;
Stack<TreeNode> nextStack = new Stack<>();
List<Integer> listone = new ArrayList<>();
for(TreeNode node:nowStack) {
listone.add(node.val);
if (node.right != null)
nextStack.add(node.right);
if (node.left != null)
nextStack.add(node.left);
}
nowStack = nextStack;
if(flag)
Collections.reverse(listone);
listall.add(listone);
}
System.out.println(listall);
}
}
