Bulldozer_code

Bulldozer_code二维数组中的查找题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序

剑指Offer 刷题代码:

  1. 二维数组中的查找
    题目描述
    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
    在这里插入图片描述
    思路:从右上角开始查找,作比较 是返回 ,小了row++ ,大了 col–
    Java:
public boolean Find(int target, int [][] array) {
        int row = 0;
        int col = array[0].length -1;
        while(row<array.length && col>= 0) {
        	if (array[row][col]==target) {
				return true;
			}
        	else if (array[row][col]<target) {
				row++;
			}
        	else {
				col--;
			}
        }
        return false;
    }

2.替换空格
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路: 新建一个newstr 判断当前 str 中位置是不是空格 不是append 进 newstr,是 append %20

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer newstr = new StringBuffer();
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i)!=' ')
                newstr.append(str.charAt(i));
            else
                newstr.append("%20");
            
        }
        return newstr.toString();
    }
}

3.数值的整数次方
  给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方

public class Solution {
    public double Power(double base, int exponent) {
		//本题注意的是exponent小于0 或者 等于 0 的情况 还有base为0的情况
        double result = 1;
	    if(exponent < 0){
	    	base = 1/base;
	    	exponent = (-1) * exponent;
	    	for (int i = 1; i <= exponent; i++) {
				result = result *base;
			}
	    }
	    else{
		    for (int i = 1; i <= exponent; i++) {
				result = result *base;
			}
	    }
		return result;
  }
}
public class Solution {
	//时间复杂度O(n)
	public double Power(double base, int exponent) {
		int n = Math.abs(exponent);
		if (n == 0)
			return 1;
		if (n == 1)
			return base;
		//以上两个if判断可省。for循环中判断
		double result = 1.0;
		for (int i = 0; i < n; i++) {
			result *= base;
		}
		if (exponent < 0) {
			result = 1 / result;
		}
		return result;
	}
}

4.二进制中1的个数
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示.
思路:最简单的思路,整数n每次进行无符号右移一位,同1做&运算,可以判断最后以为是否为1。n&(n-1) 操作相当于把二进制表示中最右边的1变成0。所以只需要看看进行了多少次这样的操作即可。看看什么时候n为0.
0110&0101 -> count=1,n=0100 & 0011 -> n=0000 count=2

public class Solution {
    public int NumberOf1(int n) {
     int count =0;
     while(n!=0){
         n=n&(n-1);
         count++;
     }
        return count;
    }
}

5.从头到尾打印链表
题目描述:
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
代码:

 //新建一个 ArrayList 对象 判断节点是不是空,然后添加节点。反转
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> addressArrayList =new ArrayList<Integer>();
        if(listNode == null){
            ArrayList first =new ArrayList();
            return first;
        }
        while(listNode != null){
            addressArrayList.add(listNode.val); 
            listNode =listNode.next;
        }
        Collections.reverse(addressArrayList);
        return addressArrayList;
            
        
    }
}
//利用堆栈实现
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       if(listNode == null){
           ArrayList firstlist =new ArrayList();
           return firstlist;
       }
       Stack<Integer> stk = new Stack<Integer>();
       while(listNode != null){
           stk.push(listNode.val);
           listNode = listNode.next;
       }
       ArrayList<Integer> arr =new ArrayList<Integer>();
        while(!stk.empty()){
            arr.add(stk.pop());
        }
        return arr;
        
    }
}
//大佬写的递归实现 1 2 3 4 5  实现 5 4 3 2  然后add 1 
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    private ArrayList<Integer> re = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       if(listNode==null)
           return re;
        printListFromTailToHead(listNode.next);
        re.add(listNode.val);
        return re;
    }
}

6.斐波那契额数列
现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39

//递归 占用内存打大
public class Solution {
    public int Fibonacci(int n) {
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
        return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
}
//非递归
public class Solution {
    public int Fibonacci(int n) {
       int a=1,b=1,c=0;
        if(n==0) return 0;
        else if(n==1||n==2) return 1;
        else {
            for(int i=2;i<n;i++){
               c=a+b;
               b=a;
               a=c;
            }
            return c;
        }
    }
}

7.旋转数组的最小数字【这个题暂时没看懂】
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

//这样直接求最小写能通过,但不是题目本意
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    int min=array[0];
        for(int i=0;i<array.length-1;i++){
            if (min>array[i]){
                min=array[i];
            }
        }
        return min;
    }
}
//用到二分,找到中间的数,然后和最左边的值进行比较,若大于最左边的数,则最左边从mid开始,若小于最右边值,则最右边从mid开始。若左中右三值相等,则取mid前后值中较小的数。
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    int front=0;
    int rear =array.length-1;
    int middle =(front+rear)/2;
    while(front<rear){
        if(rear-front == 1)
            break;
        middle =(rear+front)/2;
        if(array[middle] >= array[front]){
            front = middle;
        }else{
            rear = middle;
        }   
    }
        return array[rear];
    }
}

