数据结构与算法 2

数据结构与算法 2

目录

双链表

栈

两数之和

回文数

双链表

实现一个双链表，双链表初始为空，支持 55 种操作：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 kk 个插入的数删除；
4. 在第 kk 个插入的数左侧插入一个数；
5. 在第 kk 个插入的数右侧插入一个数

现在要对该链表进行 MM 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 kk 个插入的数并不是指当前链表的第 kk 个数。例如操作过程中一共插入了 nn 个数，则按照插入的时间顺序，这 nn 个数依次为：第 11 个插入的数，第 22 个插入的数，…第 nn 个插入的数。

输入格式

第一行包含整数 MM，表示操作次数。

接下来 MM 行，每行包含一个操作命令，操作命令可能为以下几种：

1. L x，表示在链表的最左端插入数 xx。
2. R x，表示在链表的最右端插入数 xx。
3. D k，表示将第 kk 个插入的数删除。
4. IL k x，表示在第 kk 个插入的数左侧插入一个数。

import java.util.Scanner;public class Main{static int[] a=new int [100010];static int[] l=new int [100010];static int[] r=new int [100010];static int  idx=0;static void initial(){r[0]=1;l[1]=0;idx=2;}static void sert(int k,int x)//右侧插入{a[idx]=x;r[k]=idx;l[idx]=k;l[r[k]]=idx;r[idx]=r[k];idx++;}static void remove(int k){l[r[k]]=l[k];r[l[k]]=r[k];}public static void main(String[] args) {Scanner input =new Scanner(System.in);int m;m&#Int();while(m>0){String s; s&#();int x,k;if(s.equals("L") ){x&#Int();sert(0,x);}else if(s.equals("R") ){x&#Int();sert(l[1],x);}else if(s.equals("IR") ){x&#Int();k&#Int();sert(k+1,x);}else if(s.equals("IR")) {x&#Int();k&#Int();sert(l[k+1],x);}else  if(s.equals("D")){k&#Int();remove(k+1);}m--;}}}

栈

表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1231−1。
• 题目中的整除是指向 00 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=15/3=1，对于小于 00 的结果向上取整，例如 5/(1−4)=−15/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

#include <iostream>
//#include <string>
#include <stack>
#include <unordered_map>using namespace std;stack<int> num;
stack<char> op;
unordered_map<char,int > pr={{'+',1},{'-',1},{'*',2},{'/',2}};void eval()
{int b = p(); num.pop();int a = p(); num.pop();char c = op.top(); op.pop();int x;if(c == '+') x = a + b;else if(c == '-') x = a - b;else if(c == '*') x = a * b;else x = a / b;num.push(x);
}int main()
{string s;cin >> s;for(int i=0; i<s.size();i++){char c=s[i];if(isdigit(c)) {int x=0,j=i;while(j<s.size()&&isdigit(s[j])) x=10*x+s[j]-'0';i=j-1;num.push(x);}else if(c=='(') op.push(c);else if(c==')')  {while(op.size() &&p()!='(') eval(),op.pop();else{  if(op.size()&&p()]>=pr[c]) eval();op.push(c);}}while(op.size()) eval();cout<&p();return 0;
}

两数之和

双指针

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

class Solution {int [] a=new int[2];public int[] twoSum(int[] nums, int target) {a=new int[2];for(int i=0;i<nums.length;i++){for(int j=nums.length-1;j>i;j--){if(nums[i]+nums[j]==target){a[0]=i;a[1]=j;return a; }}}return a;}
}

回文数

双指针解

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

class Solution {public boolean isPalindrome(int x) {if(x<0) return false;else if(x<10) return true;else{String s=String.valueOf(x);char c[]&#CharArray();for(int i=0,j=c.length-1;i<=j;i++,j--)if(c[i]!=c[j]) return false;return true;}}
}