LeetCode 剑指offer 简单篇（更新中）

class Solution {
    public String replaceSpace(String s) {
        //K神思路：在java中　String是字符串常量，不可变对象，无法直接修改字符串的某一位，需要新建一个可以修改的字符串对象进行替换。遍历字符串，放入res中，如果某个字符为' ',append("%20")
        //知识点：
        //关于StringBUffer 和StringBuilder
        //StringBuffer字符串变量，线程安全，支持多线程，若需要经常对字符串进行改变，用它，转换为string对象使用toString()方法，append(E)在末端添加元素，insert(index,E)在指定地点添加元素。相当于全局变量。
        //StringBuilder 一般用在内部，线程不安全，相当于'+',用完可以丢弃。
        
        //关于char和character
        //char是基本数据类型，Character是其包装器类，实例化出来的叫对象。
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c==' '){
                sb.append("%20");
            }else{
                sb.append(c);
            }
        }    
        return sb.toString();
    }
}

class Solution {
    public int[] reversePrint(ListNode head) {
        //我的思路：一涉及到反转，一般都会用到栈这个数据结构，后进先出。
        Deque <Integer> stack=new LinkedList<>();
        while(head!=null){
            stack.push(head.val);
            head=head.next;
        }
        int []res=new int[stack.size()];
        for(int i=0;i<res.length;i++){
            res[i]=stack.pop();
        }
        return res;
    }
}

 class Solution {
    public int[] reversePrint(ListNode head) {
        //把head当哨兵，让node去走循环，得到链表的长度len
        ListNode node=head;
        int len=0;
        while(node!=null){
            node=node.next;
            len++;
        }
        //定义res,倒叙构造res
        int [] res=new int[len];
        for(int i=len-1;i>=0;i--){
            res[i]=head.val;
            head=head.next;
        }
        return res;
    }
 }

class CQueue {
//我的思路：先定义两个栈，栈是后进先出的，实现队列，先进先出，前出后进，然后实现插入删除方法
//不要直接用stack做，速度慢。原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。
//可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。
//s1,s2放外边大家都能用
    Deque<Integer> s1;
    Deque<Integer> s2;
    public CQueue() {
        //实例化对象
        s1=new LinkedList<>();
        s2=new LinkedList<>();
    }
    
    public void appendTail(int value) {
        //放入第一个栈
        s1.push(value);
    }
    
    public int deleteHead() {
        /*删除元素的原则：只有当输出栈为空时候，才将输入栈的元素导入，否则先输出输出栈中的元素 */

        //当输出栈为空,且输入栈不为空时
        if(s2.isEmpty()&& !s1.isEmpty()){//判断栈空的方法isEmpty()
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
            return s2.pop();
        }else if(s1.isEmpty() && s2.isEmpty()){//输出栈为为空，输入栈为空
            return -1;
        }else {//输出栈不为空
            return s2.pop();
        }  
        
    }
}

class CQueue {
// 栈（stack）：先进后出
// 队列(queue)：先进先出
// Deque接口，是queue接口的子接口，是指队列两端的元素，既能入队（offer）也能出队。
// 如果将Deque限制为只能从一端进行入队，和出队，就是栈的数据结构的实现。对于栈而言，有入栈（push）和出栈（pop），遵循先进后出的规则
//Java的集合类并没有单独的Stack接口，因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。
// 当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，那样会破坏栈的本质。

// 用两个栈实现队列时，使用deque
// 这道题中定义栈的方法
// Deque <Integer> stack=new LinkedList<>();

// java语言不使用这种方法普通定义栈的方法
// Stack<Integer> stack=new Stack<>()

// 普通定义队列的方法
// Queue <Integer> queue=new LinkedList<>();


// 这道题的解题思路
// 两个栈s1,s2 因为栈的特性是先进后出，队列的特性是后进先出
// 一个栈s1实现插入，一个栈s2实现删除 
// s1直接入栈 s1.push()一个元素
// s2删除元素，s1入栈直接压到栈底了，所以会后出，将s1中的元素一个个的pop到s2中，后进s1的元素就被压到s2栈底了
// 有一个问题是，当s2中有元素，又向s1push 了新的元素，但是按理说应该s2中的元素按先进先出的规则先走，要注意的是，当s2不为空时，s1不许向里压栈，只有s2空了，才允许向里填s1中的所有元素
// 判断为空s.isEmpty(),是true,否false
// 定义两个栈
    //定义两个公共变量s1,s2
    Deque<Integer> s1;
    Deque<Integer> s2;
    public CQueue(){
        s1=new LinkedList<>();
        s2=new LinkedList<>();
    }
    public void appendTail(int value){
        s1.push(value);
    }
    public int deleteHead(){
        //当s2不为空时
        //栈的判空isEmpty()
        if(!s2.isEmpty()){
            return s2.pop();
        }
        //当s2为空时 当s1不为空时
        if(s2.isEmpty() &&!s1.isEmpty() ){
            
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
            return s2.pop();
        }
        //当s1s2为空，返回-1
      return -1;
        

    }
}

