栈

1. 栈 求众数(出现次数是大于n/2 )

双重循环遍历是对数组普适的办法,而方法的巧妙正在于一次遍历

wulinshan / 这里的c就是竞争力,帮派人数,也是出栈入栈的日常

int wulinshan;
    for(int i=0,c=0; i<n; i++)
    {
       if( c == 0){//如果武林山上没有人
           wulinshan = a[i]; //登上武林山大喊一声，老子是众数帮，你们TM是谁
           c = 1; //此人代表的帮派有一个人站在山上了        
       }
       else{
           if( wulinshan == a[i])//如果是同一个帮派的
               c ++; //谁不服我们？
           else
               c --;
       }
    }
    printf("%d",wulinshan);

摩尔投票法

package edu.yihui.myTry;
 
import java.util.Scanner;
public class Main2 {
    //求一个数里面出现次数超过一半的数
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int len = input.nextInt();
        int[] a = new int[len];
        for(int i = 0; i < len;i++){
            a[i] = input.nextInt();
        }
        //设置两个变量统计数组中哪两个元素出现次数最多（两个投票候选人）
        //开始时都赋值为数组的第一个元素（假设第一个元素出现次数最多）
        int num1=a[0];
        int num2=a[0];
        //设置两个计数变量统计元素出现次数
        int cnt1 =0; 
        int cnt2 =0; 
        //核心是通过比较各自的"投票数"/优势,找到出现次数最多的两个元素
        for(int i=0;i<len;i++){
            if(a[i] == num1){
                cnt1++;
                continue;
            }
            if(a[i] == num2){
                cnt2++;
                continue;
            }
            if(cnt1 == 0){
                num1 = num2;
                num2 = a[i];
                int tmp = cnt1;
                cnt1 = cnt2;
                cnt2 = tmp;
                //num1 = a[i];
                //以上不是简单的调换,为了让即使num1先失去了优势,num1始终处于num2之前
                cnt1++;
                continue;
            }
            if(cnt2 == 0){
                num2 = a[i];
                cnt2++;
                continue;
            }
            cnt1--;
            cnt2--;
        }
        cnt1 = 0;cnt2 =0; 
        for(int i = 0; i < len; i++){
            if(a[i] == num1){
                cnt1++;
            }else if(a[i] == num2){
                cnt2++;
            }
        }
        if(cnt1 >len/3){
            System.out.print(num1+" ");
        }
        if(cnt1 >len/3){
            System.out.println(num2);
        }
        input.close();
    }
}                 

2. 对栈的操作

----从对数组的操作转向,后面是Queue,Tree & Graph吧?而这些都是数据与数据的关系.

输入两个整数序列（int类型），第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

从题目到思路 通过手动模拟正确的出入栈操作得到思路: 遍历pop序列,也就是正在测试的出栈序列:

1. 如果要弹出的这个元素在栈顶⇒弹出
2. 如果要弹出的这个不在栈顶, - 按压入顺序将下一个压入,一直压到这个数字再弹出 - 如果压不到这个数字/压入弹出不对,说明出栈序列不对⇐翻译成code语言就是： 如果是空，就返回false;否则继续压入 从步骤到代码

• 输入:压栈顺序数组/出栈顺序数组/数组长度
• 输出:判断出栈顺序
• 参与方：
  1. 需要有一个judge栈：与pop序列中的元素比较，使得push序列中的元素出栈入栈然后判断
  2. 可以再多两个栈放入pop序列和push序列，然后按照pop序列的指示push入judge栈与judge栈再pop
• 过程中涉及到哪些辅助/标志的东西？
  1. 辅助标记把push栈哪些已经入了judge栈，下次从这里继续入—push_location

Code

import java.util.*;
 