8.用两个栈实现一个队列
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

//  push  第一个栈 ,然后 查看第二个栈如果第二个不空直接pop 如果为空 第一个先push  第二个再pop
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {
        stack1.push(node); 
    }
    
    public int pop() {
        if(stack2.isEmpty()){
      while(!stack1.isEmpty()){
          stack2.push(stack1.pop());
      }
        }
      return stack2.pop();
    }
}

9.重建二叉树:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

//利用 前序和中序生成树
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre == null || in == null) {
			return null;
		}
		if (pre.length == 0 || in.length == 0) {
			return null;
		}
		if (pre.length != in.length) {
			return null;
		}
		TreeNode root = new TreeNode(pre[0]);//第一个
		for (int i = 0; i < in.length; i++) {
			if (pre[0] == in[i]) {
				//pre的0往后数i个是左子树的,copyofrange包含前面的下标,不包含后面的下标
				//in的i往前数i个是左子树的。
				root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i)); // 分别除去根节点
				//注意in是从i+1开始,因为i是现在的根,i+1开始才是右子树
				root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
						Arrays.copyOfRange(in, i + 1, in.length));
			}
		}
		return root;

    }
}

10.跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

// 递归 :斐波拉契数序列,初始条件n=1:只能一种方法,n=2:两种 ,对于第n个台阶来说,只能从n-1或者n-2的台阶跳上来,所以 F(n) = F(n-1) + F(n-2)
public class Solution{
    public int JumpFloor(int n){
        if(n==0) return 0;
        else if(n==1)return 1;
        else if(n==2)return 2;
        else return JumpFloor(n-1)+JumpFloor(n-2);
    }
}

11.变态跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//参考思路:在这里插入图片描述

//竟然是个等比数列
public class Solution {
    public int JumpFloorII(int target) {

        int res=1;
        for(int i=1;i<=target-1;i++){
            res=res*2;
        }
        return res;
    }
}

12.矩阵覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

//依然是斐波那契数列  可以试着 归纳做
public class Solution {
    public int RectCover(int n) {
          if(n==0) return 0;
          else if(n==1) return 1;
          else if(n==2) return 2;
          else{
              int result;
              result=RectCover(n-1)+RectCover(n-2);
              return result;
          }       
    }
}

13.调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

//通过 Arraylist 变长数组解决
import java.util.ArrayList;
public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList<Integer> jlist = new ArrayList<Integer>();
        ArrayList<Integer> olist = new ArrayList<Integer>();
        for(int i=0; i<array.length;i++){
            if(array[i]%2==0)
                olist.add(Integer.valueOf(array[i]));
            else
                jlist.add(Integer.valueOf(array[i]));//valueOf 是将int转换为Integer
        }
        
        jlist.addAll(olist); //先把所有偶数加上
        int temp=0;
        for(int i=0;i< jlist.size();i++){
            array[temp]=jlist.get(i).intValue();//intValue是反过来
            temp++;
        }
    }
}
//另一种方法 前偶后奇交换
import java.util.ArrayList;
public class Solution {
    public void reOrderArray(int [] array) {
      int temp = 0;
        for (int i = 0; i < array.length - 1; i++) {  
            for (int j = 0; j < array.length - 1 - i; j++) {  
                // 前偶后奇数就交换  
                if ((array[j] & 1) == 0 && (array[j + 1] & 1) == 1) {  //与1位与得1就是奇数,1只有最后一位是1
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }  
            }  
        }  
    }
}

14.链表中倒数第k个结点
输入一个链表,输出该链表中倒数第k个结点。

