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

2021-11-17 13:31:39

剑指Offer（四十五）：扑克牌顺子

1、排序

2、计算所有相邻数字间隔总数

3、计算0的个数

4、如果2、3相等，就是顺子

5、如果出现对子，则不是顺子

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;
    }
}

剑指Offer（四十六）：孩子们的游戏（圆圈中最后剩下的数）

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;
    }
}

剑指Offer（四十七）：求1+2+3+…+n

解题思路：
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;
    }

&&就是逻辑与，逻辑与有个短路特点，前面为假，后面不计算。

剑指Offer（四十八）：不用加减乘除的加法

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;
    }
}

链接：https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215

来源：牛客网

首先看十进制是如何做的： 5+7=12，三步走

第一步：相加各位的值，不算进位，得到2。

第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。

第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。

第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。

第三步重复上述两步，各位相加 010^1010=1000，进位值为100=(010&1010)<<1。

继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

剑指Offer（五十四）：字符流中第一个不重复的字符

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;
    }
}

剑指Offer（六十三）：数据流中的中位数

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());
        }
    }


}

剑指Offer（六十四）：滑动窗口的最大值

//经典的暴力破解的方法

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;
    }
}

//使用一个队列来解决，让O(kn)变为O(n)

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;
    }
}

回溯法（两道）

（一）：矩阵中的路径【回溯法】

占坑，以后写

（二）：机器人的运动范围【回溯法】