public class StackJudge{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        List<Integer> list_push= new ArrayList<Integer>();
        System.out.println("请输入压栈序列:");
        int n = in.nextInt();
        while(n!=-1){
            list_push.add(n);
            n  = in.nextInt();
        }
        // for (int i=0;i<list_push.size();i++)
        //     System.out.print(lisoInEyXfht_push.get(i));
        List<Integer> list_pop= new ArrayList<Integer>();
        System.out.println("请输入弹栈序列:");
        n = in.nextInt();
        while(n!=-1){
            list_pop.add(n);
            n  = in.nextInt();
        }
        int[] pushorder = new int[list_push.size()];
        for(int i=0; i<list_push.size();i++){
            pushorder[i] = list_push.get(i);
        }
        int[] poporder = new int[list_pop.size()];
        for(int i=0;i<list_pop.size();i++)
            poporder[i] = list_pop.get(i);
        System.out.println("出栈顺序是正确的吗?:\n"+judgePop(pushorder, poporder,list_push.size()));
        in.close();
    }
    public static Boolean judgePop(int[] pushorder,int[] poporder,int length){
        if(pushorder == null || poporder == null || length<=0) return false;
        Stack<Integer> stack_judge = new Stack<Integer>();
        Stack<Integer> stack_push = new Stack<Integer>();
        Stack<Integer> stack_pop = new Stack<Integer>();
        //注意从length-1到i>=0,对于这种栈的题目,把数组放入栈之后真的就不需要数组了
        for(int i=length-1; i>=0; i--)
        stack_push.push(pushorder[i]);
        for(int i=length-1; i>=0; i--)
        stack_pop.push(poporder[i]);
        // for(int i=length-1; i>=0; i--)
        //     System.out.println(poporder[i]);
 
 
        int push_location = 0;
        //刚开始judge是空的,因此必须先把push中的元素入judge栈
        for(int i=0;i< length;i++){// 把flag的那个放入的话,当i=5的时候就已经越界了,尽管不会进入循环
            stack_judge.push(stack_push.peek());
            // System.out.println("<"+stack_judge.peek()+">");
            stack_push.pop();
            push_location++;
            if( stack_judge.peek() == stack_pop.peek())  break;
        } 
        while(!stack_judge.empty()){
            if(stack_judge.peek() == stack_pop.peek() && !stack_judge.empty()){
                // System.out.println("<>"+stack_judge.peek()+"<>");
                stack_judge.pop();
                stack_pop.pop();
            }else if(stack_judge.peek() != stack_pop.peek()){
            
                if(!stack_push.empty()){
                    for(int i= push_location; i<length;i++){
                        stack_judge.push(stack_push.peek());
                        // push_location用来辅助标记把push栈加到了什么地方
                        push_location++;
                        // System.out.println("<<"+stack_judge.peek()+">>");
                        stack_push.pop();
                        if( stack_judge.peek() == stack_pop.peek() ) break;
                    }
                }else
                    return false;
            }
        }
        if(stack_judge.empty()) return true;
 
    }
    return false;
}

另外看一下同样的思路可以表达的多么简洁…

public static boolean judgePop(int[] pushorder, int[] poporder){
        if(pushorder == null || pushorder.length ==0 ) return false;
        Stack<Integer> stack = new Stack<>();
        int temp = 0;
        for(int i = 0; i < pushorder.length;i++){
            stack.push(pushorder[i]);
            while(stack.empty() ==false && stack.peek() == poporder[temp]){
                stack.pop();
                temp++;
            }
        }
        return stack.empty() == true;
    }

究其原因,好吧不知道,不过可以积累这样简洁的表达,多看优秀代码,就像用成语表达一些描述一样.

3. 求回文不用stack和queue

 
import java.util.*;
public class Test {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s = input.nextLine();
 
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
        }
        String stest = sb.reverse().toString();
        
        System.out.println(stest.equals(s) ? "是回文" : "不是");
        input.close();
    }
}

4. 快速排序重新用栈写

#include <cstdio>
#include <stack>
#include <iostream>
using namespace std;
typedef struct l_h_f{
    int l;
    int h;
    int flag;
}l_h_f;
void QuickSort_stack(int a[],int low,int high){
    stack<l_h_f> cs;
    l_h_f ini = {0,0,-1};cs.push(ini);//指令初始化,栈底
    l_h_f n1 = {low,high,0};cs.push(n1);//第一次划分开始指令
    while(true){//用无限循环模拟递归调用
        l_h_f n2 = cs.top();cs.pop();
        low=n2.l;high=n2.h;
        // flag指示low与high的比较状态,以便跳到下一次或者跳出
        if(n2.flag == 0){
            if(low>=high){
                l_h_f n3 = {0,0,1};cs.push(n3);
                continue;
            }
            int i = low; int j = high;
            int pivot = a[low];
            // 以下为快排扫描调换
            while(i<j){
                while(i<j && a[j]>=pivot) --j;
                if(i<j) a[i]=a[j];
                while(i<j && a[i]<pivot) ++i;
                if(i<j) a[j]=a[i];
            }
            a[i]=pivot;
            l_h_f n4={0,0,0};
            n4.l=low;n4.h=i-1;
            cs.push(n4);// 给定下一次划分的范围
            n4.l=i+1;n4.h=high;
            cs.push(n4);
        }else if(n2.flag ==1 ) 
            continue;
        else if(n2.flag == -1 )   
            break;
    }
}
``