//一种思路 先遍历求长度 ,然后输入倒数第K个 【不行】
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head ==null) return head;
        ListNode node =head;
        int count =0;
        while(node != null){
            count++;
            node =node.next;
        }
        if(count < k) return null;
        ListNode p= head;
        for(int i=0;i<count -k;i++){
            p=p.next;
        }
        return p;
    }
}
//正常思路:设置两个游标,让快的领先K个,然后一块走,fast==null slow指向的那个就是
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    ListNode slow = head;
    ListNode fast = head;
    if(head ==null || k<=0){
        return null;
    }
    for(int i=1;i<k;i++){快的先走k-1步,倒数第三个,其实应该快的指到第三个,只需要走两步即可。
        if(fast.next == null)
            return null;
        else 
            fast=fast.next;
    }
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }
        return slow;
    }
}

15.反转链表
题目描述
输入一个链表,反转链表后,输出新链表的表头。

// 设置 三个指针 pre head next    next =head.next  head-next=pre  pre=head  head=next
public class Solution {
    public ListNode ReverseList(ListNode head) {
    if(head==null)
            return null;
        //head为当前节点,如果当前节点为空的话,那就什么也不做,直接返回null;
        ListNode pre = null;
        ListNode next = null;
        //当前节点是head,pre为当前节点的前一节点,next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向,但反转之后如果不用next节点保存next1节点的话,此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while(head!=null){
            //做循环,如果当前节点不为空的话,始终执行此循环,此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息,保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next,就可以让head从指向next变成指向pre了,代码如下
            head.next = pre;
            //head指向pre后,就继续依次反转下一个节点
            //让pre,head,next依次向后移动一个节点,继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候,pre就为最后一个节点了,但是链表已经反转完毕,pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}

16 .合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

//新建一个链表 比较两个链表看小的加入新链表 然后 长的链表在比较完毕后直接添加到尾部
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        //新建一个用于存放融合之后的链表
        ListNode res = new ListNode(0);
        ListNode merlistNode =res;
        while(list1 !=null && list2 != null){
            if(list1.val <list2.val){
                merlistNode.next=list1; //链上小的list1
                list1=list1.next;
                merlistNode=merlistNode.next;
            }
            else{
                merlistNode.next=list2;
                list2=list2.next;
                merlistNode=merlistNode.next;
            }
        }
        if(list1!=null)
            merlistNode.next=list1;
        if(list2!= null)
            merlistNode.next=list2;
        return res.next;
    }
}
//递归
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
            if (list1 == null)   return list2;  
            if (list2 == null)  return list1;  
            ListNode newHead = null;  
            if (list1.val <= list2.val) {  
                newHead = list1;  
                newHead.next = Merge(list1.next,list2);  
            }else {  
                newHead = list2;  
                newHead.next = Merge(list1,list2.next);  
            }  
  
            return newHead;
    }
}

17最大子序列和
给定一个序列,求最大的子序列和

//穷举    n3
public static int maxSub_1(int [] sequence){
        int max=0;
        int n =sequence.length;
        int sum=0;
        // i 设置窗口 
        for(int i=1;i<=n;i++) //第一重循环执行一次计算出长度为 i 的所有子序列的和的最大值
            for(int j=0;j<n;j++){
                sum=0;
                for(int k=j;k<j+i && k<n;k++)  j-j+i 为当前子序列   
                    sum+=sequence[k];
                if(sum>max) max=sum;

            }
        return max;
    }
 //改进  n2
    public static int maxSub_2(int [] sequence){
        int max=0;
        int n =sequence.length;
        int sum=0;
        for(int i=0;i<=n;i++) { //第一重循环执行一次计算出长度为 i 的所有子序列的和的最大值
            sum = 0;
            for (int j = i; j < n; j++) {
                sum += sequence[j];
                if (sum > max) max = sum;

            }
        }
        return max;
    }
    //递归  nlogn  分 左 右 中间
        public static int maxSum(int[] sequence,int left,int right){
        if(left == right) //只有一个数据
            if(sequence[left]>0)
                return sequence[left];
            else
                return 0;
            int mid =(left+right)/2;
            int maxLeftSum= maxSum(sequence,left,mid);
            int maxRightSum= maxSum(sequence,mid+1,right);
            int maxLeftBorderSum=0,leftBorderSum=0;
            for(int i = mid;i>=left;i--){
                leftBorderSum+=sequence[i];
                if(leftBorderSum> maxLeftBorderSum)
                    maxLeftBorderSum=leftBorderSum;
            }
        int maxRightBorderSum=0,rightBorderSum=0;
        for(int i=mid+1;i<=right;i++){
            rightBorderSum+=sequence[i];
            if(leftBorderSum> maxRightBorderSum)
                maxRightBorderSum=rightBorderSum;
        }
        return max3(maxLeftSum,maxRightSum,maxRightBorderSum+maxRightBorderSum);

    }
    public static int max3(int a,int b,int c){
        int max=a>b? a:b;
        max=max>c? max:c;
        return max;
    }
    //DP n  动态规划 
    public static int maxSub_4(int [] sequence){
        int max=0; 
        int n= sequence.length;
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=sequence[i]; 
            if(sum>max)  max=sum;  
            else if(sum<0)  sum=0;
        }
        return max;
    }