class Solution {
    public int fib(int n) {
        //我的思路：迭代的思路在里边，最后一个元素的值与前两个元素的有关，那么我把前俩个元素的值存起来即可。
        //特殊情况先输出
        if(n==0){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }
        int [] res=new int[3];
        res[0]=0;
        res[1]=1;
        res[2]=1;
        for(int i= 3;i<=n;i++){
            res[0]=res[1];
            res[1]=res[2];
            res[2]=(res[0]+res[1])%1000000007;//记得题目要求的取余
        }
        return res[2];
    }
}

class Solution {
    public int fib(int n) {
        //方法一、动态规划
        if(n==0){
            return 0;
        }
        if(n==1){
           return 1;
        }
        //字符串长度是可以变化的
        int [] dp= new int [n+1];
        dp[0]=0;
        dp[1]=1;
        //取余符号%
        for(int i=2;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%(1000000007);
        }
        return dp[n];


        
        // //方法二、递归
        // //如果n=1或者2时
        // if(n==1 || n==2){
        //     return 1;
        // }
        // //把最开始两个数组存储起来
        // int a=0,b=1;
        // int ans=0;
        // for(int i=2;i<=n;i++){
        // ans=(a+b)%(1000000007);
        // a=b;
        // b=ans;
        // }
        
        // return ans;

    }
      
}

class Solution {
    public int numWays(int n) {
        //我的思***蛙的最后一跳有两种情况，跳一阶或者跳两阶，所以只要求出青蛙跳倒数第一阶之前的方法+跳倒数第二阶之前的方法之和，即可获得青蛙跳台阶的方法。还是一个递归的问题，最后一跳需要前边跳法递归而来。f(n)=f(n-1)+f(n-2),跟斐波那契数列一模一样。
        int []dp=new int[n+1];//把0阶台阶也算上，对应着好看
        if(n==0||n==1){
            return 1;
        }
        //0阶台阶，1种；一阶台阶，1中；二阶台阶，2种
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];

    }
}

class Solution {
    public int minArray(int[] numbers) {
        //思路：旋转数组最开始是一个升序数组，当这个数组整个进行旋转时返回原数组。第一个值就是最小值（特殊情况）。
        //部分旋转：当后边的一个值小于前边的值时，说明后边那个值就是最小值，返回后边那个值即可。
        
        int res=-1;
        //部分旋转
        for(int i=0;i<numbers.length-1;i++){
            if(numbers[i]>numbers[i+1]){
              res=numbers[i+1];
              return res;
              }
        }
        //完全旋转
        return numbers[0];
    }
}

class Solution {
        public int minArray(int[] numbers) {
            //二分法思路：双指针i,j指向数组两端，其中mid=i+(j-i)/2。
            //当numbers[mid]>numbers[j]时，m在大数组中，所求最小的值在[mid+1,j]中，令i=mid+1
            //当numbers[mid]<numbers[j]时，m在小数组中，所求最小值在[i,m],令j=mid;
            //当numbers[mid]=numbers[j]时，最小值不能确定在哪边，比如[5,4,4,4,4]和[1,2,2,2,2]，执行j=j-1,打破这个平衡,然后继续比较。
            //当i=j时跳出循环，返回numbers[j]即可。
            int i=0,j=numbers.length-1;
            while(i<j){
                int mid=i+(j-i)/2;//如果是(i+j)/2,可能会出现越界问题
                if(numbers[mid]>numbers[j]){
                    i=mid+1;
                }else if(numbers[mid]<numbers[j]){
                    j=mid;
                }else{
                    j=j-1;
                }
            }
            return numbers[j];
        }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //思路：题干说32位的二进制数，遍历这个二进制数32次，用二进制数最后一位进行异或操作，如果等于1，cnt++;二进制数进行右移，进行下次循环
        

        int cnt=0;
        for(int i=0;i<32;i++){
            if((n&1)==1){//判断当前位是否为1，&运算都为1才等于1
                cnt++;
            }
            //n进行右移1位，比较下一位,前边缺少的用0补上
            n=n>>>1;
        }
        return cnt;

    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //二进制中的与 或 非 异或
        //与& 全1则1
        //或| 有1则1
        //非~ 按位取反   ~10000 =01111
        //异或^  相同取0，不同取1  
        //位移运算：常见有左位移（<<<），与右位移（>>>）简单说就是将一个二级制数中的1向左或向右移动若干位，多余的位用0补齐

        //若 n& 1 = 0,则 n 二进制 最右一位 为 0；
        //若 n & 1 = 1,则 n 二进制 最右一位 为 1 。
        //&只能比较最后一位的，然后需要进行右移，移过的位置用0补齐

        int cnt=0;
        for(int i=0;i<32;i++){
            //用小括号括起来
            if((n &1) ==1){
                cnt++;
            }
            //比较完一次之后，将n右移一位，比较下一位，格式如下
            n=n>>>1;
        }
        return cnt;
    }
}

class Solution {
    public int[] printNumbers(int n) {
    //Math.pow(底数,几次方)
    // 如：int a=3;
    //int b=3;
    //int c=(int)Math.pow(a,b);
    //就是3的三次方是多少；a、b及函数值都是double型,强制装换成int类型的
        int len=(int)Math.pow(10,n)-1;
        int [] res=new int[len];
        for(int i=0;i<len;i++){
            res[i]=i+1;
        }
        return res;
    }
}