一、旋转数组

描述

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围：0<n≤100，0≤m≤1000

进阶：空间复杂度 O(1)，时间复杂度 O(n)

解题

如果允许使用其他数组，那么久很简单了，时间复杂度为O(n)，空间复杂度也为O(n)。

但是这道题要求不允许使用额外数组，所以就需要用比较巧的方法解决。

最后采用的是三次旋转法（记住这个技巧就可以了，没什么别的）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // 别忘了m需要先取模
        m = m % n;
        //第一次逆转全部数组元素
        reverse(a.begin(), a.end());
        //第二次只逆转开头m个
        reverse(a.begin(), a.begin() + m);
        //第三次只逆转结尾m个
        reverse(a.begin() + m, a.end());
        return a;
    }

ps：C++版本比java版本方便很多，因为有reverse函数可以直接调用

二、顺时针旋转矩阵

描述

有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于300。

示例：

输入：[[1,2,3],[4,5,6],[7,8,9]],3，返回值：[[7,4,1],[8,5,2],[9,6,3]]

代码

直接暴力交换就好，画个图很清晰

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        int length = mat.length;
        //矩阵转置
        for(int i = 0; i < length; ++i){
            for(int j = 0; j < i; ++j){
                //交换上三角与下三角对应的元素
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        //每行翻转
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length/2; j++){
                int temp = mat[i][j];
                mat[i][j] = mat[i][length - j - 1];
                mat[i][length - j - 1] = temp;
            }
        }
        return mat;
    }
}

错误复盘

因为我刚从C++转java，所以写这段代码时最开始犯了一个很典型的错误，下面是我第一次写的代码：

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
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @param n int整型 
     * @return int整型二维数组
     */
    public int[][] rotateMatrix (int[][] mat, int n) {
        // 首先交换对角线上的元素
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                swap(mat[i][j],mat[j][i]);
            }
        }

        //然后反转每一行的元素
        for(int i=0;i<n;i++){
            for(int j=0;j<n/2;j++){
                swap(mat[i][j],mat[i][n-1-j]);
            } 
        }

        return mat;
    }

    public void swap(int a, int b){
        int tmp = a;
        a = b;
        b = tmp;
    }
}

上述代码输出时矩阵没有任何变化，原因是这段代码中存在一个常见的误解，即在 Java 中int类型传递的是值而不是引用。在 swap 方法中，我试图通过传递参数来交换两个整数的值，但这种方式在 Java 中是不起作用的。Java 中的参数传递是按值传递的，这意味着传递给方法的是实际参数的副本，而不是参数本身。因此，即使在 swap 方法中交换了 a 和 b 的值，这只会影响方法内部的副本，而不会影响到原始数组 mat 中的值。

为了解决这个问题，可以将 swap 方法修改为接受数组索引，然后在 rotateMatrix 方法中调用这个方法来交换数组中元素的值。这样就可以实现矩阵的旋转了。

下面是修改后的代码：

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
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @param n int整型 
     * @return int整型二维数组
     */
    public int[][] rotateMatrix(int[][] mat, int n) {
        // 首先交换对角线上的元素
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(mat, i, j, j, i); // 交换对角线上的元素
            }
        }

        // 然后反转每一行的元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                swap(mat, i, j, i, n - 1 - j); // 反转每一行的元素
            }
        }

        return mat;
    }

    public void swap(int[][] mat, int i1, int j1, int i2, int j2) {
        int tmp = mat[i1][j1];
        mat[i1][j1] = mat[i2][j2];
        mat[i2][j2] = tmp;
    }
}

在Java中，数组传递的是引用。这意味着将一个数组作为参数传递给方法时，实际上传递的是数组在内存中的地址，而不是数组的副本。

总结：在 Java 中，基本数据类型（如 int、double、char 等）传递的是值，而对象类型（包括数组、类的实例等）传递的是引用。

三、设计LRU缓存结构

描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

  1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

  2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。

  3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

思路

一道很高频的面试题，这道题的难点是不容易想到数据结构（双向链表+哈希表），需要对双向链表和哈希表的操作比较了解，另外发现我写算法题习惯用C++，用JAVA完全不会写，找JAVA后端开发一定要用java刷题吗有没有人能解答我的疑惑QAQ

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <unordered_map>
class Solution {
public:

 struct Node{
    int key, val;
    Node *prev, *next;
    Node(int k, int v): key(k), val(v), prev(nullptr), next(nullptr){}
 };

 unordered_map<int, Node*> mp;
 Node* L,*R;
 int n;
 Solution(int capacity){
 // write code here
  n=capacity;
  L = new Node(-1, -1);
  R = new Node(-1, -1);
  L->next=R;
  R->prev=L;
 }
 
 int get(int key) {
 // write code here
  if(mp.count(key)){
    //把该节点移动到头
    Node *tmp = mp[key];
    remove(tmp);
    insert(tmp);
    //返回对应的值
    return tmp->val;
  }
  else return -1;
 }
 
 void set(int key, int value){
 // write code here
  if(mp.count(key)){
    Node* tmp = mp[key];
    tmp->val = value;
    remove(tmp);
    insert(tmp);
  }
  else{
    Node* tmp = new Node(key,value);
    mp[key] = tmp;
    if(mp.size() > n){
        Node* node = L->next;
        mp.erase(node->key);
        remove(node); 
        insert(tmp);
        delete node;
    }else{
        insert(tmp);
    }
  }
 }

 void remove(Node* node){
    Node* pre = node->prev;
    Node* nxt = node->next;
    pre->next = nxt;
    nxt->prev = pre;
 }

 void insert(Node* node){
    node->prev = R->prev;
    R->prev->next = node;
    node->next = R;
    R->prev = node; 
 }
};

四、回文链表

题目

判断输入的链表是不是回文的

解题

这道题的知识点两个：一个是利用快慢指针找到链表中点（奇数刚好是中点，偶数的话是中点靠前一个节点），第二个是如何reverse链表，这里需要有三个指针，一个是pre，一个是cur，还有一个是curNext。

代码

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
58
59
60
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr)
            return true;
        
        //找到前半部分的尾结点病反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        //判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        //还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    //反转后半部分链表
    ListNode* reverseList(ListNode* head){
        ListNode* pre = nullptr;
        ListNode* curr = head;

        while(curr!=nullptr){
            ListNode* nextTemp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = nextTemp;
        }

        return pre;
    }
};

五、八皇后问题

题目略

思路

这道题写过无数次了，但每次自己写都写不出来，在acwing看了y总的解法，代码十分优美。遂记录。

这道题的难点有三：

1、如何处理输出

2、如何遍历

3、如何判断当前行、当前列、当前对角线上是否存在皇后