18.树的子结构判断
  输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

思路:
   //先从根开始再把左作为根,再把右作为根由本函数决定。把一个为根的时候的具体比对过程是第二个函数决定。
    //从根可以认为是一颗树,从左子树开始又可以认为是另外一颗树,从右子树开始又是另外一棵树。
    //本函数就是判断这一整颗树包不包含树2,如果从根开始的不包含,就从左子树作为根节点开始判断,
    //再不包含从右子树作为根节点开始判断。
    //是整体算法递归流程控制。
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean res = false;
        if (root1 != null && root2 != null) {
			if(root1.val == root2.val){
				res = doesTree1haveTree2(root1,root2);
			}
			if(!res)
			{
				res = HasSubtree(root1.left, root2);
			}
			if(!res)
			{
				res = HasSubtree(root1.right, root2);
			}
		}
        return res;
    }
	//本函数,判断从当前的节点 ,开始两个树能不能对应上,是具体的比对过程
    public boolean doesTree1haveTree2(TreeNode root1,TreeNode root2) {
		if(root2 == null)
			return true;
		if(root1 == null)
			return false;
		if(root1.val != root2.val){
			return false; 
		}
		//如果根节点可以对应上,那么就去分别比对左子树和右子树是否对应上
		return doesTree1haveTree2(root1.left, root2.left) && doesTree1haveTree2(root1.right, root2.right);
	}
}

19.二叉树的镜像
操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义:源二叉树
在这里插入图片描述

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/  递归  然后交换左右子树 
public class Solution {
    public void Mirror(TreeNode root) {
    if(root ==null) return; 
    if(root.left != null || root.right != null){
        TreeNode temp = root.left;
        root.left=root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
  }
}
//栈解决
/*public void Mirror(TreeNode root) {
        if (root == null) {
			return;
		}
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
        	TreeNode node = stack.pop();
        	if (node.left != null || node.right != null) {
				TreeNode temp = node.left;
				node.left = node.right;
				node.right = temp;
			}
        	if(node.left != null)
        		stack.push(node.left);
        	if(node.right != null)
        		stack.push(node.right);
			
		}
    }*/

20.顺时针打印矩阵
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

import java.util.ArrayList;
public class Solution {
	/**
	 * 基本思路:
	 * 1.左上角的坐标和右下角的坐标固定了一圈矩阵,先打印这一圈矩阵。其中,对矩阵只有一行或者一列分别打印。
	 * 2.打印完了这一圈,左上角坐标都+1 ,右下角的都减一,到更内一圈。
      *比如:4*4的矩阵,(0,0)--(3,3)然后,(1,1)--(2,2)
	 * 3.当左上角跑到右下角下面就结束了。
     * —---------|
       |         |
       |         |
       |----------
	 * @param matrix
	 * @return
	 */
	public  ArrayList<Integer> printMatrix(int [][] matrix){
		ArrayList<Integer> list = new ArrayList<Integer>();  //新建 list数组
		int topRow = 0;
		int topCol = 0;
		int downRow = matrix.length - 1;
		int downCol = matrix[0].length - 1;
		while (topRow <= downRow && topCol <= downCol) { //当满足左上角的小于等于右下角就可以循环
			printCircle(list, matrix, topRow++, topCol++, downRow--, downCol--);
		}
		return list;
	}
	
