剑指offer刷题记录 其他、回溯（3）

import java.util.Arrays;
public class Solution {
    public boolean isContinuous(int [] numbers) {
        if(numbers.length==0||numbers==null)
            return false;
        int length=numbers.length;
        int ZeroOfNumber=0;
        int IntervalOfNumber=0;
        Arrays.sort(numbers);
        for(int i=0;i<length-1;i++){
            if(numbers[i]==0){
                ZeroOfNumber++;
                continue;
            }
            if(numbers[i]==numbers[i+1])
                return false;
            IntervalOfNumber+=numbers[i+1]-numbers[i]-1;
        }
        if(ZeroOfNumber>=IntervalOfNumber){
            return true;
        }
       return false;
    }
}

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(m<1||n<1){
            return -1;
        }
        //针对于这个题，首先捋一下思路;n:表示数组的大小 m:表示 
        /用数组模拟链表，定义一个环，如果到m，则设置为-1;如果遇到-1则跳过；
        int[] a=new int[n];   /定义一个数组模拟环
        int i=-1,step=0,count=n;
        while(count>0){
            i++;
            if(i>=n) i=0;
            if(a[i]==-1) continue;
            step++;
            if(step==m){
                a[i]=-1;
                step=0;
                count--;
            }
        }
        return i;
    }
}

解题思路：
1.需利用逻辑与的短路特性实现递归终止。 2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；
3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。
    public int Sum_Solution(int n) {
      int sum = n;
      boolean ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
      return sum;
    }

public class Solution {
    public int Add(int num1,int num2) {
        while (num2!=0) {
            int temp = num1^num2;
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
}

Solution: Java版的，使用一个HashMap来统计字符出现的次数，同时用一个ArrayList来记录输入流，每次返回第一个出现一次的字符都是在这个ArrayList（输入流）中的字符作为key去map中查找。
import java.util.*;
public class Solution {
    HashMap<Character, Integer> map=new HashMap();
    ArrayList<Character> list=new ArrayList<Character>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(map.containsKey(ch)){
            map.put(ch,map.get(ch)+1);
        }else{
            map.put(ch,1);
        }
        list.add(ch);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    { char c='#';
      for(char key : list){
            if(map.get(key)==1){
                c=key;
                break;
            }
        }
        return c;
    }
}

import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    /首先定义一个 最小堆  即升序
    PriorityQueue<Integer> minHeap=new PriorityQueue();    //定义最小堆 
    /接着定义一个 最大堆  即降序
    PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(21,new Comparator<Integer>(){    //定义最大堆
        public int compare(Integer o1,Integer o2){
            return o2-o1;
        }
    });
    int count=0;
    public void Insert(Integer num) {
        if(count%2==1){     /当为偶数的时候，插入小根堆
            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(maxHeap.peek()+minHeap.peek())/2;
        }else{
            return new Double(maxHeap.peek());
        }
    }
}

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(num.length==0||num==null||(num.length<size)||size==0)
            return list;
        for(int i=0;i<num.length-size+1;i++){
            int temp=num[i];
            for(int j=i+1;j<i+size;j++){
                if(temp<num[j])
                    temp=num[j];
            }
            list.add(temp);
        }
        return list;
    }
}

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        /*
        用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口欢动一次
        1.判断当前最大值是否过期
        2.新增加的值从队尾开始比较，把所有比他小的值丢掉
        */
        ArrayList<Integer> res=new ArrayList<Integer>();     //定义一个数组，来添加程序
        if(size==0) return res;                              //返回size的大小
        int begin;
        LinkedList<Integer> q=new LinkedList<Integer>();     //定义一个双边链表
        for(int i=0;i<num.length;i++){
            begin=i-size+1;
            if(q.isEmpty()){
                q.add(i);             加进去的是下标
            }else if(begin>q.peekFirst())   /判断当前值是否过期 
                q.pollFirst();
            while((!q.isEmpty())&&num[q.peekLast()]<=num[i])
                q.pollLast();
            q.add(i);
            if(begin>=0){
                res.add(num[q.peekFirst()]);
            }
        }
        return res;
    }
}