+关注继续查看

# Datawhale 系列数据结构

#### 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(){
cnt = 0;
}

public void push(T 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 方法:

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]；

*/
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();
}


#### 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;
}

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(){
cnt = 0;
size = 10;
}

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;
}
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 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) {
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--;
return true;
}

/**
* Get the front item from the queue.
*/
public int Front() {
if (count == 0 ) {
return -1;
}
}

/**
* 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 tail;
/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
numbers=new int[k+1];
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{
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{
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;
}

/** 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() {
}

/** Checks whether the circular deque is full or not. */
public boolean isFull() {
}
}
//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];
}
}
int[] res = new int[nums.length - k + 1];//要返回的结果数据
res[0] = max;
for(int i = k; i < nums.length;i++){
int z =list.remove(0);//移走第一位数并插入新的一位数
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){
}
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++){
}

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];
}
}


15 0

40 0

186 0
【热点】Salesforce的敏捷数据开发

150 0

Datawhale 系列数据结构 Task3.1 排序 3.1.1归并 //采用分治(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全的序列 public static int [] mergeSort(int []arr){ int len =arr.
1319 0
Redis指令与数据结构（二）
0、Redis目录结构       1）Redis介绍及部署在CentOS7上（一）       2）Redis指令与数据结构（二）       3）Redis客户端连接以及持久化数据（三）       4）Redis高可用之主从复制实践（四）       5）Redis高可用之哨兵模式Sentinel配置与启动（五）       6）Redis高可用之集群配置（六）   一、前言 上一篇介绍了《Redis介绍及部署在CentOS上》，相必大家对redis有一定的了解了，Redis使用的场景非常的多，比如 之前 手机营销活动的秒杀等。
714 0
Android官方DataBinding（二）：动态数据更新notifyPropertyChanged
Android官方DataBinding（二）：动态数据更新notifyPropertyChanged 附录文章1使用了最简单的Android官方DataBinding技术，所以写的例子以简单明了能说明问题即可。
1138 0
+关注

11

100