	public  void printCircle(ArrayList<Integer> list, int [][] matrix, int topRow, int topCol, int downRow, int downCol) {
		if (topRow == downRow) { //子矩阵只有一行的时候
			for (int i = topCol; i <= downCol; i++) {//注意循环开始的条件,是从这一列开始,不是从零
				list.add(matrix[topRow][i]);
			}
		}
		else if (topCol == downCol) {//子矩阵只有一列的时候
			for (int i = topRow; i <= downRow; i++) {//
				list.add(matrix[i][topCol]);
			}
		}
		else { //其他的情况下
			int currentRow = topRow;
			int currentCol = topCol;
			while (currentCol != downCol) {//左到右 本行最后一个不访问,在下个循环里面。如
				list.add(matrix[topRow][currentCol]);
			    currentCol++;
			}
			while (currentRow != downRow) {//上到下0
				list.add(matrix[currentRow][downCol]);
				currentRow++;
			}
			while (currentCol != topCol) {//右到左
				list.add(matrix[downRow][currentCol]);
				currentCol--;
			}
			while (currentRow != topRow) {//下到上
				list.add(matrix[currentRow][topCol]);
				currentRow--;
			}
		}
	}
}

21.两个链表的第一个公共结点
输入两个链表,找出它们的第一个公共结点

//相交节点的判断  公共部分是相交部分
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
     // 首先,如果相交,那么尾节点一定是一样的。
     // 接下来,谁长谁就先走一定的步数,然后一起走,肯定是同时到达相交的点。
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {        
        if(pHead1 == null || pHead2 ==null) return null;
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        int n =0;
        while(cur1.next != null){
            n++; // 记录长度
            cur1=cur1.next;
        }
        while(cur2.next  != null){
            n--;
            cur2=cur2.next;
        }
        if(cur1 != cur2) return null; //判断尾节点是否相同
        cur1 = n>0? pHead1:pHead2; //cur1 是 长 的 链表
        cur2 = cur1 == pHead1? pHead2:pHead1;
        n=Math.abs(n);
        while(n !=0){
            n--;
            cur1 =cur1.next;
        }
        while(cur1 !=cur2){
            cur1 =cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}

22 链表中环的入口节点
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null
//判断有环的思路
思路:

第一步,找环中相汇点。分别用p1,p2指向链表头部,

  • p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点。

通过快慢指针来判断是否有环,现在我们假设两个指针相遇在z点,如图
在这里插入图片描述
fast指针走过a+b+c+b
slow指针走过a+b
那么2*(a+b) = a+b+c+b
所以a = c

此时让slow回到起点,fast依然停在z,两个同时开始走,一次走一步
那么它们最终会相遇在y点,正是环的起始点【有点难理解】

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
      if (pHead == null || pHead.next == null) {
			return null;
		}
        ListNode fast = pHead;
        ListNode slow = pHead;
      while(fast != null && fast.next!=null){
            slow = slow.next;
        	fast = fast.next.next;//一个走一步 一个走两步 
            if(slow == fast){  //直到相遇
                fast = pHead; // 之后让fast 从头开始走  fast slow 都从头开始走
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
         }
        return null;
      }
 }

23.数组中只出现一次的数字
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

//思路 利用异或  数组异或 相同的数为0 和顺序无关
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
     int e0=0,e0ne=0;
     for(int num:array)
         e0 ^= num;  // e0的结果为 a^b  a b 为那两个数 
     int firstOne =e0 &(~e0+1);//求得二进制中第一位1,比如101和011得到001
     for(int cur:array)
         if((cur & firstOne) !=0){ //把第k位是1的找出来进行异或
             e0ne ^=cur;  //最后的到一个 a
         }
        num1[0]=e0ne;
        num2[0] = e0ne^e0;  // eone 为 a  则 eone^e0 为b 
     }
    
}

24.丑数
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

public class Solution {
  /**
     * 剑指offer的思路:
     * 取一个数组来放丑数,下一个丑数必定是这个数组里面的数乘以2或者3
     * 或者5,这三种中最小的那一个。依次,判断下去
     * @param index
     * @return
     */
    public int GetUglyNumber_Solution(int index) {
    	if(index <= 0)
    		return 0;
    	int [] res = new int[index];
    	res[0] = 1;//先把1放入
    	int m2 = 0;//控制乘以2的位置,假设得到一个丑数是乘以2得到的,
    	            //那么下一次就是数组中的下一个丑数可能达到。
    	int m3 = 0;
    	int m5 = 0;
    	for (int i = 1; i < index; i++) {
			int min = Math.min(res[m2]*2, Math.min(res[m3]*3, res[m5]*5));
			res[i] = min;//最小的那个作为当前的丑数
			//判断是由谁乘以得到的
			if(res[m2] *2 == min)//假设res[1]是乘以2得到的丑数,那么下一次就要判断
				              //是否是res[2]乘以2可能得到丑数,所以就要++
				m2++;
			if(res[m3]*3 == min)
				m3++;
			if(res[m5]*5 == min)
				m5++;
		}
        return res[index - 1];
    }
}
 

