中国建设监理协会网站投稿,文山知名网站建设报价,怎么用7牛云做网站,夜夜夜在线观看文章目录 1. 栈结构例题1#xff1a;字符串括号匹配例题2#xff1a;最小栈例题3#xff1a;逆波兰表达式求值例题4#xff1a;下一个更大元素 2. 队列结构题目1: 实现一个队列#xff0c;包括入队和出队操作#xff0c;并判断队列是否为空。题目2: 判断给定的字符串是否… 文章目录 1. 栈结构例题1字符串括号匹配例题2最小栈例题3逆波兰表达式求值例题4下一个更大元素 2. 队列结构题目1: 实现一个队列包括入队和出队操作并判断队列是否为空。题目2: 判断给定的字符串是否是回文字符串。题目3: 使用队列实现栈。题目4: 使用队列实现猫狗队列可以按顺序存储猫和狗并可以按顺序弹出猫和狗。 2. 堆结构例题一使用堆结构实现一个最小堆例题二使用堆结构实现一个优先级队列 4. 链表结构1. 反转链表2. 删除链表的倒数第N个节点3. 合并两个有序链表4. 判断链表是否有环5. 返回链表的中间节点6. 删除链表中的重复元素 5. hash思想题目一找出数组中重复的数字题目二找出数组中只出现一次的数字题目三找出字符串中第一个不重复的字符 1. 栈结构
例题1字符串括号匹配
import java.util.Stack;public class BracketMatching {public static boolean isBracketMatching(String s) {StackCharacter stack new Stack();for (char c : s.toCharArray()) {if (c ( || c { || c [) {stack.push(c);} else {if (stack.isEmpty()) {return false;}char top stack.pop();if ((c ) top ! () || (c } top ! {) || (c ] top ! [)) {return false;}}}return stack.isEmpty();}public static void main(String[] args) {String s1 {[()]}; // validString s2 {[(])}; // invalidString s3 ()[]{}; // validSystem.out.println(isBracketMatching(s1)); // output: trueSystem.out.println(isBracketMatching(s2)); // output: falseSystem.out.println(isBracketMatching(s3)); // output: true}
}例题2最小栈
import java.util.Stack;public class MinStack {private StackInteger stack;private StackInteger minStack;public MinStack() {stack new Stack();minStack new Stack();}public void push(int x) {stack.push(x);if (minStack.isEmpty() || x minStack.peek()) {minStack.push(x);}}public void pop() {if (stack.pop().equals(minStack.peek())) {minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}public static void main(String[] args) {MinStack minStack new MinStack();minStack.push(3);minStack.push(5);minStack.push(2);System.out.println(minStack.getMin()); // output: 2minStack.pop();System.out.println(minStack.top()); // output: 5System.out.println(minStack.getMin()); // output: 3}
}例题3逆波兰表达式求值
import java.util.Stack;public class EvaluateReversePolishNotation {public static int evalRPN(String[] tokens) {StackInteger stack new Stack();for (String token : tokens) {if (token.equals() || token.equals(-) || token.equals(*) || token.equals(/)) {int b stack.pop();int a stack.pop();switch (token) {case :stack.push(a b);break;case -:stack.push(a - b);break;case *:stack.push(a * b);break;case /:stack.push(a / b);break;}} else {stack.push(Integer.parseInt(token));}}return stack.pop();}public static void main(String[] args) {String[] tokens1 {2, 1, , 3, *}; // (2 1) * 3 9String[] tokens2 {4, 13, 5, /, }; // 4 (13 / 5) 6System.out.println(evalRPN(tokens1)); // output: 9System.out.println(evalRPN(tokens2)); // output: 6}
}例题4下一个更大元素
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;public class NextGreaterElement {public static int[] nextGreaterElement(int[] nums) {int[] result new int[nums.length];Arrays.fill(result, -1);StackInteger stack new Stack();MapInteger, Integer map new HashMap();for (int i 0; i nums.length; i) {while (!stack.isEmpty() nums[i] nums[stack.peek()]) {int index stack.pop();result[index] nums[i];}stack.push(i);}for (int i 0; i nums.length; i) {while (!stack.isEmpty() nums[i] nums[stack.peek()]) {int index stack.pop();result[index] nums[i];}}return result;}public static void main(String[] args) {int[] nums1 {4, 2, 5, 7}; // output: [5, 5, 7, -1]int[] nums2 {3, 1, 2, 4}; // output: [4, 2, 4, -1]int[] result1 nextGreaterElement(nums1);int[] result2 nextGreaterElement(nums2);System.out.println(Arrays.toString(result1));System.out.println(Arrays.toString(result2));}
}2. 队列结构
题目1: 实现一个队列包括入队和出队操作并判断队列是否为空。
public class Queue {private int[] data; // 存储队列元素的数组private int front; // 队首指针private int rear; // 队尾指针public Queue(int size) {data new int[size];front 0;rear -1;}public boolean isEmpty() {return rear -1;}public void enqueue(int value) {data[rear] value;}public int dequeue() {int value data[front];if (front rear) {front 0;rear -1;}return value;}
}题目2: 判断给定的字符串是否是回文字符串。
import java.util.LinkedList;public class Palindrome {public static boolean isPalindrome(String str) {LinkedListCharacter queue new LinkedList();// 将字符串的每个字符入队for (int i 0; i str.length(); i) {queue.addLast(str.charAt(i));}// 依次出队和字符串的每个字符比较for (int i 0; i str.length(); i) {if (queue.removeFirst() ! str.charAt(i)) {return false;}}return true;}
}题目3: 使用队列实现栈。
import java.util.LinkedList;public class Stack {private LinkedListInteger queue;public Stack() {queue new LinkedList();}public void push(int value) {queue.addLast(value);}public int pop() {if (queue.isEmpty()) {throw new IllegalStateException(Stack is empty.);}// 将队列中除最后一个元素外的所有元素出队并入队实现栈的后进先出特性int size queue.size();for (int i 0; i size - 1; i) {int value queue.removeFirst();queue.addLast(value);}return queue.removeFirst();}public int top() {if (queue.isEmpty()) {throw new IllegalStateException(Stack is empty.);}return queue.getLast();}public boolean isEmpty() {return queue.isEmpty();}
}题目4: 使用队列实现猫狗队列可以按顺序存储猫和狗并可以按顺序弹出猫和狗。
import java.util.LinkedList;public class AnimalQueue {private LinkedListAnimal catQueue;private LinkedListAnimal dogQueue;private int order;public AnimalQueue() {catQueue new LinkedList();dogQueue new LinkedList();order 0;}public void enqueue(Animal animal) {animal.setOrder(order);if (animal instanceof Cat) {catQueue.addLast(animal);} else if (animal instanceof Dog) {dogQueue.addLast(animal);}}public Animal dequeueAny() {if (catQueue.isEmpty() dogQueue.isEmpty()) {throw new IllegalStateException(No animals in the queue.);} else if (catQueue.isEmpty()) {return dogQueue.removeFirst();} else if (dogQueue.isEmpty()) {return catQueue.removeFirst();} else {if (catQueue.getFirst().getOrder() dogQueue.getFirst().getOrder()) {return catQueue.removeFirst();} else {return dogQueue.removeFirst();}}}public Cat dequeueCat() {if (catQueue.isEmpty()) {throw new IllegalStateException(No cats in the queue.);}return (Cat) catQueue.removeFirst();}public Dog dequeueDog() {if (dogQueue.isEmpty()) {throw new IllegalStateException(No dogs in the queue.);}return (Dog) dogQueue.removeFirst();}
}class Animal {private String name;private int order;public Animal(String name) {this.name name;}public String getName() {return name;}public int getOrder() {return order;}public void setOrder(int order) {this.order order;}
}class Cat extends Animal {public Cat(String name) {super(name);}
}class Dog extends Animal {public Dog(String name) {super(name);}
}2. 堆结构
例题一使用堆结构实现一个最小堆
import java.util.ArrayList;
import java.util.List;public class MinHeap {private ListInteger heap;public MinHeap() {heap new ArrayList();}// 获取父节点索引private int getParentIndex(int childIndex) {return (childIndex - 1) / 2;}// 获取左孩子节点索引private int getLeftChildIndex(int parentIndex) {return 2 * parentIndex 1;}// 获取右孩子节点索引private int getRightChildIndex(int parentIndex) {return 2 * parentIndex 2;}// 上浮操作将新插入的元素与父节点比较如果小于父节点就交换位置直到满足最小堆的性质private void siftUp(int index) {while (index 0) {int parentIndex getParentIndex(index);if (heap.get(index) heap.get(parentIndex)) {swap(index, parentIndex);index parentIndex;} else {break;}}}// 下沉操作将顶部元素与左右孩子节点中较小的比较如果大于孩子节点就交换位置直到满足最小堆的性质private void siftDown(int index) {int leftChildIndex getLeftChildIndex(index);int rightChildIndex getRightChildIndex(index);int smallestIndex index;if (leftChildIndex heap.size() heap.get(leftChildIndex) heap.get(smallestIndex)) {smallestIndex leftChildIndex;}if (rightChildIndex heap.size() heap.get(rightChildIndex) heap.get(smallestIndex)) {smallestIndex rightChildIndex;}if (smallestIndex ! index) {swap(index, smallestIndex);siftDown(smallestIndex);}}// 交换两个元素的位置private void swap(int index1, int index2) {int temp heap.get(index1);heap.set(index1, heap.get(index2));heap.set(index2, temp);}// 插入元素public void insert(int value) {heap.add(value);siftUp(heap.size() - 1);}// 删除并返回堆顶元素public int deleteMin() {if (heap.isEmpty()) {throw new IllegalStateException(Heap is empty);}int minValue heap.get(0);heap.set(0, heap.get(heap.size() - 1));heap.remove(heap.size() - 1);siftDown(0);return minValue;}// 获取堆的大小public int size() {return heap.size();}// 判断堆是否为空public boolean isEmpty() {return heap.isEmpty();}// 打印堆中的元素public void printHeap() {for (int i 0; i heap.size(); i) {System.out.print(heap.get(i) );}System.out.println();}
}例题二使用堆结构实现一个优先级队列
import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {// 创建一个优先级队列PriorityQueueInteger priorityQueue new PriorityQueue();// 添加元素到优先级队列priorityQueue.offer(5);priorityQueue.offer(3);priorityQueue.offer(8);priorityQueue.offer(1);priorityQueue.offer(2);// 打印优先级队列中的元素System.out.println(Priority Queue: priorityQueue);// 获取并移除优先级队列中的最小元素int minElement priorityQueue.poll();System.out.println(Minimum Element: minElement);// 打印优先级队列中的元素System.out.println(Priority Queue: priorityQueue);}
}这是一个使用Java内置的PriorityQueue类实现的优先级队列示例。使用PriorityQueue的offer()方法可以添加元素到队列中poll()方法可以获取并移除队列中的最小元素。
4. 链表结构
1. 反转链表
class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}public class ReverseLinkedList {public ListNode reverseList(ListNode head) {ListNode prev null; // 前驱节点ListNode curr head; // 当前节点while (curr ! null) {ListNode nextTemp curr.next; // 保存当前节点的下一个节点curr.next prev; // 当前节点的指针指向前驱节点prev curr; // 前驱节点向后移动curr nextTemp; // 当前节点向后移动}return prev; // 返回反转后的头节点}
}2. 删除链表的倒数第N个节点
class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}public class RemoveNthNodeFromEnd {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(0); // 创建虚拟头节点dummy.next head;ListNode first dummy; // 快指针ListNode second dummy; // 慢指针for (int i 0; i n; i) {first first.next; // 快指针先向后移动n步}while (first ! null) {first first.next; // 快指针继续向后移动second second.next; // 慢指针向后移动}second.next second.next.next; // 删除倒数第N个节点return dummy.next; // 返回头节点}
}3. 合并两个有序链表
class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}public class MergeTwoSortedLists {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy new ListNode(0); // 创建虚拟头节点ListNode curr dummy; // 当前节点while (l1 ! null l2 ! null) {if (l1.val l2.val) {curr.next l1; // 将l1节点接到当前节点后面l1 l1.next; // l1节点向后移动} else {curr.next l2; // 将l2节点接到当前节点后面l2 l2.next; // l2节点向后移动}curr curr.next; // 当前节点向后移动}if (l1 ! null) {curr.next l1; // 将剩余的l1节点接到当前节点后面}if (l2 ! null) {curr.next l2; // 将剩余的l2节点接到当前节点后面}return dummy.next; // 返回合并后的头节点}
}4. 判断链表是否有环
class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}public class LinkedListCycle {public boolean hasCycle(ListNode head) {if (head null || head.next null) {return false; // 链表为空或只有一个节点不可能有环}ListNode slow head; // 慢指针ListNode fast head.next; // 快指针while (slow ! fast) {if (fast null || fast.next null) {return false; // 快指针走到链表尾部不存在环}slow slow.next; // 慢指针向后移动一步fast fast.next.next; // 快指针向后移动两步}return true; // 快慢指针相遇存在环}
}5. 返回链表的中间节点
class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}public class MiddleOfLinkedList {public ListNode middleNode(ListNode head) {ListNode slow head; // 慢指针ListNode fast head; // 快指针while (fast ! null fast.next ! null) {slow slow.next; // 慢指针移动一步fast fast.next.next; // 快指针移动两步}return slow; // 返回中间节点}
}6. 删除链表中的重复元素
class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}public class RemoveDuplicatesFromSortedList {public ListNode deleteDuplicates(ListNode head) {ListNode curr head;while (curr ! null curr.next ! null) {if (curr.val curr.next.val) {curr.next curr.next.next; // 删除重复节点} else {curr curr.next; // 不重复节点向后移动}}return head; // 返回头节点}
}5. hash思想
题目一找出数组中重复的数字
问题描述给定一个整数数组数组中有些数字是重复的找出数组中任意一个重复的数字。
解决思路使用哈希思想可以借助集合(Set)来模拟哈希表遍历数组将数字放入集合中如果集合中已经存在该数字则找到了重复的数字。
import java.util.HashSet;public class DuplicateNumbers {public static int findDuplicate(int[] nums) {// 创建一个集合用于存储已经遍历过的数字HashSetInteger set new HashSet();// 遍历数组将数字放入集合中for (int num : nums) {// 如果集合中已经存在该数字返回该数字if (set.contains(num)) {return num;}// 将数字放入集合中set.add(num);}// 如果没有找到重复的数字则返回-1return -1;}public static void main(String[] args) {int[] nums {2, 3, 1, 0, 2, 5, 3};int duplicate findDuplicate(nums);System.out.println(Duplicate Number: duplicate);}
}题目二找出数组中只出现一次的数字
问题描述给定一个整数数组数组中有两个数字只出现了一次其他数字都出现了两次请找出这两个只出现一次的数字。
解决思路使用哈希思想可以借助集合(Set)来模拟哈希表遍历数组将数字放入集合中如果集合中已经存在该数字则从集合中移除该数字最后集合中剩余的两个数字就是只出现一次的数字。
import java.util.HashSet;public class SingleNumbers {public static int[] findSingleNumbers(int[] nums) {// 创建一个集合用于存储只出现一次的数字HashSetInteger set new HashSet();// 遍历数组将数字放入集合中或从集合中移除for (int num : nums) {// 如果集合中已经存在该数字将其从集合中移除if (set.contains(num)) {set.remove(num);} else {// 否则将数字放入集合中set.add(num);}}// 将集合中的数字转化为数组并返回int[] result new int[2];int index 0;for (int num : set) {result[index] num;index;}return result;}public static void main(String[] args) {int[] nums {2, 3, 1, 0, 2, 5, 3};int[] singleNumbers findSingleNumbers(nums);System.out.println(Single Numbers: singleNumbers[0] , singleNumbers[1]);}
}题目三找出字符串中第一个不重复的字符
问题描述给定一个字符串找出字符串中第一个不重复的字符并返回其索引。
解决思路使用哈希思想可以借助数组来模拟哈希表遍历字符串统计每个字符出现的次数然后再次遍历字符串找到第一个出现次数为1的字符返回其索引。
public class FirstUniqueCharacter {public static int firstUniqChar(String s) {// 创建一个长度为26的数组用于统计每个字符出现的次数int[] count new int[26];// 第一次遍历字符串统计每个字符出现的次数for (char c : s.toCharArray()) {count[c - a];}// 第二次遍历字符串找到第一个出现次数为1的字符返回其索引for (int i 0; i s.length(); i) {if (count[s.charAt(i) - a] 1) {return i;}}// 如果字符串中没有不重复的字符则返回-1return -1;}public static void main(String[] args) {String s leetcode;int index firstUniqChar(s);System.out.println(First Unique Character Index: index);}
}
