腾讯笔试题：100，60，60，（伪100）0，0
第一题：
package com.week.tencent;
import java.util.Scanner;
import java.util.Stack;
/**
* @author ：week
* @date ：Created in 2019-08-17 19:48
* @description：
* @modified By：
* @version: 1.0.0
*/
public class q_1 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str=sc.next();
Stack<String> stack=new Stack<String>();
StringBuffer sb=new StringBuffer();
for(int i=0;i<str.length();i++){
char tmp=str.charAt(i);
if(tmp=='['){
stack.push(tmp+"");
}else if(tmp==']'){
String now="";
while(!stack.peek().equals("[")){
now=stack.pop()+now;
}
stack.pop();
String re=build(now);
if(stack.empty()){
sb.append(re);
}else{
stack.push(re);
}
}else{
if(stack.empty()){
sb.append(tmp);
}else{
stack.push(tmp+"");
}
}
}
System.out.println(sb.toString());
}
public static String build(String str){
String[] arr=str.split("\\|");
int num=Integer.valueOf(arr[0]);
StringBuffer sb=new StringBuffer();
for(int i=0;i<num;i++){
sb.append(arr[1]);
}
return sb.toString();
}
}
第二题：暴力法。
package com.week.tencent;
import java.util.Scanner;
/**
* @author ：week
* @date ：Created in 2019-08-17 19:49
* @description：
* @modified By：
* @version: 1.0.0
*/
public class q_2 {
private static int count = 0;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] num=new int[1<<n];
for(int i=0;i<1<<n;i++){
num[i]=sc.nextInt();
}
int m=sc.nextInt();
int[] q=new int[m];
for(int i=0;i<m;i++){
q[i]=sc.nextInt();
}
for(int i=0;i<m;i++){
if(q[i]!=0){
num=change(num,1<<q[i]);
count=0;
int[] tmp=num.clone();
System.out.println(inversePairs(tmp));
}else{
count=0;
int[] tmp=num.clone();
System.out.println(inversePairs(tmp));
}
}
}
public static int[] change(int[] num,int n){
int[] res=new int[num.length];
for(int i=0;i<num.length;i++){
int a=i/n;
int b=i%n;
res[a*n+(n-1-b)]=num[i];
}
return res;
}
public static int inversePairs(int[] array) {
if (array == null) {
return 0;
}
int len = array.length;
if (len == 0) {
return 0;
}
sort(array, 0, len - 1);
return count;
}
private static void sort(int[] arr, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
sort(arr, start, mid);
sort(arr, mid + 1, end);
merger(arr, start, mid, mid + 1, end);
}
}
private static void merger(int[] arr, int start1, int end1, int start2, int end2) { //归并排序
int len = end2 - start1 + 1;
int [] nums = new int[len];
int k = end2 - start1 + 1;
int i = end1;
int j = end2;
while(i >= start1 && j >= start2){
if(arr[i] > arr[j]){
nums[--k] = arr[i--];
count = count + (j - start2 + 1);
}else{
nums[--k] = arr[j--];
}
}
for( ; i >= start1; i--){
nums[--k] = arr[i];
}
for( ; j >= start2; j--){
nums[--k] = arr[j];
}
for(int m =0; m < len; m++){
arr[start1++] = nums[m];
}
}
}
第三题：贪心排序，暴力扩右边界。
package com.week.tencent;
import java.util.*;
import java.util.concurrent.locks.Condition;
/**
* @author ：week
* @date ：Created in 2019-08-17 19:49
* @description：
* @modified By：
* @version: 1.0.0
*/
public class q_3 {
static class XY{
public int x;
public int y;
public XY(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int L=sc.nextInt();
List<XY> list=new ArrayList<XY>();
for(int i=0;i<n;i++){
int x=sc.nextInt();
int y=sc.nextInt();
XY xy=new XY(x,y);
list.add(xy);
}
Collections.sort(list, new Comparator<XY>() {
@Override
public int compare(XY o1, XY o2) {
if(o1!=o2){
return o1.x-o2.x;
}else{
return o2.y-o2.y;
}
}
});
int R=0;
int count=0;
int i=0;
boolean[] tag=new boolean[n];
while(i<list.size()){
if(R>=L){
break;
}
XY xy=list.get(i);
int max=0;
int max_index=0;
for(int j=0;j<list.size()&&list.get(j).x<=R;j++){
if(!tag[j]){
if(list.get(j).y>max){
max=list.get(j).y;
max_index=j;
}
}
}
if(max<=R){
System.out.println(-1);
return;
}else{
count++;
R=max;
tag[max_index]=true;
}
}
if(R<L){
System.out.println(-1);
}else{
System.out.println(count);
}
}
}
第四题：应该是正确的最优解，但是我把结算的注释1和注释2给搞错顺序了，在交完卷子第12分钟的时候才发现这个问题。。。。
package com.week.tencent;
import java.util.Scanner;
import java.util.Stack;
/**
* @author ：week
* @date ：Created in 2019-08-17 19:49
* @description：
* @modified By：
* @version: 1.0.0
*/
public class q_4 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] w=new int[n];
int[] wz=new int[n];
for(int i=0;i<n;i++){
w[i]=sc.nextInt();
wz[n-1-i]=w[i];
}
int[] L=build(w);
int[] R=build(wz);
for(int i=0;i<n;i++){
System.out.print((L[i]+R[n-1-i]+1)+" ");
}
}
public static int[] build(int[] w){
Stack<Integer> stack=new Stack<Integer>();
stack.push(w[0]);
int[] res=new int[w.length];
for(int i=1;i<w.length;i++){
int count=0;
//直接看不到
if(stack.isEmpty()){
stack.push(w[i]);
res[i]=count;
}else{
//当前小于上一个
if(w[i]<stack.peek()){
res[i]=stack.size();
stack.push(w[i]);
}else if(w[i]==stack.peek()){
res[i]=res[i-1];
}else{
while (!stack.isEmpty()&&stack.peek()<w[i]){
stack.pop();
count++;
}
//注释1
if(stack.isEmpty()){
res[i]=count;
}else{
res[i]=count+1;
}
//注释2
if(stack.isEmpty()||stack.peek()>w[i]){
stack.push(w[i]);
}
}
}
}
return res;
}
}
第五题：暂时想到暴力解，然后优化成dp。。。。一首凉凉送给我自己
拼多多集团-PDD公司福利 474人发布