25.数组中出现超过数组长度的一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

public class Solution {
    //我的想法:排序取出中间数
    //哈希表记录 
    public int MoreThanHalfNum_Solution(int [] array) {
        int cand=0;
        int times =0;
        for(int i =0;i< array.length;i++){
            if(times ==0){
                cand = array[i];
                times = 1;
            }else if(array[i] == cand){
                times++;
            }else{
                times--;
            }
        }
        times =0;
        //做判断 cand 到底是不是 那个数
        for(int i=0; i<array.length;i++){
            if(array[i] ==cand)
                times++;
        }
        if(times*2 >array.length)  return cand;
        else return 0;
    }
}

26.最小的K个数
输入N个数,找出其中最小的K个数。例如,输入1,2,3,4,5,6,7,8,求最小的4个数,既输出1,2,3,4。

//还有其他方法建立一个堆
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;
public class Solution {
     //笨方法 排序 然后选择前K个
        //一种解法
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        List<Integer> list =new ArrayList<Integer>();
        if(k> input.length || k==0) return (ArrayList)list;
        for( int i =0;i<k;i++){
            list.add(input[i]);  //先放k个数
        }
        for( int i=k; i< input.length;i++){
            Collections.sort(list);  //每次都排序
            if(input[i]<list.get(k-1)){  //从k后面一个开始遍历,如果比list里面最大的值小,就替换掉。重新排序一次。循环执行
                list.set(k-1,input[i]);
            }
        }
        return (ArrayList)list;
    }
}

27 .把数组排成最小的数
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

思路一的复杂度为O(n!),那么我们能不能不进行全排列就能找到那个特定的排列呢?很容易想到就是排序,如果能想到一个很好的排序策略,即可优雅得到最后的结果。 
对于给定的2个数,a和b。如何确定两者之间的排序策略呢?我们可以发现这两者的排列为:ab,ba。我们最终目的是找到字典序最小的那个排列,所以我们肯定应该保持这种关系,从而决定是否交换顺序: 
1. 当ab < ba, a排在b的左边 
2. 当ab > ba, b排在a的左边 
3. 当ab = ba, 位置关系随意

不理解的话,可以结合选择排序算法来理解,我们在n个元素选择出最小的作为左边的值,显然它应该位于所有n-1个元素的左边,也就是第一个位置上。接着在n-1个元素找到次最小,反复如此,直到没有剩余元素。 
如果你理解了选择排序的做法,又因为一般的排序算法的结果都是一样,所以我们可以采用更快的排序算法来解答此题,为了方便,直接了使用了库函数,当然你可以自行实现快速排序或归并排序,这些都未尝不可。

    public static String PrintMinNumber2(int [] numbers) {
        if(numbers == null || numbers.length == 0) {
            return "";
        }
        String[] strNumbers = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(strNumbers, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < strNumbers.length; i++) {
            sb.append(strNumbers[i]);
        }
        return sb.toString();
    }

28.包含min函数的栈
  定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))

import java.util.Stack;

 /* 
* 思路:用一个栈stack保存数据,用另外一个栈min保存依次入栈最小的数  
* 比如,stack中依次入栈,5, 4, 3, 8, 10,11,12,1  
* 则min依次入栈,5, 4, 3, 3, 3, 3, 3, 1 
* 每次入栈的时候,如果入栈的元素比min中的栈顶元素小或等于则入栈,否则入stack的栈顶元素。  
* 保持stack中和min中保持相同个数的元素 ,同时保持min的栈顶是此时原栈的最小值。
*/
public class Solution {
    Stack<Integer> stackData =new Stack();
    Stack<Integer> stackMin =new Stack<Integer>();
    public void push(int node) {
        stackData.push(node);
        if(stackMin.size()==0|| stackMin.peek()> node)
            stackMin.push(node);
         else
             stackMin.push(stackMin.peek());
    }
    
