Datawhale 系列数据结构
Task2.1 栈
2.1.1用数组实现一个顺序栈
public class ArrayStack<T> {
private T [] data;
private int size;
private int cnt;
@SuppressWarnings("unchecked")
public ArrayStack(){
data= (T[]) new Object [10];
cnt = 0;
size =10;
}
public void push(T t){
if(cnt>=size){
data=Arrays.copyOf(data, data.length*2);
size*=2;
}
data[size] = t;
cnt++;
}
public T peek(){
if (cnt==0) {
throw new EmptyStackException();
}
return data[cnt];
}
public T pop(){
if (cnt==0) {
throw new EmptyStackException();
}
cnt--;
return data[cnt];
}
public int search(T t){
for(int i=cnt;i>0;i--){
if(data[i]==t)
return i;
}
return -1;
}
public boolean isEmpty(){
return cnt==0;
}
}
2.1.2 用链表实现一个链式栈
public class ListStack<T> {
private List<T> data;
private int cnt;
public ListStack(){
data= new LinkedList<T>();
cnt = 0;
}
public void push(T t){
data.add(t);
cnt++;
}
public T peek(){
if (cnt==0) {
throw new EmptyStackException();
}
return data.get(cnt);
}
public T pop(){
if (cnt==0) {
throw new EmptyStackException();
}
T t=data.remove(cnt);
cnt--;
return t;
}
public int search(T t){
for(int i=cnt;i>0;i--){
if(data.get(i)==t)
return i;
}
return -1;
}
public boolean isEmpty(){
return cnt==0;
}
}
2.1.3 编程模拟实现一个浏览器的前进后退功能
public class BrowserSimula {
public static void main(String[] args) {
Browser b1=new Browser();
b1.open();
b1.open();
b1.open();
b1.open();
System.out.println(b1.backward());
System.out.println(b1.backward());
System.out.println(b1.forward());
System.out.println(b1.forward());
}
}
class Browser{
private Stack<Integer> s1;
private Stack<Integer> s2;
int cnt;
Browser(){
s1=new Stack<Integer>();
s2=new Stack<Integer>();
cnt=0;
}
/**
* 点开一个新的链接
*/
public void open(){
cnt++;
s1.push(cnt);
}
//后退
public Integer backward(){
if(cnt==0)
throw new ArrayIndexOutOfBoundsException(cnt);
Integer a =s1.pop();
s2.push(a);
return s1.peek();
}
//前进
public Integer forward(){
if(s2.isEmpty())
throw new ArrayIndexOutOfBoundsException(cnt);
Integer a =s2.pop();
s1.push(a);
return a;
}
}
2.1.4 练习
//Valid Parentheses（有效的括号）
private HashMap<Character, Character> mappings;
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (this.mappings.containsKey(c)) {
char topElement = stack.empty() ? '#' : stack.pop();
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
//Longest Valid Parentheses（最长有效的括号）[作为可选]
/*dp 方法:
我们用 dp[i] 表示以 i 结尾的最长有效括号；
1 当 s[i] 为 ( , dp[i] 必然等于0,因为不可能组成有效的括号;
2 那么 s[i] 为 )
2.1 当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2；
2.2 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；
时间复杂度：O(n)
*/
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) return 0;
int[] dp = new int[s.length()];
int res = 0;
for (int i = 0; i < s.length(); i++) {
if (i > 0 && s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2);
} else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
//Evaluate Reverse Polish Notatio（逆波兰表达式求值）
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0 ;i < tokens.length;i++){
String str = tokens[i];
if (str.length() == 1){
char ch = str.charAt(0);
if (ch-'0' >= 0 && ch - '0' <= 9 ){
Integer a = Integer.valueOf(str);
stack.push(a);
}
else{
if (stack.size() < 2)
return 0;
int num2 = stack.pop();
int num1 = stack.pop();
switch(ch){
case '+':
stack.push(num1 + num2);
break;
case '-':
stack.push(num1 - num2);
break;
case '*':
stack.push(num1 * num2);
break;
case '/':
stack.push(num1 / num2);
break;
}
}
}else{
int n = Integer.valueOf(str);
stack.push(n);
}
}
return stack.pop();
}
TASK2.2 队列
2.2.1 用数组实现一个顺序队列
public class ArrayQueue<T> {
private T [] data ;
private int cnt;//元素个数
private int size;//队列长度
@SuppressWarnings("unchecked")
public ArrayQueue(){
data =(T[]) new Object [10];
cnt = 0;
size = 10;
}
@SuppressWarnings("unchecked")
public ArrayQueue(int size){
data =(T[]) new Object [size];
cnt = 0;
this.size = size;
}
public void add(T t){
if(cnt>=size){
throw new IllegalStateException();
}
data[cnt]=t;
cnt++;
}
public T remove(){
if(cnt<0){
throw new NoSuchElementException();
}
T t= data[0];
data = Arrays.copyOfRange(data,0,size);
cnt--;
return t;
}
public boolean offer(T t){
if(cnt>=size){
return false;
}
data[cnt]=t;
cnt++;
return true;
}
public boolean pull(T t){
if(cnt<0){
return false;
}
data = Arrays.copyOfRange(data,0,size);
cnt--;
return true;
}
//返回队列头元素
public T element(){
return data[0];
}
public boolean isEmpty(){
return cnt==0 ;
}
public boolean isFull(){
return cnt==size;
}
}
2.2.2 用链表实现一个链式队列
public class ListQueue<T> {
private List<T> data ;
private int cnt;//元素个数
private int size;//队列长度(用链表的话这里可以强行定义)
public ListQueue(){
data =new LinkedList<T>();
cnt = 0;
size = 10;
}
public void add(T t){
data.add(t);
cnt++;
}
public T remove(){
if(cnt<0){
throw new NoSuchElementException();
}
T t= data.remove(cnt);
cnt--;
return t;
}
public boolean offer(T t){
if(cnt>=size){
return false;
}
data.add(t);
cnt++;
return true;
}
public boolean pull(T t){
if(cnt<0){
return false;
}
data.remove(cnt);
cnt--;
return true;
}
//返回队列头元素
public T element(){
return data.get(0);
}
public boolean isEmpty(){
return cnt==0 ;
}
public boolean isFull(){
return cnt==size;
}
}
2.2.3 实现一个循环队列
public class MyCircularQueue {
private final int capacity;
private final int[] array;
private int head = 0;
private int tail = 0;
private int count = 0;
/**
* Initialize your data structure here. Set the size of the queue to be k.
*/
public MyCircularQueue(int k) {
this.capacity = k;
this.array = new int[this.capacity];
}
/**
* Insert an element into the circular queue. Return true if the operation is successful.
*/
public boolean enQueue(int value) {
//队列已满
if (count == capacity) {
return false;
}
//队列为空, 重新设置头部
if (count == 0) {
head = (head == capacity) ? 0 : head;
tail = head;
array[head] = value;
count++;
return true;
}
//队列未满 (有空位)
if (tail == capacity - 1) {
//tail 达到 maxIndex, 重置为 0
tail = 0;
} else {
//tail 未达到 maxIndex, tail++
tail++;
}
array[tail] = value;
count++;
return true;
}
/**
* Delete an element from the circular queue. Return true if the operation is successful.
*/
public boolean deQueue() {
if (count == 0) {
//队列为空
return false;
}
count--;
head++;
return true;
}
/**
* Get the front item from the queue.
*/
public int Front() {
if (count == 0 ) {
return -1;
}
return array[head];
}
/**
* Get the last item from the queue.
*/
public int Rear() {
if (count == 0 ) {
return -1;
}
return array[tail];
}
/**
* Checks whether the circular queue is empty or not.
*/
public boolean isEmpty() {
return count == 0;
}
/**
* Checks whether the circular queue is full or not.
*/
public boolean isFull() {
return count == capacity;
}
}
2.2.4 练习
//Design Circular Deque（设计一个双端队列）
class MyCircularDeque {
public int k;
public int[] numbers;
public int head;
public int tail;
/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
numbers=new int[k+1];
head=0;
tail=0;
this.k=k;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {
if(isFull())
return false;
else{
head=(head+k)%(k+1);
numbers[head]=value;
return true;
}
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
public boolean insertLast(int value) {
if(isFull())
return false;
else{
numbers[tail]=value;
tail=(tail+1)%(k+1);
return true;
}
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {
if(isEmpty())
return false;
else{
head=(head+1)%(k+1);
return true;
}
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
if(isEmpty())
return false;
else{
tail=(tail+k)%(k+1);
return true;
}
}
/** Get the front item from the deque. */
public int getFront() {
if(isEmpty())
return -1;
return numbers[head];
}
/** Get the last item from the deque. */
public int getRear() {
if(isEmpty())
return -1;
return numbers[(tail+k)%(k+1)];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
return tail==head;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull() {
return (tail+1)%(k+1)==head;
}
}
//Sliding Window Maximum（滑动窗口最大值）
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(k==0){
return new int[0];
}
List<Integer> list = new ArrayList<>();//存放窗口内的数字
int max = Integer.MIN_VALUE;//窗口内的最大数字
for(int i = 0; i<k;i++){
if(max<nums[i]){
max = nums[i];
}
list.add(nums[i]);
}
int[] res = new int[nums.length - k + 1];//要返回的结果数据
res[0] = max;
for(int i = k; i < nums.length;i++){
int z =list.remove(0);//移走第一位数并插入新的一位数
list.add(nums[i]);
if(z!=max){//移走的数不是max，只需判断max与新插入的数哪个大
if(nums[i]> max){
max = nums[i];
}
res[i-k+1] = max;
}else{//移走的数是max，重新判断列表中哪个数是最大的
if(!list.contains(max)){
max = Integer.MIN_VALUE;
for(Integer num : list){
if(max<num){
max = num;
}
}
}else{
if(nums[i]> max){
max = nums[i];
}
}
}
res[i-k+1] = max;
}
return res;
}
}
3 递归
3.1 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)
public static int Fibe(int n){
if(n==1) return 1;
if(n==2) return 1;
return Fibe(n-1)+Fibe(n-2);
}
3.2 编程实现求阶乘 n!
public static int factorial(int n){
if(n==1) return 1;
return factorial(n-1)*n;
}
3.3 编程实现一组数据集合的全排列
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
permition(nums, 0, nums.length-1);
return res;
}
public void permition(int[] nums, int p, int q){
if(p==q){
res.add(arrayToList(nums));
}
for(int i = p; i <= q; i++){
swap(nums, i, p);
permition(nums, p+1, q);
swap(nums, i,p);
}
}
private List<Integer> arrayToList(int[] nums){
List<Integer> res = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
res.add(nums[i]);
}
return res;
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
3.4 练习
// Climbing Stairs（爬楼梯）
//直接递归，但是直接递归leetcode竟然不能通过，于是又方法2
class Solution {
public int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
}
//非递归放啊
class Solution {
public int climbStairs(int n) {
int [] ways = new int[n+1];
ways[0] = 0;
for (int i = 1;i<ways.length;i++){
if (i < 3 ){
ways[i] = i;
}else {
ways[i] = ways[i-1] + ways[i-2];
}
}
return ways[n];
}
}
