疫情已经好转，待工在家很迷茫，看完快手4月，5月的Java岗面经的整理，准备上战场。一面：

1

2

3

4

5

6

7

8

9

10

11

12

1lock指令

对volatile修饰的变量，执行写操作的话，JVM会发送一条lock前缀指令给CPU，CPU在计算完之后会立即将这个值写回主内存，同时因为有MESI缓存一致性协议，所以各个CPU都会对总线进行嗅探，自己本地缓存中的数据是否被别人修改

如果发现别人修改了某个缓存的数据，那么CPU就会将自己本地缓存的数据过期，然后这个CPU上执行的线程在读取那个变量的时候，就会从主内存重新加载最新的数据。

lock前缀指令 + MESI缓存一致性协议

（2）内存屏障：禁止重排序

底层就是插入了XX内存屏障，XX内存屏障，就可以保证指令不会重排

对于volatile修改变量的读写操作，都会加入内存屏障

1

2

SELECT stu.id, stu.name FROM stu, stu_score WHERE stu_score.coursename = '计算机'

AND stu_score.score <60 AND stu.id = stu_score.stuid

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Singleton{

    public static volatile Singleton uniqueInstance;

    public static Singleton getUniqueInstance(){

        if(uniqueInstance==null){

            synchronized(Singleton.class){

                if(uniqueInstance==null){

                    uniqueInstance=new Singleton();

                }

            }

        }

        return uniqueInstance;

    }

    public static void main(String args[]){

        for(int i=0;i<50;i++){

            new Thread(new Runnable(){

                public void run(){

                    System.out.println(Thread.currentThread().getName()+":"+Singleton.getUniqueInstance().hashCode());

                }

            }).start();

        }

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

public class ArrayBlockingQueueDemo {

    private ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue(3, true);

    public static void main(String[] args) {

        ArrayBlockingQueueDemo test = new ArrayBlockingQueueDemo();

        Consumer c1 = test.new Consumer();//内部非静态类实例化方式

        Producer p1 = test.new Producer();

        ExecutorService service = Executors.newCachedThreadPool();

        service.execute(p1);

        service.execute(c1);

        //new Thread(p1).start();

        //new Thread(c1).start();

    }

    class Consumer extends Thread {

        @Override

        public void run() {

            try {

                while (true) {

                    System.out.println("消费" + blockingQueue.take());

                    if (blockingQueue.size() == 0) {

                        System.out.println("队列为空，阻塞");

                    }

                }

            } catch (InterruptedException e1) {

                System.out.println("消费者等待时被打断");

                e1.printStackTrace();

            }

        }

    }

    class Producer extends Thread {

        private int element = 0;

        @Override

        public void run() {

            try {

                while (element < 20) {

                    System.out.println("生产" + element);

                    blockingQueue.put(element++);

                }

                if (blockingQueue.size() == 20) {

                    System.out.println("队列满，阻塞");

                }

            } catch (InterruptedException e) {

                System.out.println("生产者等空闲时被打断");

                e.printStackTrace();

            }

            System.out.println("终止生产");

        }

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

public class ProducerAndConsumer {

    private int number = 0;

    private final int MAX = 10;

    private final int MIN = 0;

    private Lock lock = new ReentrantLock();

    private Condition condition = lock.newCondition();

    public static void main(String args[]) {

        ProducerAndConsumer test = new ProducerAndConsumer();

        Consumer c1 = test.new Consumer();

        Producer p1 = test.new Producer();

        ExecutorService service = Executors.newCachedThreadPool();

        for (int i = 0; i < 10; i++) {

            service.execute(p1);

        }

        for (int i = 0; i < 5; i++) {

            service.execute(c1);

        }

    }

    class Producer extends Thread {

        public void run() {

            try {

                lock.lock();

                while (number >= MAX) {//不用if是因为可能有错误唤醒的线程，while可以进行多次判断

                    System.err.println("产品已满");

                    condition.await();

                }

                number++;

                System.out.println("生产了一个产品，现在有：" + number + "个产品");

                condition.signalAll();

            } catch (InterruptedException e) {

                e.printStackTrace();

            } finally {

                lock.unlock();

            }

        }

    }

    class Consumer extends Thread {

        public void run() {

            try {

                lock.lock();

                while (number <= MIN) {

                    condition.await();

                }

                number--;

                System.out.println("消费了一个，现在有" + number);

                condition.signalAll();

            } catch (InterruptedException e) {

                e.printStackTrace();

            } finally {

                lock.unlock();

            }

        }

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

//https://blog.csdn.net/u013568373/article/details/90607083

import java.util.LinkedHashMap;

public class LRUCache extends LinkedHashMap {

    //首先设定最大缓存空间 MAX_ENTRIES 为 3；

    private static final int MAX_ENTRIES = 3;

    //之后使用LinkedHashMap的构造函数将 accessOrder设置为 true，开启 LRU顺序；

    public LRUCache() {

        super(MAX_ENTRIES, 0.75f, true);

    }

    //最后覆盖removeEldestEntry(）方法实现，在节点多于 MAX_ENTRIES 就会将最近最少使用的数据移除。

    //因为这个函数默认返回false，不重写的话缓存爆了的时候无法删除最近最久未使用的节点

    @Override

    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {

        //在容量超过最大允许节点数的时候返回true，使得在afterNodeInsertion函数中能执行removeNode()

        return size() > MAX_ENTRIES;

    }

    public static void main(String[] args) {

        LRUCache cache = new LRUCache();

        cache.put(1, 1);

        cache.put(2, 2);

        cache.put(3, 3);

        cache.get(1);

        cache.put(4, 4);

        System.out.println(cache.keySet());

    }

}

1

2

3

4

5

6

7

8

#include//万能头文件

//数组中的输入

vectornum;

int n;

while(cin>>n){

    num.push_back(n);

}

//链表中输入

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution {

public:

    int maxSubArray(vector& nums) {

        int res=nums[0],s=0;//设定初始状态为nums[0]

        for(auto x:nums){

            if(s<0)s=0;

            s+=x;

            res=max(res,s);

        }

        return res;

    }

};

class Solution {

public:

    int maxSubArray(vector& nums) {

        int res=nums[0];//设定初始状态为nums[0]

        for(int i=1;i<nums.size();i++){

            nums[i]+=max(nums[i-1],0);//状态转移方程为dp[i]=max(dp[i-1],0)

            res=max(res,nums[i]);

        }

        return res;

    }

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

#include

using namespace std;

char ch[256];

int main(){

    cin>>ch;

    int len=strlen(ch);

    char maxchar;

    int num=1,maxn=0;

    for(int i=0;i<len;i++){

        if(ch[i]==ch[i+1])num++;

        else{

            if(num>maxn){

                maxn=num;

                maxchar=ch[i];

            }

            num=1;

        }

    }

    cout<<maxchar<<" "<<maxn;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

#include

using namespace std;

int function1(string s){

        int left=0,res=0,n=s.size();

        unordered_map m;

        for(int i=0;i<n;i++){

            left=max(left,m[s[i]]);

            m[s[i]]=i+1;

            res=max(res,i-left+1);

        }

        return res;

    }

int main(){

    string n;

    cin>>n;

    cout<<function1(n);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

public class QuickSort {

    private  void quickSortC(int[] a, int l, int r) {

        if (l >= r) {

            return;

        }

        int p = partition(a, l, r);

        quickSortC(a, l, p - 1);

        quickSortC(a, p + 1, r);

    }

    //空间浪费比较多的分区函数可以将小于分界点存一段，大于分界点存一段，再合并

    public  int partition(int[] a, int l, int r) {

        int pivot = a[r];

        int i = l;

        for (int j = l; j < r; j++) {

            if (a[j] < pivot) {

                swap(a, i, j);

                i = i + 1;

            }

        }

        swap(a, i, r);

        return i;

    }

    public static void swap(int[] a,int l,int r){

        int temp=a[l];

        a[l]=a[r];

        a[r]=temp;

    }

    public static void main(String[] args) {

        int a[]={9,8,6,1,2,5,3,7,10,4};

        QuickSort quickSort=new QuickSort();

        for(int a1:a){

            System.out.print(a1+" ");

        }

        System.out.println();

        quickSort.quickSortC(a,0,9);

        for(int a1:a){

            System.out.print(a1+" ");

        }

    }

}

1

2

3

4

5

6

7

8

//136 https://leetcode.wang/leetcode-136-Single-Number.html

public int singleNumber(int[] nums) {

    int ans = 0;

    for (int i = 0; i < nums.length; i++) {

        ans ^= nums[i];

    }

    return ans;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

//https://leetcode.wang/leetcode-137-Single-NumberII.html?q=

public int singleNumber(int[] nums) {

    int ans = 0;

    //考虑每一位

    for (int i = 0; i < 32; i++) {

        int count = 0;//别忘了写这个

        //考虑每一个数

        for (int j = 0; j < nums.length; j++) {

            //当前位是否是 1,无符号右移(右移不论正负都是高位补0)

            if ((nums[j] >>> i & 1) == 1) {

                count++;

            }

        }

        //1 的个数是否是 3 的倍数

        if (count % 3 != 0) {

            ans = ans | (1 << i);

        }

    }

    return ans;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

//https://leetcode-cn.com/problems/rotate-array/

class Solution {

    public void rotate(int[] nums, int k) {

        int previous,temp;

        int len =nums.length;

        for(int i=0;i<k;i++){

            previous=nums[len-1];

            for(int j=0;j<len;j++){

                temp=nums[j];

                nums[j]=previous;

                previous=temp;

            }

        }

    }

}

1

2

3

4

5

/*https://blog.csdn.net/xijiaoda_liuhao/article/details/8168875?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.nonecase*/

//https://blog.csdn.net/weixin_37553155/article/details/78806038?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-2

//https://blog.csdn.net/robbyo/article/details/8575339?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-5

//https://blog.csdn.net/u012605629/article/details/40482851?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-1

//https://blog.csdn.net/u012605629/article/details/40482851?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution {

public:

    vector exchange(vector& nums) {

        int fast=0,slow=0;

        while(fast<nums.size()){

            if(nums[fast]&1){

                swap(nums[slow],nums[fast]);

                slow++;

            }

            fast++;

        }

        return nums;

    }

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

//https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387

int jumpFloor(int n){

    int result=0;

    if(n==1||n==0){

        result=1;

    }else{

        result=2*jumFloor(n-1);

    }

    return result;

}

//leetcode10 https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

//青蛙跳台阶问题

//斐波那契类型，可以跳一格或两格

int jumpFloor2(int n){

    int dp[n+2];

    if(n<2){

        dp[n]=1;

    }

    dp[0]=1;dp[1]=1;

    for(int i=2;i<=n;i++){

        dp[i]=dp[i-1]+dp[i-2];

    }

    return dp[n];

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

//leetcode22 链表中倒数第k个节点

//https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

class Solution {

public:

    ListNode* getKthFromEnd(ListNode* head, int k) {

        auto first=head;

        auto second=head;

        for(int i=0;i<k;i++){

            first=first->next;

        }

        while(first!=NULL){

            first=first->next;

            second=second->next;

        }

        return second;

    }

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

struct ListNode {

     int val;

     ListNode *next;

     ListNode(int x) : val(x), next(NULL) {}

};

//leetcode206 https://leetcode-cn.com/problems/reverse-linked-list/

class Solution {

public:

    ListNode* reverseList(ListNode* head) {

        if(head==NULL)return NULL;

        auto a=head,b=head->next;

        while(b){

            auto c=b->next;

            b->next=a;

            a=b;

            b=c;

        }

        head->next=NULL;

        return a;

    }

};

//leetcode92 https://leetcode-cn.com/problems/reverse-linked-list-ii/

class Solution {

public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {

        if(m==n)return head;

        auto dummy=new ListNode(-1);

        dummy->next=head;

        auto a=dummy,d=dummy;

        for(int i=0;inext;

        for(int i=0;inext;

        auto b=a->next,c=d->next;

        for(auto p=b,q=b->next;q!=c;){

            auto o=q->next;

            q->next=p;

            p=q;q=o;

        }

        a->next=d;

        b->next=c;

        return dummy->next;

    }

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

#include

#include

//using  namespace std;

typedef struct Node{

    int data;

    struct Node *next;

}Node;

Node *CreateH();

Node *CreateH1();

void show(Node *Head);

int main(){

    Node *Head,*Head1;

    Head=CreateH();

    show(Head);

    Head1=CreateH1();

    show(Head1);

    return 0;

}

Node *CreateH(){

    int x;

    Node *Head;

    Head = (Node *)malloc(sizeof(Node));

    Head->next=NULL;

    Node *r;

    r=Head;

    while(scanf("%d",&x)!=EOF){

        Node *p = (Node *)malloc(sizeof(Node));

        p->data=x;

        r->next=p;

        r=p;

    }

    r->next=NULL;

    return Head;

}

Node *CreateH1(){

    int x;

    Node *Head;

    Node *p;

    Head = (Node *)malloc(sizeof(Node));

    Head->next=NULL;

    while(scanf("%d",&x)!=EOF){

        p = (Node *)malloc(sizeof(Node));

        p->data=x;

        p->next=Head->next;

        Head->next=p;

    }

    return Head;

}

void show(Node *Head){

    Node *p;

    p=Head->next;

    while(p!=NULL){

        printf("%d n",p->data);

        p=p->next;

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

//leetcode162寻找峰值  https://leetcode-cn.com/problems/find-peak-element/

class Solution {

public:

    int findPeakElement(vector& nums) {

        int l=0,r=nums.size()-1;

        while(l<r){

            int mid=l+r>>1;

            if(nums[mid]>nums[mid+1])r=mid;

            else l=mid+1;

        }

        return l;

    }

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

//https://www.nowcoder.com/questionTerminal/051934d3b2384b0fbfba3c544a0f75b1   牛客网题目

//leetcode33 https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

#include

using namespace std;

int main(){

    int len,target;

    cin>>len>>target;

    vectornum;

    int n;

    while(cin>>n){

        num.push_back(n);

    }

    int l=0,r=len-1;

    while(l<r){

        int mid=(l+r)>>1;

        if(num[mid]<=num.back())r=mid;

        else l=mid+1;

    }

    if(target<=num.back())r=len-1;

    else l=0,r--;

    while(l<r){

        int mid=(l+r)>>1;

        if(num[mid]>=target)r=mid;

        else l=mid+1;

    }

    if(num[l]==target)cout<<"Yes";

    else cout<<"No";

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

String charAt length//记得加()      HashSet contains  add

//1.left记录左括号数目，res记录匹配括号对数，right记录右括号数目

//2.遇到左括号left++

//3.遇到右括号：当left不为0，表示匹配，res++，left--；当left为0表示不匹配，right++

public static void main(String[] args){

    Scanner scan=new Scanner(System.in);

    String s=scan.next();

    HashSet cals=new HashSet();//要记得new HashSet后的()

    int left=0,right=0,res=0;

    cals.add('(');

    cals.add(')');

    for(int i=0;i<s.length();i++){

        if(cals.contains(s.charAt(i))){

            if(s.charAt(i)=='('){

                left++;

            }else if(s.charAt(i)==")"){

                if(left=0)right++;

                else if(left>0){

                    res++;

                    left--;

                }

            }

        }

    }

   System.out.println(res+" "+left+" "+right);

}

1

2

//https://blog.csdn.net/zrh_CSDN/article/details/80694202

//https://www.nowcoder.com/discuss/38862?type=post&order=create&pos=&page=1&channel=&source_id=1_post

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

import java.util.Stack;

//用两个栈实现队列

public class Stack2 {

    private Stack s1=new Stack();

    private Stacks2=new Stack();

    public Integer push(int p){

        return s1.push(p);

    }

    public Integer pop(){

        if(s1.isEmpty()&&s2.isEmpty())return 0;

        if(!s2.isEmpty()){

            return s2.pop();

        }

        int size=s1.size();

        for(int i=0;i<size;i++){

            s2.push(s1.pop());

        }

        return s2.pop();

    }

    public static void main(String[] args) {

        Stack2 stack2=new Stack2();

        for(int i=0;i<5;i++){

            System.out.println(stack2.push(i));

        }

        for(int i=0;i<5;i++){

            System.out.println(stack2.pop());

        }

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

public class ArrayStack {

    private int n;//栈长

    private int count;//数组长

    private String[] item;

    public ArrayStack(int capacity){

        item=new String[capacity];

        this.n=capacity;

        this.count=0;

    }

    public boolean push(String item1){

        if(count==n)return false;

        item[count]=item1;

        count++;

        return true;

    }

    public String pop(){

        if(count==0)return null;

        String res=item[count-1];

        count--;

        return res;

    }

    public static void main(String[] args) {

        ArrayStack stack=new ArrayStack(5);

        String[] s={"a","b","c","d","e"};

        for(int i=0;i<5;i++){

            System.out.println(stack.push(s[i]));

        }

        for(int i=0;i<5;i++){

            System.out.println(stack.pop());

        }

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

// 用数组实现的队列

public class ArrayQueue {

  // 数组：items，数组大小：n

  private String[] items;

  private int n = 0;

  // head表示队头下标，tail表示队尾下标

  private int head = 0;

  private int tail = 0;

  // 申请一个大小为capacity的数组

  public ArrayQueue(int capacity) {

    items = new String[capacity];

    n = capacity;

  }

  // 入队

  public boolean enqueue(String item) {

    // 如果tail == n 表示队列已经满了

    if (tail == n) return false;

    items[tail] = item;

    ++tail;

    return true;

  }

  // 出队

  public String dequeue() {

    // 如果head == tail 表示队列为空

    if (head == tail) return null;

    // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了

    String ret = items[head];

    ++head;

    return ret;

  }

  //主方法

  public static void main(String[] args) {

        ArrayQueue queue=new ArrayQueue(5);

        String[] s={"a","b","c","d","e"};

        for(int i=0;i<5;i++){

            System.out.println(queue.enqueue(s[i]));

        }

        for(int i=0;i<5;i++){

            System.out.println(queue.dequeue());

        }

    }

}