剑指offer（java版）
2020-02-14 本文已影响0人
少年梦游计_3403
1.二维数组的查找
题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在下边，因此，从右上角开始查找，就可以根据target和当前元素的大小来缩小查找区间，当前元素的查找区间为左下角的所有元素。
大于的，下移一行(r++)，小于的，左移一列(c--)
image.png
public class Solution {
public boolean Find(int target, int [][] array) {
/**
思路：先获取二维数组的行和列
从右上角那个数开始比较，大于它的，行++；小于它的，列--
**/
int rows = array.length, cols = array[0].length;
int r = 0, c = cols-1;
if(array==null || array.length==0){
return false;
}
while(r <= cols-1 && c >= 0){
if(target == array[r][c]){
return true;
}else if(target > array[r][c]){
r++;
}else{
c--;
}
}
return false;
}
}
2.替换空格
题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：找到一个空格，直接插入%20，然后在后面追加。或者直接replace函数
public class Solution {
public String replaceSpace(StringBuffer str) {
// return str.toString().replace(" ","%20");
StringBuilder sb = new StringBuilder();
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
if(c == ' '){
sb.append("%20");
}else{
sb.append(c);
}
}
return sb.toString();
}
}
3.从尾到头打印链表
题目描述：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
思路：递归
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//使用递归的思路
ArrayList<Integer> arrayList = new ArrayList<>();
if(listNode!=null){
arrayList.addAll(printListFromTailToHead(listNode.next));
arrayList.add(listNode.val);
}
return arrayList;
}
4.重建二叉树
题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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.length == 0 || in.length == 0)
return null;
TreeNode root = new TreeNode(pre[0]);
//在中序中找到先序的根
for(int i=0;i<in.length;i++){
if(in[i]==pre[0]){
root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
break;
}
}
return root;
}
}
5.用两个栈实现一个队列
题目描述：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：栈为先进后出，队列为先进先出，数据先全部进栈1，然后出栈1，进栈2，出栈2，这样出来的就是队列的顺序了
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);//数据进栈1
}
public int pop() {
if(stack2.isEmpty()){//栈2为空
while(!stack1.isEmpty()){//栈1不空
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
6.旋转数组的最小数字
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素，例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：二分法
public int minNumberInRotateArray(int [] array) {
int left = 0,right = array.length - 1,mid = 0;
while(array[left] >= array[right]){
mid = left + (right-left)/2;
if(array[mid] >= array[left]){
left = mid;
}else if(array[mid] <= array[right]){
right = mid;
}
if(right - left == 1){
mid = right;
break;
}
}
return array[mid];
}
7.斐波那契数列
题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
思路：递归
public static int Fibonacci(int n) {
if(n==0){
return 0;
}else if(n==1){
return 1;
}else{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
8.跳台阶
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：递归
public int JumpFloor(int target) {
if(target == 1){//台阶数为1
return 1;
}else if(target == 2){
return 2;
}else{
return JumpFloor(target-1) + JumpFloor(target-2);
}
}
9.变态跳台阶
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
public int JumpFloorII(int n) {
if(n <= 0){
return 0;
}else if(n == 1){
return 1;
}else{
return 2*JumpFloorII(n-1);
}
}
10.矩形覆盖
题目描述：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：
public int RectCover(int target) {
if(target==1){
return 1;
}else if(target==2){
return 2;
}else if(target==0){
return 0;
}
return RectCover(target-1)+RectCover(target-2);
}
11.二进制中1的个数
题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路：如二进制数11011，将其-1，得11010，在于原来的数做与运算，得11010，此二进制数相比原二进制数中的1少了一个，重复此过程，直至该数变为0，结束循环
public static int NumberOf1(int n) {
int count=0;
while (n!=0){
int n2 = n-1;
n=n&n2;
count++;
}
return count;
}
12.数值的整数次方
题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0
思路：分正整数和负整数，正整数就是直接累乘，负整数就是正整数的分之一
public double Power(double base, int exponent) {
double res=1.0;
if(exponent >= 0){//正整数次方
for(int i=1;i<=exponent;i++){
res*=base;
}
}else{//负整数次方
for(int i=1;i<=-exponent;i++){
res*=base;
}
res=1/res;
}
return res;
}
13.调整数组顺序使奇数位于偶数前面
题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：两个游标i和j，i从前往后走，遇到偶数停住，j从后往前走，遇到奇数停住，游标i和j位置的数交换。
public void reOrderArray(int [] array) {
for(int i=0;i<array.length;i++){
for(int j=array.length-1;j>=i;j--){
while(array[i]%2==0 && array[j]%2==1){
int t=array[i];
array[i]=array[j];
array[j]=t;
}
}
}
}
14.
题目描述：
思路：用两个指针，一个先出发k-1个节点，然后同步出发，当p1到达尾部时，p2则是我们要求的结点
public ListNode FindKthToTail(ListNode head,int k) {
ListNode p1=head,p2=head;
if(head==null || k<=0)
return null;
for(int i=0;i<k-1;i++){
if(p1.next==null)
return null;
p1=p1.next;
}
while(p1.next!=null){
p1=p1.next;
p2=p2.next;
}
return p2;
}
15.反转链表
题目描述：输入一个链表，反转链表后，输出新链表的表头。
思路：递归
public ListNode ReverseList(ListNode head) {
if(head==null)
return null;
else if(head.next==null)
return head;
ListNode L=head.next;
head.next=null;
ListNode returnVal = ReverseList(L);
L.next=head;
return returnVal;
}
//头插法
ListNode L=new ListNode(-1);
while(head!=null){
ListNode next=head.next;
head.next=L.next;
L.next=head;
head=next;
}
return L.next;...
16.合并两个排序的链表
题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：递归和迭代两种思路
//递归
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null){//list1为空，合并后则为list2
return list2;
}else if(list2==null){
return list1;
}else if(list1.val <= list2.val){//list1的值小于list2的值，list2接在list1后边
list1.next=Merge(list1.next,list2);
return list1;
}else{
list2.next=Merge(list2.next,list1);
return list2;
}
}
//迭代
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head = new ListNode(-1);
ListNode p = head;
while(list1!=null && list2!=null){
if(list1.val <= list2.val){
p.next = list1;
list1 = list1.next;
}else{
p.next = list2;
list2 =list2.next;
}
p=p.next;
}
if(list1!=null){
p.next=list1;
}else if(list2!=null){
p.next=list2;
}
return head.next;
}
17.树的子结构
题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null){
return false;
}else if(root2==null){
return false;
}
return isChild(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
}
private boolean isChild(TreeNode A,TreeNode B){
if(B==null){
return true;
}else if(A==null){
return false;
}else if(A.val!=B.val){
return false;
}
return isChild(A.left,B.left)&&isChild(A.right,B.right);
}
18.二叉树的镜像
题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。
思路：用先序遍历+递归的思路
public void Mirror(TreeNode root) {
//先序遍历
if(root==null)
return;
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
Mirror(root.left);
Mirror(root.right);
}
19.顺时针打印矩阵
题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
思路：
public ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(matrix==null || matrix.length==0)
return res;
printClock(matrix,0,0,matrix.length-1,matrix[0].length-1,res);
return res;
}
public void printClock(int[][] matrix,int startR,int startC,int endR,int endC,ArrayList<Integer> res){
int i=0;
if(startR<endR && startC<endC){
for(i=startC;i<=endC;i++){ res.add(matrix[startR][i]); }
for(i=startR+1;i<=endR-1;i++){ res.add(matrix[i][endC]); }
for(i=endC;i>=startC;i--){ res.add(matrix[endR][i]); }
for(i=endR-1;i>=startR+1;i--){ res.add(matrix[i][startC]); }
printClock(matrix,startR+1,startC+1,endR-1,endC-1,res);
}else if(startR==endR && startC<endC){
for(i=startC;i<=endC;i++){ res.add(matrix[startR][i]); }
}else if(startR<endR && startC==endC){
for(i=startR;i<=endR;i++){ res.add(matrix[i][endC]); }
}else if(startR==endR && startC==endC){
res.add(matrix[startR][startC]);
}else{
return;
}
}
20 包含min函数的栈
题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：用两个栈，stack 和 min，最开始都存一个元素，然后每个元素都和min的顶部元素比较，小于min的顶部元素，入min栈，否则不入min，只入stack栈，最后返回min的顶部
import java.util.Stack;
public class Solution {
private Stack<Integer> stack=new Stack<>();
private Stack<Integer> minStack=new Stack<>();
public void push(int node) {
if(stack.isEmpty()){
stack.push(node);
minStack.push(node);
return;//只让一个元素入栈
}
int topVal=minStack.peek();//peek函数：取栈顶元素值，且栈顶元素依然在栈中
if(topVal > node){
minStack.push(node);//minStack里面元素比新元素大，入新元素
}else{
minStack.push(topVal);
}
stack.push(node);
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
21.栈的压入弹出序列
题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
22.从上往下打印二叉树
题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：用队列按层次遍历
import sun.reflect.generics.tree.Tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class PrintFromTopToBottom
{
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
/**
* 思路：
* 1、利用队列进行层次遍历
* 2、每次弹出队列中的一个元素，并把左右孩子加入队列即可
*/
public ArrayList<Integer> printFromTopToBottom(TreeNode root) {
ArrayList<Integer> cache = new ArrayList<>();
if(root==null){
return cache;
}
Queue<TreeNode> q= new LinkedList<>();
q.add(root);
TreeNode curNode;
while (!q.isEmpty()){
curNode=q.poll();
cache.add(curNode.val);
if(curNode.left!=null){
q.offer(curNode.left);
}
if(curNode.right!=null){
q.offer(curNode.right);
}
}
return cache;
}
public static void main(String[] args)
{
TreeNode root = createBinaryTree();
System.out.println(new PrintFromTopToBottom().printFromTopToBottom(root));
}
private static TreeNode createBinaryTree() {
TreeNode root = new TreeNode(0);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
root.left = node1;
root.right = node2;
TreeNode node3 = new TreeNode(3);
node1.left = node3;
return root;
}
}
23.二叉搜索树的后续遍历
题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：二叉搜索树的后序遍历下，最后一个为根结点，小于根结点值的为根结点的左子树，大于的为右子树，可以这样递归判断
public class Solution {
/**
* 后续遍历，最后一个为根结点，比根结点的小的都在左子树上，比根结点大的都在右子树上，递归判断即可
* @param sequence
* @return
*/
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null || sequence.length==0){
return false;
}
return judge(sequence,0,sequence.length-1);
}
private boolean judge(int[] arr,int start,int end){
if(start>=end){
return true;
}
int i=end;
//右子树
while (i>start && arr[i-1]>arr[end]){
i--;
}
//左子树
for(int j=start;j<i-1;j++){
if(arr[j]>arr[end]){
return false;
}
}
//递归判断左右子树
return judge(arr,start,i-1)&&judge(arr,i,end-1);
}
}
24.二叉树中和为某一值的路径
题目描述：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路：从根结点开始加，加到够target为止
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> res=new ArrayList<>();
private ArrayList<Integer> path=new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root==null){
return res;
}
findPath(root,target,0);
return res;
}
public void findPath(TreeNode root,int target,int sum){
path.add(root.val);
sum+=root.val;
if(sum==target&&root.left==null&&root.right==null){
res.add(new ArrayList(path));//将路径加入结果集中
}
//如果左子树非空，递归左子树
if(root.left!=null){
findPath(root.left,target,sum);
}
//递归右子树
if(root.right!=null){
findPath(root.right,target,sum);
}
//无论当前路径是否加出了target，必须去掉最后一个，返回父节点，去查找另一条路径
path.remove(path.size()-1);
return;
}
}
25.复杂链表的复制
题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路：
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.HashMap;
public class Solution {
HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
public RandomListNode Clone(RandomListNode oldNode) {
if(oldNode==null)
return null;
if(map.containsKey(oldNode)){
return map.get(oldNode);
}
RandomListNode tmpNode = new RandomListNode(oldNode.label);
map.put(oldNode,tmpNode);
tmpNode.next=Clone(oldNode.next);
tmpNode.random=Clone(oldNode.random);
return tmpNode;
}
}
26.二叉搜索树与双向链表
题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
import java.util.Stack;
public class Solution {
/**
* 思路：利用一个栈实现二叉树的中序遍历，二叉搜索树的中序遍历为递增有序的序列
* 这时候只要在中序遍历的时候找到一个遍历结点的时候先将这个结点保存起来，
* 然后遍历下一个结点的时候将之前保存的结点的right域指向下一个结点，
* 下一个结点的left域指向上一个结点，这样就形成了一个排序的双向链表，
* 然后将指向保存的指针指向当前这个结点
*/
public TreeNode Convert(TreeNode pRootOfTree) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = pRootOfTree;
TreeNode node = null;
TreeNode retRoot = null;
while (cur!=null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
if(node==null){
node=cur;
retRoot=node;
}else{
node.right=cur;
cur.left=node;
node=node.right;
}
cur=cur.right;
}
}
return retRoot;
}
}
27.字符串的排列
题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str){
ArrayList<String> res = new ArrayList<>();
if(str!=null || str.length()>0){
help(0,str.toCharArray(),res);
Collections.sort(res);
}
return res;
}
public static void help(int i,char[] arr,ArrayList<String> res){
if(i==arr.length-1){
String val = String.valueOf(arr);
if(!res.contains(val)){
res.add(val);
}
}else{
for(int j=i;j<arr.length;j++){
swap(i,j,arr);//依次选一个数固定住
help(i+1,arr,res);//让后面的进行全排列
swap(i,j,arr);
}
}
}
public static void swap(int i,int j,char[] arr){
char temp = arr[i];
arr[i]= arr[j];
arr[j]=temp;
}
}
28.数组中出现超过一半的数字
题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int len=array.length;
if(len==0){
return 0;
}
int res = array[0];//res作为最后结果，初始化为数组中第一个
int times = 1;//统计每个的次数
for(int i=1;i<len;i++){
//times为0的时候需要将次数置1，并且写入下一个数字
if(times==0){
res=array[i];
times=1;
}else if(array[i]==res){
times++;//数字相同加1
}else{
times--;//数字不同 减1
}
}
//统计的个数必须大于长度的一半才有效
times=0;
for(int i=0;i<len;i++){
if(res==array[i]){
times++;
}
}
if(times*2<=len){
res=0;
}
return res;
}
}
29.最小的k个数
题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：
import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
/**
* 思路:创建一个容量为k的数据容器存储最小的k个数字，接下来每次从输入的n个整数中读入一个
* 数，如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器中，如果容器中
* 已经有了k个数字了，我们就不能再放入数字了，只能去替换容器中已有的数字，替换的
* 规则为，我们拿待插入的数字和容器中k个数字中的最大值相比较，如果大于容器中的最大值
* 则抛弃这个数，否则替换
*
*/
ArrayList<Integer> list = new ArrayList<Integer>();
int len = input.length;
if(input==null || len==0 || k<=0 || k>len){
return list;
}
TreeSet<Integer> treeSet = new TreeSet<Integer>();
for(int i=0;i<len;i++){
if(treeSet.size()<k){
treeSet.add(input[i]);
}else if(input[i]<treeSet.last()){
treeSet.remove(treeSet.last());
treeSet.add(input[i]);
}
}
Iterator<Integer> iterator = treeSet.iterator();
while (iterator.hasNext()){
list.add(iterator.next());
}
return list;
}
}
30连续子数组的最大和
题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
思路：
public class Solution30 {
public int FindGreatestSumOfSubArray(int[] array) {
if(array==null || array.length==0){
return 0;
}
//初始化sum为第一个元素的值
int sum = array[0];
//初始化maxSum为第一个元素的值
int maxSum = sum;
for(int i=1;i<array.length;i++){
//当前连续字符序列的和
int curSum = sum+array[i];
//更新连续子序列的最大和
maxSum=Math.max(maxSum,curSum);
//更新sum，小于等于0的话置连续子序列和为0
sum = curSum<0?0:curSum;
}
return maxSum;
}
public static void main(String[] args){
int[] arr = {6,-3,-2,7,-15,1,2,2};
System.out.println(new Solution30().FindGreatestSumOfSubArray(arr));
}
}
31.整数中1出现的次数
题目描述：求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
思路：
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
/**
* 首先想到的就是：遍历1到n，把每个整数转为为string，
* 然后转化做char[],判断每一位上的1的个数。
*/
if(n<=0){
return 0;
}
int sum=0;
for(int i=1;i<=n;i++){
char[] cs = String.valueOf(i).toCharArray();
for(char c:cs){
if(c=='1'){
sum++;
}
}
}
return sum;
}
}
32.把数组排成最小的数
题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路：
public class Solution {
public String PrintMinNumber(int[] numbers) {
String min=new String();
int len=numbers.length;
if(numbers==null || len==0){
return min;
}
if(len==1){
return String.valueOf(numbers[0]);
}
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
String a = numbers[i]+""+numbers[j];
String b = numbers[j]+""+numbers[i];
if(a.compareTo(b)>0){
swap(i,j,numbers);//a>b时，交换i和j
}
}
}
for(int num:numbers){
min+=String.valueOf(num);
}
return min;
}
private static void swap(int i,int j,int[] nums){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
33.丑数
题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路：
public class Solution {
public int GetUglyNumber_Solution(int index) {
/**
* 首先除2，直到不能整除为止，然后除5直到不能整除为止
* 然后除3直到不能整除为止，最终判断剩余的数字是否为1
* 为1则为丑数，否则不是
*/
if(index<=0)
return 0;
int[] uglyArr = new int[index];//存储丑数的数组
uglyArr[0]=1;//第一个丑数为1
int multiply2=0,multiply3=0,multiply5=0;
for(int i=1;i<index;i++){
//为了有序，所以需要从三个中取最下的加入到数组
int min=getMinOfThree(uglyArr[multiply2]*2,uglyArr[multiply3]*3,uglyArr[multiply5]*5);
uglyArr[i]=min;
//如果生成的丑数和数组中已有的重复，则继续累加
while (uglyArr[multiply2]*2 == uglyArr[i])
multiply2++;
while (uglyArr[multiply3]*3 == uglyArr[i])
multiply3++;
while (uglyArr[multiply5]*5 == uglyArr[i])
multiply5++;
}
return uglyArr[index-1];
}
public int getMinOfThree(int num1,int num2,int num3){
int min=(num1<num2)?num1:num2;
return min<num3?min:num3;
}
}
34.第一个只出现一次的字符
题目描述：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
思路：
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int FirstNotRepeatingChar(String str) {
/**
* 通过一个map来保存字母及其出现过的次数，然后在从头遍历一次
* 找到一个只出现过一次的代码
*/
if(str.equals(""))
return -1;
Map<Character,Integer> map = new HashMap<>();
for(int i=0;i<str.length();i++){
if(map.get(str.charAt(i))!=null){
map.put(str.charAt(i),1+map.get(str.charAt(i)));
}else{
map.put(str.charAt(i),1);
}
}
for(int i=0;i<str.length();i++){
if(map.get(str.charAt(i))==1){
return i;
}
}
return 0;
}
}
35.数组中的逆序对
题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
思路：
public class Solution {
/**
* 优化思路：
* 1、分开计算子序列的逆序对数
* 2、合并时，子序列进行排序，从排序后的最后一个元素开始比较
* 3、如果上一个子序列最后一个元素大于后一个子序列的最后一个元素，则逆序对个数为后一个子序列的长度，并把大的元素，暂存一个复制数组的最后一个空缺位
* 4、如果上一个子序列的最后一个元素小于后一个子序列的最后一个元素，则把后一个序列的最后一个元素放到复制数组的最后一个空缺位
* 5、处理两个子序列未处理完的部分
* 6、排序后的部分 更新到 原数组中
*/
public int InversePairs(int [] array) {
if (array == null || array.length == 0) {
return 0;
}
// 归并获取逆序对数量
return getInversePairsNumFast(array, 0, array.length - 1);
}
private int getInversePairsNumFast(int[] arr, int start, int end) {
if (start == end) {
return 0;
}
int mid = (start + end) /2;
int left = getInversePairsNumFast(arr, start, mid) % 1000000007;
int right = getInversePairsNumFast(arr, mid + 1, end) % 1000000007;
// 记数第一个序列的最后一个索引
int i = mid;
// 记数第二个序列的最后一个索引
int j = end;
// copy当前子数组序列段用于排序
int len = end - start + 1;
int[] copy = new int[len];
// 第一个数据要放的位置
int copyIndex = len - 1;
// 逆序对的数量
int count = 0;
// 遍历两个序列，从最后一个元素开始
while (i >= start && j >= mid + 1) {
if (arr[i] > arr[j]) {
// 逆序对增加 当前第二个序列的元素个数
count += j - mid;
// 大的元素拷贝到拷贝的排序数组中
copy[copyIndex] = arr[i];
if(count >= 1000000007) {//数值过大求余
count %= 1000000007;
}
// i位置前移
i--;
} else {
// 此种情况 当前第一个序列中的所有元素无法与第二个序列中的这个元素组成逆序对
// count不变，第二个序列中的当前元素进入拷贝数组
copy[copyIndex] = arr[j];
//j位置前移
j--;
}
// copyIndex位置前移
copyIndex--;
}
// 处理剩余的第一个序列的元素
while (i >= start) {
copy[copyIndex--] = arr[i--];
}
// 处理剩余的第二个序列的元素
while (j >= mid + 1) {
copy[copyIndex--] = arr[j--];
}
// copy数组复制到原数组
for(int k = 0; k < len; k++) {
arr[k + start] = copy[k];
}
return (count + left + right) % 1000000007;
}
}
36.两个链表的第一个公共结点
题目描述：输入两个链表，找出它们的第一个公共结点。
思路：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
/**
* 先遍历找到两个链表的长度cnt1和cnt2，比较两个的长度差gap，然后让长的先走gap步
* 走完gap步后两个同样长，两个一起走，就可以了
* @param pHead1
* @param pHead2
* @return
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2==null)
return null;
ListNode p1=pHead1,p2=pHead2;
int cnt1=0,cnt2=0;//统计pHead1和pHead2的长度
while (p1!=null){
cnt1++;
p1=p1.next;
}
while (p2!=null){
cnt2++;
p2=p2.next;
}
int gap=cnt1-cnt2;//长度差
ListNode pLong=pHead1,pShort=pHead2;
if(gap<0){//pHead1比pHead2短的话
pLong=pHead2;
pShort=pHead1;
gap=cnt2-cnt1;
}
//长的先走
for(int i=0;i<gap;i++){
pLong=pLong.next;
}
//此时两个一样长
while (pLong!=null && pLong!=pShort){
pLong=pLong.next;
pShort=pShort.next;
}
return pLong;
}
}
37.数字在排序数组中出现的次数
题目描述：统计一个数字在排序数组中出现的次数。
思路：
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length==0)
return 0;
int left=0,right=array.length-1,index=0;
//二分法
while (left<right){
int mid = (left+right)/2;
if(array[mid] < k){
left = mid+1;
}else if(array[mid] > k){
right = mid-1;
}else{
index = mid;
break;
}
}
//遍历查找所有的k
int cnt=0;
for(int i=index;i>=0&&array[i]==k;i--)
cnt++;
for(int i=index+1;i<array.length&&array[i]==k;i++)
cnt++;
return cnt;
}
}
38.二叉树的深度
题目描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路：递归
public int TreeDepth(TreeNode root) {
if(root==null)
return 0;
int left=TreeDepth(root.left),right=TreeDepth(root.right);
return left>=right?(left+1):(right+1);
}
39.平衡二叉树
题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路：平衡二叉树为左右子树高度差小于等于1
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null)
return true;
if(Math.abs(height(root.left)-height(root.right)) <= 1)
return true;
else
return false;
}
public int height(TreeNode root){
if(root==null)
return 0;
int left=height(root.left),right=height(root.right);
return left>right?(left+1):(right+1);
}
}
40 数组中只出现一次的数字
题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路：
//两个相同数字异或=0，一个数和0异或还是它本身。
if(array.length<2)
return;
int xor=0,flag=1;
for(int i=0;i<array.length;i++)
xor^=array[i];
while ((xor&flag)==0)
flag<<=1;
for(int i=0;i<array.length;i++){
if((flag&array[i])==0)
num2[0]^=array[i];
else
num1[0]^=array[i];
}
41.和为s的连续正数序列
题目描述：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
思路：
import java.util.ArrayList;
public class Solution {
/**
* 我们要找的是和为S的连续正数序列，因此这个序列是个公差为1的等差序列
* 而这个序列的中间值代表了平均值的大小，假设序列长为n，那么这个序列的中间值
* 可以通过(s/n)得到，知道序列的中间值和长度即可。
* 满足条件的n分为两种情况：n为奇数时，序列中间的数正好是序列的平均值，
* 奇数条件为：n%2==1 && sum%n==0
* n为偶数时，序列中间的两个数的平均值即为序列的平均值
* 偶数条件为：(sum%n)%2==n
* 等差数列的求和公式S=(1+n)*n/2
* @param sum
* @return
*/
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int n = (int) Math.sqrt(2*sum);n>=2;n--){
if((n%2==1 && sum%n==0) || (sum%n)*2==n){
ArrayList<Integer> temp = new ArrayList<>();
for(int j=0,k=(sum/n)-(n-1)/2;j<n;j++,k++){
temp.add(k);
}
list.add(temp);
}
}
return list;
}
}
42.和为s的两个数字
题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路：
import java.util.*;
public class Solution {
/**
* 使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值，指向较小
* 元素的指针从头到尾遍历，指向较大的指针从尾到头遍历
* 如果两个指针指向元素的和sum==target，那么得到要求的结果
* 若sum>target 移动较大的元素，使得sum变小一些
* 若sum<target 移动较小的元素，使sum变大一些
* @param array
* @param sum
* @return
*/
public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
int i=0,j=array.length-1;
while (i < j){
int cur = array[i]+array[j];
if(cur == sum){
return new ArrayList<>(Arrays.asList(array[i],array[j]));
}else if(cur < sum){
i++;
}else{
j--;
}
}
return new ArrayList<>();
}
}
43.左旋转字符串
题目描述：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
思路：
public class Solution {
public String LeftRotateString(String str,int n) {
// if(str==null || str.length()<n)
// return "";
// String s1=str.substring(0,n);
// String s2=str.substring(n);
// return s2+s1;
if(str.length()==0 || n>=str.length()){
return str;
}
char[] chars = str.toCharArray();
reverse(chars,0,n-1);//前半段翻转
reverse(chars,n,chars.length-1);//后半段反转
reverse(chars,0,chars.length-1);//整体翻转
return new String(chars);
}
private void reverse(char[] chars,int i,int j){
while (i<j)
swap(chars,i++,j--);
}
private void swap(char[] chars,int i,int j){
char t = chars[i];
chars[i] = chars[j];
chars[j] = t;
}
}
44.翻转单词顺序列
题目描述：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
思路：
public class Solution {
public String ReverseSentence(String str) {
int n =str.length();
char[] chars = str.toCharArray();
int i=0,j=0;
while (j<=n){
if (j==n || chars[j]==' '){
reverse(chars,i,j-1);
i=j+1;
}
j++;
}
reverse(chars,0,n-1);
return new String(chars);
}
private void reverse(char[] chars,int i,int j){
while (i<j)
swap(chars,i++,j--);
}
private void swap(char[] chars,int i,int j){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
45 扑克牌顺子
题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
思路：
import java.util.Arrays;
public class Solution {
/**
* 思路：先把数组排序，再统计数组中0（大王）的个数，最后统计排序之后的数组中
* 相邻数字之间的空缺总数，如果空缺的总数小于等于0的的个数，那么这个数组就是连续的，
* 繁殖不连续，另外如果数组中的非0数字重复出现，则不连续
* @param numbers
* @return
*/
public boolean isContinuous(int [] numbers) {
if(numbers == null || numbers.length<5)
return false;
Arrays.sort(numbers);
int cnt=0,kCnt=0,i;//cnt 0的个数，kCnt 空缺的个数
for(i=0;i<numbers.length;i++){
if(numbers[i]==0) {
cnt++;
}
}
for(i=0;i<numbers.length-1;i++){
int a = numbers[i],b=numbers[i+1];
if(a==0 || b==0){
continue;
}else if(a==b){
return false;//两张连续的牌连续，非顺子
}
kCnt +=b-a-1;
}
if( (cnt!=0 && kCnt==cnt) || kCnt==0){
return true;
}
return false;
}
}
46.孩子们的游戏
题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
思路：
import java.util.LinkedList;
public class Solution {
/**
* 采用链表来存放数据，每次对长度取余来实现循环
* 将所有数字放入LinkedList链表中，假设当前删除结点的下标为removeIndex，
* 则下一个要删除的结点下标为(removeIndex+m-1)%list.size()
* @param n
* @param m
* @return
*/
public int LastRemaining_Solution(int n, int m) {
if(n<=1 || m<1)02
return -1;
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i=0;i<n;i++)
list.add(i);
int removeIndex=0;
while (list.size()>1){
removeIndex=(removeIndex+m-1)%list.size();
list.remove(removeIndex);
}
return list.getFirst();
}
}
47.求1+2+3+...+n
题目描述：求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
思路：
public class Solution {
/**
* 利用逻辑与的短路特性实现递归终止
* &&短路：第一个表达式为false，则不再计算第二个表达式
* 当递归到0,时，Boolean a=(n>0)&&((res+=Sum_Solution(n-1))>0);
* n不大于0，逻辑与不进行后面的递归计算，最终向上一层返回0
* @param n
* @return
*/
public int Sum_Solution(int n) {
int res=n;
boolean a = (n>0)&&((res+=Sum_Solution(n-1))>0);
return res;
}
}
48.不用加减乘除做加法
题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：
public class Solution {
/**
* 1.不考虑进位对每一位相加：1+0 0+1都等于0，而0+0 1+1都等于0 所以使用异或^操作
* 2.计算进位:只有1+1产生进位，所以才用位与&操作，再左移1为
* 3.将和与进位相加，重复前两步操作，结束判断进位为0
* @param num1
* @param num2
* @return
*/
public int Add(int num1,int num2) {
while (num2!=0){
int sum = num1^num2;//没进位的和
int carry=(num1&num2)<<1;//进位
num1=sum;
num2=carry;
}
return num1;
}
}
49.把字符串转换成整数
题目描述：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
思路：
public class Solution {
public int StrToInt(String str) {
if (str.length()==0 || str==null) {
return 0;
}
// 数字的正负，默认是正数
int symbol = 1;
char[] array = str.toCharArray();
int sum = 0;
// 如果第一位是'-'，说明结果应该是个负数，'+'不需要处理symbol
// 同时替换该位置上的字符为0，这样在下面的处理中，可以认为是跳过该字符
// 因为0 * 10还是0
if (array[0] == '-') {
symbol = -1;
array[0] = '0';
} else if (array[0] == '+') {
array[0] = '0';
}
for (int i = 0; i < array.length; i++) {
// 如果不是数字，而是其他字母符号一类非数字字符，则直接返回0
if (array[i] < '0' || array[i] > '9') {
return 0;
}
// sum * 10是为了将当前已获得数字整体左移一位，让新的数字可以处于个位上，比如"12"
// 第一次拿出1，在第二次拿出2的时候，1应该在十位上，2在个位上，所以 1 * 10 + 2 = 12
// array[i] - '0'，这里减去字符'0'，是因为字符'0'-'9'的ascii码值与其对应的数字相差48，而'0'的ascii码值正好是48
sum = sum * 10 + array[i] - '0';
}
return sum * symbol;
}
}
50.数组中重复的数字
题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路：
import java.util.*;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
boolean flag=false;
if(length==0 || numbers==null)
return false;
Arrays.sort(numbers);//先排序
for(int i=0;i<numbers.length-1;i++){
if(numbers[i]==numbers[i+1]){
flag=true;
duplication[0]=numbers[i];
break;
}
}
return flag;
}
}0.
51.构建乘积数组
题目描述：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。
思路：
image.png
import java.util.ArrayList;
public class Solution {
/**
* 本题的中心思想是将返回的数据列成一个矩阵，然后每一个矩阵的行向量都是一个从
* a(0)到a(n-1),然后这个对角线都是1，那么此时B0的值就是A0为1，剩下的行向量相乘
* @param A
* @return
*/
public int[] multiply(int[] A) {
int len = A.length;
int[] B = new int[len];
B[0] = 1;
//计算下三角
for(int i=1;i<len;i++){
B[i] = B[i-1]*A[i-1];
}
int temp=1;
//计算上三角
for(int j=len-2;j>=0;j--){
temp*=A[j+1];
B[j]*=temp;
}
return B;
}
}
52.正则表达式匹配
题目描述：请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
思路：
public class Solution {
/**
* 分析：本题的核心在于分析*，因为对.来说，他和任意字符都匹配，可以当做普通字符
* 对于*的分析，要分情况讨论
* 1.在每轮匹配中，Pattern第二个字符是*是
* ①第一个字符不匹配，那么*只能代表匹配0次，比如ba和a*ba，字符串不变，模式串向后
* 移动两个字符，然后匹配剩余字符串和模式串
* ②第一个字符匹配，那么*可能代表匹配0次，1次，比如aaa和a*aaa，aba和a*ba，aaaba和a*ba，
* 匹配0次时，字符串不变，模式串向后移动两个字符，然后匹配剩余字符串和模式串，
* 匹配1次时，字符串往后移动一个字符，模式串向后移动两个字符，
* 匹配多次时，字符串往后移动一个字符，模式不变
* 2.pattern第二个不是*时
* ①如果字符串第一个字符和模式中的第一个字符匹配，那么在字符串和模式上都向后移动一个字符，然后匹配剩余字符串和模式串
* ②如果字符串第一个字符和模式串已经不匹配了，直接返回false
* @param str
* @param pattern
* @return
*/
public boolean match(char[] str, char[] pattern) {
if(str==null || pattern==null)
return false;
int strIndex=0,patternIndex=0;
return matchCore(str,strIndex,pattern,patternIndex);
}
public boolean matchCore(char[] str,int strIndex,char[] pattern,int patternIndex){
//有效性检验，str到尾，pattern到尾，匹配成功
if(strIndex==str.length && patternIndex==pattern.length)
return true;
//pattern先到尾，匹配失败
if(strIndex!=str.length && patternIndex==pattern.length)
return false;
//如果模式串第二个是*，且字符串第一个根模式串第一个匹配，分三种匹配模式
if(patternIndex+1 < pattern.length && pattern[patternIndex+1]=='*'){
if( (strIndex!=str.length && pattern[patternIndex]==str[strIndex]) || (pattern[patternIndex]=='.' && strIndex!=str.length) ){
return matchCore(str,strIndex,pattern,patternIndex+2)||
matchCore(str,strIndex+1,pattern,patternIndex+2)||
matchCore(str,strIndex+1,pattern,patternIndex);
}else{
return matchCore(str,strIndex,pattern,patternIndex+2);
}
}
//模式第二个不是*，且字符串第一个根模式第一个匹配，则都后移一位
if( (strIndex!=str.length && pattern[patternIndex]==str[strIndex]) || (pattern[patternIndex]=='.' && strIndex!=str.length)){
return matchCore(str,strIndex+1,pattern,patternIndex+1);
}
return false;
}
}
53.表示数值的字符串
题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路：
public class Solution {
public boolean isNumeric(char[] str) {
//标记符号，小数点，e是否出现过
boolean sign=false,decimal=false,hasE=false;
for(int i=0;i<str.length;i++){
if(str[i]=='e' || str[i]=='E'){
if(i==str.length-1)
return false;
if(hasE)
return false;
hasE=true;
}else if(str[i]=='+' || str[i]=='-'){
if(sign && str[i-1]!='e' &&str[i-1]!='E')
return false;
if(!sign && i>0 && str[i-1]!='e' && str[i-1]!='E')
return false;
sign=true;
}else if(str[i]=='.'){
if(hasE || decimal)
return false;
decimal=true;
}else if(str[i]<'0' || str[i]>'9')
return false;
}
return true;
}
}
54.字符流中第一个不重复的字符
题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
思路：
import java.util.*;
public class Solution {
/**
* 因为一个字符不会超过8位，所以创建一个大小为256的整形数组，创建一个list，
* 存放只出现一次的字符，insert时先对该字符所在数组位置数量+1，在判断该位置的值是否为1
* 如果为1，就添加到List中，不为1，则表示该字符已出现不止1次，然后从List中移除
* 取出时先判断List的size是否为0，不为0直接List.get(0),就可以得到结果，否则返回#
* @param ch
*/
int[] arr = new int[256];
List<Character> charList = new ArrayList<Character>();
public void Insert(char ch)
{
arr[ch]++;//先加1
if(arr[ch]==1) {
charList.add(ch);//只出现一次
}else {
charList.remove((Character)ch);//出现多次，移除
}
}
public char FirstAppearingOnce()
{
if(charList.size()==0)
return '#';
else
return charList.get(0);
}
}
55链表中环的入口结点
题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 思路：
* 1.确定链表是否有环，通过两个不同速度的指针确定
* 2.确定环中结点的数目n：指针走一圈，边走边计数
* 3.找到环的入口：从头结点开始，通过两个相差为n的指针来得到
* 即寻找链表中道速第n个结点
* @param pHead
* @return
*/
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode meetNode = meetingNode(pHead);
if(meetNode==null)
return null;
int count=1;
ListNode pNode1=meetNode.next;
while (pNode1!=meetNode){
count++;
pNode1=pNode1.next;
}
//先移动pnode1，次数为count
pNode1=pHead;
for(int i=1;i<=count;i++){
pNode1=pNode1.next;
}
ListNode pNode2=pHead;
while (pNode1!=pNode2){
pNode1=pNode1.next;
pNode2=pNode2.next;
}
return pNode1;
}
//确定链表是否有环，采用快慢指针来确定，返回值代表快慢指针相遇时的结点
private ListNode meetingNode(ListNode head){
if(head==null)
return null;
ListNode pFast=head,pSlow=head;
while (pFast!=null){
pFast=pFast.next;
pSlow=pSlow.next;
if(pFast!=null)
pFast=pFast.next;
if(pSlow!=null && pFast==pSlow){
return pSlow;
}
}
return null;
}
}
56.删除链表重复的结点
题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
if(pHead==null || pHead.next==null)
return pHead;
ListNode head = new ListNode(0);
head.next=pHead;
ListNode pre=head , p=head.next;
while (p!=null){
if(p.next!=null && p.val==p.next.val){
while (p.next!=null && p.val==p.next.val){
p=p.next;
}
pre.next=p.next;
p=p.next;
}else {
p=p.next;
pre=pre.next;
}
}
return head.next;
}
}
57.二叉树的下一个结点
题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：
ublic class Solution {
/*
题目：给定一个二叉树和其中的一个结点，找出中序遍历的下一个结点并返回
思路：中序：左根右
*/
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode==null)
return null;
if(pNode.right!=null){
pNode=pNode.right;
while (pNode.left!=null){
pNode=pNode.left;
}
return pNode;
}
while (pNode.next!=null){
if(pNode.next.left==pNode)
return pNode.next;
pNode=pNode.next;
}
return null;
}
}
58.对称的二叉树
题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot==null)
return true;
return isSysmmetrical(pRoot.left,pRoot.right);
}
private boolean isSysmmetrical(TreeNode L,TreeNode R){
if(L==null && R==null)//左右子树均为空
return true;
if(L==null || R==null)//左右子树只有一个为空
return false;
if(L.val == R.val){//左右子树值相同，递归判断
return isSysmmetrical(L.left,R.right) && isSysmmetrical(L.right,R.left);
}
return false;
}
}
59.按之字形打印二叉树
题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路：
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(pRoot==null)
return res;
queue.add(pRoot);
int rows = 1;
while (!queue.isEmpty()){
ArrayList<Integer> list=new ArrayList();
int size = queue.size();
for(int i=0;i<size;i++){
TreeNode t=queue.poll();
if(rows%2==0){
list.add(0,t.val);
}else{
list.add(t.val);
}
if(t.left!=null){
queue.offer(t.left);
}
if(t.right!=null){
queue.offer(t.right);
}
}
res.add(list);
rows++;
}
return res;
}
}
60把二叉树打印成多行
题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路：层次遍历
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (pRoot==null)
return res;
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();
queue.add(pRoot);
int start=0,end =1;
while (!queue.isEmpty()){
TreeNode t = queue.poll();
list.add(t.val);
start++;
if(t.left!=null)
queue.add(t.left);
if(t.right!=null)
queue.add(t.right);
if(start==end){
end = queue.size();
start=0;
res.add(list);
list = new ArrayList<>();
}
}
return res;
}
}
61.序列化二叉树
题目描述：请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
思路：
public class Solution {
String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root==null){
sb.append("$,");
}else{
sb.append(root.val+",");
sb.append(Serialize(root.left));
sb.append(Serialize(root.right));
}
return sb.toString();
}
int index=0;
TreeNode Deserialize(String str) {
TreeNode node = null;
if(str==null || str.length()==0)
return node;
int start = index;
while (str.charAt(index)!=',')
index++;
if(!str.substring(start,index).equals("$")){
node = new TreeNode(Integer.parseInt(str.substring(start,index)));
index++;
node.left=Deserialize(str);
node.right=Deserialize(str);
}else {
index++;
}
return node;
}
}
62.二叉搜索树的第k个结点
题目描述：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
思路：二叉搜索树按照中序遍历的顺序打印出来正好是排序好的顺序，
所以按照中序遍历顺序找到第k个结点就是结果
public class Solution {
int cnt = 0;//计数
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot!=null){
TreeNode node = KthNode(pRoot.left,k);
if(node!=null)
return node;
cnt++;
if(cnt==k)
return pRoot;
node = KthNode(pRoot.right,k);
if (node!=null)
return node;
}
return null;
}
}
63.数据流中的中位数
题目描述：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路：
import java.util.*;
public class Solution {
/*
思路：先用java集合的PriorityQueue来设置一个小顶堆和大顶堆
主要的思想是：因为要求的是中位数，那么这两个堆，大顶堆用来存放较小的数，从大到小排列
小顶堆存放较大的数，从小到大的顺序排列，显然中位数就是大顶堆的根结点与小顶堆的根结点的平均数
小顶堆中的元素都大于等于大顶堆中的元素，所以每次插值，并不是直接插进去，而是从另一个堆中poll出一个最大（最小）的插值
当数目为偶数时，将这个值插入大顶堆中，再将大顶堆中根结点（即最大值）插入到小顶堆中
当数目为奇数时，将这个值插入到小顶堆中，再将小顶堆中根结点（即最小值）插入到大顶堆中
取中位数时，如果当前这个数为偶数，显然是取小顶堆和大顶堆根结点的平均值，如果是奇数，取小顶堆根结点
*/
//小顶堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
int count=0;//记录个数，奇数个或偶数个
/*
每次插入小顶堆的是当前大顶堆中最大的数
每次插入大顶堆的是当前小顶堆中最小的数
这样保证小顶堆中的数永远大于等于大顶堆中的数
中位数就可以方便的从两者的根结点获取；
*/
public void Insert(Integer num) {
//个数为偶数的话，则先插入到大顶堆中，然后将大顶堆中的最大的数插入到小顶堆中
if(count%2==0){
maxHeap.offer(num);
int max =maxHeap.poll();
minHeap.offer(max);
}else{
//为奇数的话，则先插入到小顶堆中，然后将小顶堆中最小的数插入到大顶堆中
minHeap.offer(num);
int min = minHeap.poll();
maxHeap.offer(min);
}
count++;
}
public Double GetMedian() {
if(count%2==0){
return new Double(minHeap.peek()+maxHeap.peek())/2;
}else{
return new Double(minHeap.peek());
}
}
}
64.滑动窗口的最大值
题目描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路：
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> res = new ArrayList<>();
if(num==null || size<=0 || num.length<size)
return res;
//暴力破解
int len = num.length,maxIndex=len-size;
for(int i=0;i<=maxIndex;i++){
//获取当前序列的最大值
int curMax = num[i];
for(int j=i+1;j<i+size;j++){
curMax=curMax>num[j]?curMax:num[j];
}
res.add(curMax);
}
return res;
}
}
65矩阵中的路径
题目描述：
image.png
思路：
public class Solution {
/*思路：
0.根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次
1.根据行数和列数，遍历数组，先找到一个与str字符串里第一个元素相匹配的元素，进入judge
2.根据i和j先确定一维数组的位置，因为给定的matrix是一个一维数组
3.确定递归终止条件：越界，当前找到的矩阵值不等于数组对应位置的值，已经走过的，这三类情况都直接false，说明此路不通
4.若k，就是待判定的字符串str的索引已经判断到了周围最后一位，此时说明是匹配成功的
5.递归不断的寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到k到达末尾或者不满足递归条件退出
6.走到这一步，说明本次不成功，还原index处的标志位，进入下一轮判断
*/
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
boolean[] flag = new boolean[matrix.length];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
//循环遍历二维数组，找到起点等于str第一个元素的值,再递归判断四周是否有符合条件的-回溯法
if(judge(matrix,i,j,rows,cols,flag,str,0))
return true;
}
}
return false;
}
//初始矩阵，索引行坐标i，索引纵坐标j，矩阵行数，矩阵列数
private boolean judge(char[] matrix,int i,int j,int rows,int cols,
boolean[] flag,char[] str,int k){
//先根据i和j计算匹配的第一个元素转为一维数组的位置
int index = i*cols+j;
//递归终止条件
if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k]
|| flag[index] == true)
return false;
//若k已经到达str末尾了，说明之前的都已经匹配成功了，直接返回true即可
if(k == str.length-1)
return true;
//要走的第一个位置置为true，表示已经走过了
flag[index] = true;
//回溯，递归寻找，每次找到了就给k加一，找不到，还原
if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
judge(matrix,i,j+1,rows,cols,flag,str,k+1) )
{
return true;
}
//走到这，说明这一条路不通，还原，再试其他的路径
flag[index] = false;
return false;
}
}
66.机器人的运动范围
题目描述：
思路：
public class Solution66 {
public int movingCount(int threshold, int rows, int cols)
{
if(rows<=0 || cols<=0 || threshold<0)
return 0;
boolean[][] flag=new boolean[rows][cols];
return helper(threshold,rows,cols,0,0,flag);
}
private int helper(int threshold,int rows,int cols,int row,int col,boolean[][] flag){
//row,col为行、列走的步数,rows，cols为行列数 isVisited是否访问过
//失败条件：行列步数小于0，行列步数大于等于数组行列数，已访问过，或者走的步数位数和大于限制
if(row<0 || col<0 || row>=rows || col>=cols || flag[row][col] || (numSum(row)+numSum(col))>threshold)
return 0;
flag[row][col]=true;
return helper(threshold,rows,cols,row+1,col,flag)+
helper(threshold,rows,cols,row-1,col,flag)+
helper(threshold,rows,cols,row,col+1,flag)+
helper(threshold,rows,cols,row,col-1,flag)+1;
}
//求num的各位之和
private static int numSum(int num){
int sum=0;
while (num>0){
sum+=num%10;
num/=10;
}
return sum;
}
public static void main(String [] args){
System.out.println(numSum(2250));
}
}
67.剪绳子
题目描述：给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
思路：
public class Solution {
//贪婪算法
public int cutRope(int target) {
if (target<2)
return 0;
if (target==2)
return 1;//1*1
if (target==3)
return 2;//2*1
int[] ropes = new int[target+1];
//最优解存储在数组ropes中，数组中第i个元素表示把长度为i的绳子剪成若干段后的乘积最大值
ropes[0]=0;
ropes[1]=1;
ropes[2]=2;
ropes[3]=3;
int max=0;
for(int i=4;i<=target;i++){
for(int j=1;j<=i/2;j++){
int val = ropes[j]*ropes[i-j];
max = max>val?max:val;
}
ropes[i]=max;
}
return ropes[target];
}
}
