45 翻转单词顺序列
student. a am I----->>> I am a student.
public class Solution {
public String ReverseSentence(String str) {
return f1(str.toCharArray());
}
public static String f1(char[] chas)
{
int l=0;
int r=chas.length-1;
reverse(chas,l,r);
int p1=-1;
int p2=-1;
for(int i=0;i<chas.length;i++)
{
if(chas[i]!=' ')
{
p1=i==0||chas[i-1]==' '?i:p1;
p2=i==chas.length-1||chas[i+1]==' '?i:p2;
}
if(p1!=-1&&p2!=-1)
{
reverse(chas,p1,p2);
p1=-1;
p2=-1;
}
}
return String.valueOf(chas);
}
public static void reverse(char[] chas,int l,int r)
{
char tmp=0;
while(l<r)
{
tmp=chas[l];
chas[l]=chas[r];
chas[r]=tmp;
l++;
r--;
}
}
}总结：注意p1和p2的使用一次遍历出结果
题目46 扑克牌顺子
大小王可以看作是任何数字
(只要保证任意两数字的间隙小于等于0的个数即可)
import java.util.Arrays;
public class Solution {
public boolean isContinuous(int [] numbers)
{
if(numbers==null||numbers.length==0) return false;
int big=1;
int small=0;
int countZero=0;
int countInterval=0;
Arrays.sort(numbers);
while(big<=numbers.length-1)
{
if(numbers[small]==0)
{
countZero++;
}
if(numbers[big]==numbers[small]&&numbers[big]!=0) return false;
if(numbers[small]!=0&&numbers[big]!=0)
countInterval+=numbers[big]-numbers[small]-1;
small=big;
big++;
}
if(countInterval<=countZero)
{
return true;
}
return false;
}
}题目47 约瑟夫环问题
题目48 1+2+3+4+....+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
public class Solution {
public int Sum_Solution(int n) {
int res=n;
if(n>0) res+=Sum_Solution(n-1);
return res;
}
}题目49 不用加减乘除做加法
public class Solution {
public int Add(int a,int b) {
int sum=a;
while(b!=0)
{
sum=a^b;
b=(a&b)<<1;
a=sum;
}
return sum;
}
}题目50 把字符串转化为整数
public class Solution {
public int StrToInt(String str) {
if(str==null||str.equals("")) return 0;
char[] chas = str.toCharArray();
if(!isValid(chas)) return 0;
boolean pos=true;
boolean pos2=true;
if(chas[0]=='-')
{
pos=false;
pos2=false;
}else if(chas[0]=='+')
{
pos=true;
pos2=false;
}
int minq=Integer.MIN_VALUE/10;
int minr=Integer.MIN_VALUE%10;
int res=0;
int cur=0;
for(int i=pos2?0:1;i<chas.length;i++)
{
cur='0'-chas[i];
if(res<minq||(res==minq&&cur<minr)) return 0;
res=res*10+cur;
}
if(pos&&res==Integer.MIN_VALUE)
return 0;
return pos?res*-1:res;
}
public static boolean isValid(char[] chas)
{
if(chas[0]!='+'&&chas[0]!='-'&&(chas[0]<'0'||chas[0]>'9'))
{
return false;
}
if((chas[0]=='+'||chas[0]=='-')&&chas.length==1)
{
return false;
}
for(int i=1;i<chas.length;i++)
{
if(chas[i]<'0'||chas[i]>'9')
{
return false;
}
}
return true;
}
}总结：判断合法和防止溢出的方法
题目51 数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || length <= 0) {
return false;
}
for(int i = 0; i < length; i++) {
while(numbers[i] != i) {
if(numbers[i] == numbers[numbers[i]]) {
duplication[0] = numbers[i];
return true;
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
}总结：让原本的数字归位
题目52 构建乘积数组
给定一个数组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]。不能使用除法。
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int n=A.length;
int[] B=new int[n];
if(n!=0)
{
B[0]=1;
for(int i=1;i<n;i++)
{
B[i]=B[i-1]*A[i-1];
}
int temp=1;
for(int j=n-2;j>=0;j--)
{
temp*=A[j+1];
B[j]*=temp;
}
}
return B;
}
}题目53 正则表达式匹配
public class Solution {
public boolean match(char[] s, char[] e)
{
if(s==null||e==null)
{
return false;
}
return isValid(s,e)?process(s,e,0,0):false;
}
public static boolean isValid(char[] s, char[] e)
{
for(int i=0;i<s.length;i++)
{
if(s[i]=='*'||s[i]=='.')
{
return false;
}
}
for(int i=0;i<e.length;i++)
{
if(e[i]=='*'&&(i==0||e[i-1]=='*'))
{
return false;
}
}
return true;
}
public static boolean process(char[] s,char[] e,int si,int ei)
{
if(ei==e.length)
{
return si==s.length;
}
//值和值的匹配
if(ei+1==e.length||e[ei+1]!='*')
{
return si!=s.length&&(e[ei]==s[si]||e[ei]=='.')
&&process(s,e,si+1,ei+1);
}
//如果不是值和值的匹配
while(si!=s.length&&(e[ei]==s[si]||e[ei]=='.'))
{
if(process(s,e,si,ei+2))
{
return true;
}
si++;
}
return process(s,e,si,ei+2);
}
}题目54 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符
串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
public class Solution {
private int index=0;
public boolean isNumeric(char[] str)
{
if(str.length<1)
{
return false;
}
boolean flag=scanInteger(str);
if(index<str.length&&str[index]=='.')
{
index++;
flag=scanUnsignedInteger(str)||flag;
}
if(index<str.length&&(str[index]=='E'||str[index]=='e'))
{
index++;
flag=flag&&scanInteger(str);
}
return flag&&index==str.length;
}
private boolean scanInteger(char[] str)
{
if(index<str.length&&(str[index]=='+'||str[index]=='-'))
{
index++;
}
return scanUnsignedInteger(str);
}
private boolean scanUnsignedInteger(char[] str)
{
int start=index;
while(index<str.length&&str[index]>='0'&&str[index]<='9')
{
index++;
}
return start<index;
}
}题目55 字符流中第一个不重复的字符
题目56 链表中环的入口结点
public class Solution {
public ListNode EntryNodeOfLoop(ListNode head)
{
if(head==null||head.next==null||head.next.next==null) return null;
ListNode p1=head.next;
ListNode p2=head.next.next;
while(p1!=p2)
{
if(p2.next==null||p2.next.next==null) return null;
p1=p1.next;
p2=p2.next.next;
}
p2=head;
while(p1!=p2)
{
p1=p1.next;
p2=p2.next;
}
return p1;
}
}题目57 删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表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;
ListNode last = Head.next;
while (last!=null){
if(last.next!=null && last.val == last.next.val){
// 找到最后的一个相同节点
while (last.next!=null && last.val == last.next.val){
last = last.next;
}
pre.next = last.next;
last = last.next;
}else{
pre = pre.next;
last = last.next;
}
}
return Head.next;
}
}题目58 二叉树的下一个结点
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode head)
{
if(head==null) return null;
if(head.right!=null)
{
return getMostLeft(head.right);
}
else
{
TreeLinkNode parent=head.next;
while(parent!=null&&parent.left!=head)
{
head=parent;
parent=head.next;
}
return parent;
}
}
public static TreeLinkNode getMostLeft(TreeLinkNode head)
{
if(head==null) return null;
while(head.left!=null)
{
head=head.left;
}
return head;
}
}题目60 对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot == null){
return true;
}
return comRoot(pRoot.left, pRoot.right);
}
private boolean comRoot(TreeNode left, TreeNode right) {
// TODO Auto-generated method stub
if(left == null) return right==null;
if(right == null) return false;
if(left.val != right.val) return false;
return comRoot(left.right, right.left) && comRoot(left.left, right.right);
}
}题目61 按之字形顺序打印二叉树
import java.util.ArrayList;
import java.util.LinkedList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode head) {
ArrayList<ArrayList<Integer> > allList=new ArrayList<>();
if(head==null) return allList;
ArrayList<Integer> list=new ArrayList<>();
LinkedList<TreeNode> queue=new LinkedList<>();
queue.add(head);
boolean lr=true;
TreeNode last=head;
TreeNode nextLast=null;
TreeNode cur=null;
while(!queue.isEmpty())
{
if(lr)//如果是true 左--->右
{
cur = queue.pollFirst();
if(cur.left!=null)
{
queue.addLast(cur.left);
nextLast=nextLast==null?cur.left:nextLast;
}
if(cur.right!=null)
{
queue.addLast(cur.right);
nextLast=nextLast==null?cur.right:nextLast;
}
}
else //如果是false 右--->左
{
cur = queue.pollLast();
if(cur.right!=null)
{
queue.addFirst(cur.right);
nextLast=nextLast==null?cur.right:nextLast;
}
if(cur.left!=null)
{
queue.addFirst(cur.left);
nextLast=nextLast==null?cur.left:nextLast;
}
}
list.add(cur.val);
if(cur==last&&!queue.isEmpty())
{
lr=!lr;
last=nextLast;
nextLast=null;
allList.add(new ArrayList<>(list));
list=new ArrayList<>();
}
}
allList.add(new ArrayList<>(list));
return allList;
}
}题目62 按层打印二叉树
import java.util.ArrayList;
import java.util.LinkedList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer>> Print(TreeNode head) {
ArrayList<ArrayList<Integer>> allList=new ArrayList<>();
if(head==null) return allList;
ArrayList<Integer> list=new ArrayList<>();
LinkedList<TreeNode> queue=new LinkedList<>();
queue.add(head);
TreeNode last=head;
TreeNode nextLast=null;
while(!queue.isEmpty())
{
TreeNode cur = queue.pollLast();
list.add(cur.val);
if(cur.left!=null)
{
queue.addFirst(cur.left);
nextLast=cur.left;
}
if(cur.right!=null)
{
queue.addFirst(cur.right);
nextLast=cur.right;
}
if(cur==last&&!queue.isEmpty())
{
allList.add(new ArrayList<>(list));
list=new ArrayList<>();
last=nextLast;
}
}
allList.add(new ArrayList<>(list));
return allList;
}
}题目63 序列化二叉树
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.LinkedList;
public class Solution {
String Serialize(TreeNode head) {
if(head==null) return "#!";
String res=head.val+"!";
res+=Serialize(head.left);
res+=Serialize(head.right);
return res;
}
TreeNode Deserialize(String str) {
String[] strs=str.trim().split("!");
LinkedList<String> queue=new LinkedList<>();
for(int i=0;i<strs.length;i++)
{
queue.add(strs[i]);
}
TreeNode head = f(queue);
return head;
}
public static TreeNode f(LinkedList<String> list)
{
String cur = list.poll();
if(cur.equals("#"))
{
return null;
}
TreeNode head=new TreeNode(Integer.parseInt(cur));
head.left=f(list);
head.right=f(list);
return head;
}
}题目64 二叉搜索树的第K个结点
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode KthNode(TreeNode head, int k)
{
if(head==null) return null;
TreeNode cur1=head;
TreeNode cur2=null;
while(cur1!=null)
{
cur2=cur1.left;
if(cur2!=null)
{
while(cur2.right!=null&&cur2.right!=cur1)
{
cur2=cur2.right;
}
if(cur2.right==null)
{
cur2.right=cur1;
cur1=cur1.left;
continue;
}
else
{
cur2.right=null;
}
}
k--;//System.out.println(cur1.value);
if(k==0)
{
return cur1;
}
cur1=cur1.right;
}
return null;
}
}题目65 数据流中的中位数
import java.util.*;
public class Solution {
private PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(new MaxHeapComparator());
private PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>(new MinHeapComparator());
private void modifyTwoHeapSize()
{
if(this.maxHeap.size()==this.minHeap.size()+2)
{
this.minHeap.add(this.maxHeap.poll());
}
if(this.maxHeap.size()+2==this.minHeap.size())
{
this.maxHeap.add(this.minHeap.poll());
}
}
public void Insert(Integer num) {
//最开始，向大顶堆中添加
if(this.maxHeap.isEmpty())
{
this.maxHeap.add(num);
return ;
}
//如果小于大顶堆的头，我们向大顶堆中添加
if(this.maxHeap.peek()>=num)
{
this.maxHeap.add(num);
}else //如果大于大顶堆的头
{
//如果小顶堆为空
if(this.minHeap.isEmpty())
{
this.minHeap.add(num);
return ;
}
if(this.minHeap.peek()>num)
{
this.maxHeap.add(num);
}else
{
this.minHeap.add(num);
}
}
modifyTwoHeapSize();
}
public Double GetMedian() {
int maxHeapSize=this.maxHeap.size();
int minHeapSize=this.minHeap.size();
if(maxHeapSi***HeapSize==0) return (double)0;
Integer maxHeapHead=this.maxHeap.peek();
Integer minHeapHead=this.minHeap.peek();
if(((maxHeapSi***HeapSize)&1)==0)
{
double f=(double)(maxHeapHead+minHeapHead)/2;
return f;
}
int res=maxHeapSi***HeapSize?maxHeapHead:minHeapHead;
double resd=(double)res;
return resd;
}
public static class MaxHeapComparator implements Comparator<Integer>
{
@Override
public int compare(Integer o1, Integer o2) {
if(o2>o1)
{
return 1;
}else
{
return -1;
}
}
}
public static class MinHeapComparator implements Comparator<Integer>
{
@Override
public int compare(Integer o1, Integer o2) {
if(o2<o1)
{
return 1;
}else
{
return -1;
}
}
}
}题目66 滑动窗口的最大值
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] arr, int k)
{
ArrayList<Integer> list=new ArrayList<>();
if(k==0) return list;
LinkedList<Integer> queue=new LinkedList<>();
for(int i=0;i<arr.length;i++)
{
while(!queue.isEmpty()&&arr[queue.peekLast()]<=arr[i])
{
queue.pollLast();
}
queue.addLast(i);
if(queue.peekFirst()<=i-k)
{
queue.pollFirst();
}
if(i>=k-1)
{
list.add(arr[queue.peekFirst()]);
}
}
return list;
}
}
京公网安备 11010502036488号