Click "Niuke | daily question" to eliminate it

Author's brief introduction ： One likes to write , Sophomore rookie of planning major

Personal home page ：starry Lu Li

First date ：2022 year 7 month 25 Monday, Sunday

Last article ：『 Cattle guest | A daily topic 』 Pressure into the stack 、 Pop-up sequence _

Subscription column ：『 Collection of Niuke brush questions 』

Daily recommendation ： Basic algorithm is a very important part in both graduate interview and job interview , Here we recommend an algorithm interview artifact ： Cattle from - Interview artifact ; Algorithm problems can only be kept thinking and feeling by brushing more and more frequently , Let's move quickly （ reminder ： The common interview question bank is also very nice Oh ）

If the article helps you, remember to praise + Collect and support

1. A daily topic

Original link ： Portal -》 Poke me

2. Their thinking

2.1 Thought analysis

Because the adjacent and same characters are eliminated every time , So we consider using stack ： Traversal string , Every time you encounter the same character as the top of the stack, the top of the stack element is out of the stack , The stack is empty or the current character is different from the top element , It into the stack

• step 1： Introducing auxiliary stack stk, Traversal string , Every time Encountered the same character as the top of the stack Stack the top element
• step 2： The stack is empty or the current character is different from the top element , Stack the current element
• step 3： Output results , Stack empty description is finally empty string , Direct output 0
• step 4： If It's not empty string Just introduce a stack to reverse the character output

2.2 Core code

import java.util.Scanner;
import java.util.Stack;

public class Main5 {
    

	public static void main(String[] args) {
    
		Scanner scanner = new Scanner(System.in);
		// Get input 
		String s=scanner.next();
		// Auxiliary stack 
		Stack<Character>stk=new Stack<Character>();
		// Traversal string , If the current character is not equal to the top of the stack, it will be put on the stack , If it is equal, the element at the top of the stack is out of the stack 
		for(int i=0;i<s.length();++i) {
    
			char a=s.charAt(i);
			if(stk.isEmpty()||a!=stk.peek()) {
    
				stk.push(a);
			}else if(a==stk.peek()) {
    
				stk.pop();
			}
		}
		// Output processing 
		// Stack empty description is finally empty string , Output 0
		if(stk.isEmpty()) {
    
			System.out.println("0");
		}else {
    // If it is not an empty string, then introduce a stack to reverse the character output 
			Stack<Character>stk2=new Stack<Character>();
			while(!stk.isEmpty()) {
    
				stk2.push(stk.pop());
			}
			while(!stk2.isEmpty()) {
    
				System.out.print(stk2.pop());
			}
		}
		scanner.close();

	}

}

2.3 Train of thought expansion

This question uses java The stack in the collection class actually brings inconvenience to our output , When outputting elements, you also need to introduce an auxiliary stack to reverse the elements . A more concise approach is to be direct use StringBuffer String concatenation , Delete the string to simulate stacking , Out of the stack . The idea is the same .

/** * @author starry */
import java.util.Scanner;

public class Main51 {
    

	public static void main(String[] args) {
    
		Scanner scanner = new Scanner(System.in);
		String s=scanner.next();
		int len=s.length();
		// use StringBuffer String concatenation , Delete the string to simulate stacking , Out of the stack 
		StringBuffer sbf=new StringBuffer(len);
		//index Express “ To the top of the stack ” Element subscript . Initial stack empty , Subscript to be -1
		int index=-1;
		// Traversal string 
		for(int i=0;i<len;++i) {
    
			// The current character 
			char ch=s.charAt(i);
			//“ Stack ” Empty or the current element and “ To the top of the stack ” Elements are not equal , The stack , also “ To the top of the stack ” Subscript ++
			if(index==-1||ch!=sbf.charAt(index)) {
    
				sbf.append(ch);
				index++;
			}else {
    
				// Current element and “ To the top of the stack ” The elements are equal ,“ To the top of the stack ” Element out of stack , also “ To the top of the stack ” Subscript minus 1
				sbf.deleteCharAt(index);
				index--;
			}
		}
		if(index==-1) {
    
			System.out.println("0");
		}else {
    
			System.out.println(sbf);
		}
		scanner.close();
//ahoy-starry
	}

}

Subscription column ：『 Collection of Niuke brush questions 』

Daily recommendation ： Basic algorithm is a very important part in both graduate interview and job interview , Here we recommend an algorithm interview artifact ： Cattle from - Interview artifact ; Algorithm problems can only be kept thinking and feeling by brushing more and more frequently , Let's move quickly （ reminder ： The common interview question bank is also very nice Oh ）

If the article helps you, remember to praise + Collect and support