    public void pop() {
      if(! stackData.isEmpty()){
          stackData.pop();
          stackMin.pop();
      }
    }
    
    public int top() {
        return stackData.peek();
    }
    
    public int min() {
        return stackMin.peek();
    }
}

29.栈的压入弹出
  输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

import java.util.ArrayList;
import java.util.Stack;
/**借用一个辅助的栈,遍历压栈顺序,先讲第一个放入栈中,这里是1,
    然后判断栈顶元素是不是出栈顺序的第一个元素,这里是4,很显然1≠4,所以我们继续压栈,
    直到相等以后开始出栈,出栈一个元素,则将出栈顺序向后移动一位,直到不相等,
    这样循环等压栈顺序遍历完成,如果辅助栈还不为空,说明弹出序列不是该栈的弹出顺序。
    举例: 
    入栈1,2,3,4,5 
   出栈4,5,3,2,1 
   首先1入辅助栈,此时栈顶1≠4,继续入栈2 
   此时栈顶2≠4,继续入栈3 
   此时栈顶3≠4,继续入栈4 
   此时栈顶4=4,出栈4,弹出序列向后一位,此时为5,,辅助栈里面是1,2,3 
   此时栈顶3≠5,继续入栈5 
   此时栈顶5=5,出栈5,弹出序列向后一位,此时为3,,辅助栈里面是1,2,3 
  …. 
  依次执行,最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。**/
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      if(pushA ==null ||popA == null || pushA.length ==0 ||popA.length ==0)
          return false;
       int index =0; //弹出序列的索引
       Stack <Integer> stack =new Stack<Integer>();
       for(int i =0;i<pushA.length;i++){
           stack.push(pushA[i]);
          while(! stack.isEmpty() && stack.peek() == popA[index]){
              stack.pop();
              index++;
          } //当栈不为空 且 栈顶元素等于弹出序列元素时候,弹出一个 
       }
        return stack.isEmpty(); //如果辅助栈不为空 
    }
}

30.和为 S 的两个数
题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输出描述:
对应每个测试案例,输出两个数,小的先输出

定义两个指针 一个指前 一个指后 指针游走
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
       if(array == null || array.length <2)
           return list;
       int low = 0;
       int high = array.length-1;
       while(low<high){
           int small = array[low];
           int big = array[high];
           if (small+big  == sum){
               list.add(small);
               list.add(big);
               break;
           }else if (small+big <sum){
               low++;
           }else{
               high--;
           }         
       }
       return list;
       
    }
}

31.左旋转字符串
汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

先旋转 前 n 个 和后 n 个 最后整个旋转
public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str == null || str.trim().length() ==0){
            return str;
        }
        int len =str.length();
        n = n % len;
        char[] charstr = str.toCharArray();
        reverse(charstr,0,n-1);
        reverse(charstr,n,len-1);
        reverse(charstr,0,len-1);
        return String.valueOf(charstr);
    }
    private void reverse(char[] charstr, int i ,int j){
        while(i<j){
            char temp = charstr[i];
            charstr[i] = charstr[j];
            charstr[j] = temp;
            i++;
            j--;
        }
    } 
}
  1. 翻转字符串
      例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
//普通方法 将空格把字符串切分然后 倒着写入 StringBuffer 中
public class Solution {
    public String ReverseSentence(String str){
        if(str == null || str.trim().length() == 0){
            return str;
        }
        String[] strs = str.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int i = strs.length-1; i>=0; i--){
            sb.append(strs[i]);
            if(i>0){
                sb.append(" ");
            }
    }
       return sb.toString();
}    
}
//先将要整个字符串发转 再逐个单词反转
public class Solution {
    public String ReverseSentence(String str){
        if(str == null || str.length() ==0 || str.trim().length() ==0)
            return str;
        StringBuffer sb = new StringBuffer();
        String re = reverse(str);
        String[] s = re.split(" ");
        for(int i =0 ; i< s.length -1 ;i++){
            sb.append(reverse(s[i])+" ");
        }
        sb.append(reverse(s[s.length-1]));
        return String.valueOf(sb);
}    
    public String reverse(String str){
        StringBuffer sb =new StringBuffer();
        for(int i = str.length()-1;i>=0;i--){
            sb.append(str.charAt(i));
        }
        return String.valueOf(sb);
    }
}

今天的文章Bulldozer_code分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/66068.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注