leetcode

840-矩阵中的幻方

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。

示例：

输入: [[4,3,8,4],
   [9,5,1,9],
   [2,7,6,2]]
输出: 1

解释:

下面的子矩阵是一个 3 x 3 的幻方：
438
951
276
而这一个不是：
384
519
762
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

提示:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15 

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
class Solution {
public int numMagicSquaresInside(int[][] grid) {
        int ret = 0;
        int sum = 15;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < grid.length - 2; i++) {
            for (int j = 0; j < grid[i].length - 2; j++) {
                hashMap.clear();
                int a11 = grid[i][j];
                int a12 = grid[i][j + 1];
                int a13 = grid[i][j + 2];
                int a21 = grid[i + 1][j];
                int a22 = grid[i + 1][j + 1];
                int a23 = grid[i + 1][j + 2];
                int a31 = grid[i + 2][j];
                int a32 = grid[i + 2][j + 1];
                int a33 = grid[i + 2][j + 2];
                if (a22 != 5)
                    continue;
                hashMap.put(a11, 1);
                hashMap.put(a12, 1);
                hashMap.put(a13, 1);
                hashMap.put(a21, 1);
                hashMap.put(a22, 1);
                hashMap.put(a23, 1);
                hashMap.put(a31, 1);
                hashMap.put(a32, 1);
                hashMap.put(a33, 1);
                if (hashMap.size() != 9) {
                    continue;
                }
                boolean flag = true;
                for (Map.Entry<Integer, Integer> e : hashMap.entrySet()) {
                    if (e.getKey() > 9 || e.getKey() < 1) {
                        flag = false;
                        break;
                    }
                }
                if (!flag)
                    continue;
                if (a11 + a12 + a13 != sum)
                    continue;
                if (a21 + a22 + a23 != sum)
                    continue;
                if (a31 + a32 + a33 != sum)
                    continue;
                if (a11 + a21 + a31 != sum)
                    continue;
                if (a12 + a22 + a32 != sum)
                    continue;
                if (a13 + a23 + a33 != sum)
                    continue;
                if (a11 + a22 + a33 != sum)
                    continue;
                if (a13 + a22 + a31 != sum)
                    continue;
                ret++;
            }
        }
        return ret;
    }
}

这道题真的是无脑，遍历可以解决的题还扔出来。。。

leetcode

687-最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

1
2
3
4
5
6
7
8
输入:
              5          
             / \      
            4   5
           / \   \   
          1   1   5 
输出:
2

示例 2:

1
2
3
4
5
6
7
8
输入:
              1
             / \     
            4   5   
           / \   \  
          4   4   5 
输出:
2

注意:

给定的二叉树不超过10000个结点。 树的高度不超过1000。

解答

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
class Solution {
    public int longestUnivaluePath(TreeNode root) {
        if (root == null)
            return 0;
        int res = help(root.left, root.val) + help(root.right, root.val);
        int left = longestUnivaluePath(root.left);
        int right = longestUnivaluePath(root.right);
        int max = res > left ? res : left;  // 注4
        max = max > right ? max : right;  // 注4
        return max;

    }

    public int help(TreeNode root, int parent) {
        if (root == null)
            return 0;
        int res = 0;
        if (root.val == parent)  // 注1
            res += 1;
        else
            return 0;  // 注3
        int left = help(root.left, parent);
        int right = help(root.right, parent);
        res += left > right ? left : right; // 注2
        return res;
    }

}

其他

这道题咋一看没思路,后面发现例题中三个节点相等时结果为2,也就是两条连接线.

  • 注1.而且节点的父节点值跟自己相等时,连接数应该+1.
  • 注2.这个路径同一个节点不能分叉,所以只能取其中一条分支的连接数累加上来.
  • 注3.并且为了保证是相连的,如果遇到和父节点值不一样的,直接return.
  • 注4.遍历所有节点,取最大值
leetcode

686-重复叠加字符串匹配

给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。
举个例子，A = “abcd”，B = “cdabcdab”。
答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为”abcdabcd”，B 并不是其子串。

注意:

A 与 B 字符串的长度在1和10000区间范围内。

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
class Solution {
     public int repeatedStringMatch(String A, String B) {
        if (A.length() >= B.length()) {
            if (A.contains(B))  // 注释1
                return 1;
        }
        for (int s = 0; s < A.length(); s++) { 
            if (A.charAt(s) == B.charAt(0)) {  // 注释2
                int ret = 1;
                boolean flag = false;
                int index = s;
                for (int i = 0; i < B.length(); i++) {  // 注释3
                    if (index == A.length()) {
                        index = 0;
                        ret += 1;  // 注释5
                    }
                    if (B.charAt(i) == A.charAt(index)) {
                        index++;
                        continue;
                    }
                    flag = true;  // 注释4
                    break;
                }
                if (flag)
                    continue;
                return ret;
            }
        }
        return -1;
    }
}

代码中注释对应语句

  • 注释1.如果是子串直接返回1.
  • 注释2.遍历A字符串寻找与B字符串开头一致的字符.
  • 注释3.遍历B字符串,然后对位到A字符串.
  • 注释4.任意不一样,则该情况走不通.
  • 注释5.如果索引超过A字符串长度,则需要叠加数+1.
leetcode

703-数据流中的第K大元素

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

1
2
3
4
5
6
7
8
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);  // returns 4
kthLargest.add(5);  // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9);  // returns 8
kthLargest.add(4);  // returns 8

说明:

  • 你可以假设 nums 的长度≥ k-1 且k ≥ 1。

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class KthLargest {
    private int k;
    private PriorityQueue<Integer> q;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.q = new PriorityQueue<>(k);
        for (int num : nums) {
            this.add(num);
        }
    }

    public int add(int val) {
        if (this.q.size() < k)
            this.q.offer(val);
        else if (this.q.peek() < val) {
            this.q.poll();
            this.q.offer(val);
        }
        return this.q.peek();
    }
}

主要的坑

  • 用链表不行…很麻烦..
leetcode►2019春季高校赛初赛

1-易混淆数

描述

给定一个数字 N，当它满足以下条件的时候返回 true：
把原数字旋转180°以后得到新的数字。
如 0, 1, 6, 8, 9 旋转 180° 以后，得到了新的数字 0, 1, 9, 8, 6 。
2, 3, 4, 5, 7 旋转 180° 后,得到的不是数字。
易混淆数字 (confusing number) 就是一个数字旋转180°以后，得到和原来不同的数字，且新数字的每一位都是有效的。

示例 1：9

输入：6
输出：true
解释：
把 6 旋转 180° 以后得到 9，9 是有效数字且 9!=6 。

示例 2：

输入：89
输出：true
解释:
把 89 旋转 180° 以后得到 68，86 是有效数字且 86!=89 。

示例 3：

输入：11
输出：false
解释：
把 11 旋转 180° 以后得到 11，11 是有效数字但是值保持不变，所以 11 不是易混淆数字。

示例 4：

输入：25
输出：false
解释：
把 25 旋转 180° 以后得到的不是数字。

提示：

0 <= N <= 10^9
可以忽略掉旋转后得到的前导零，例如，如果我们旋转后得到 0008 那么该数字就是 8 。

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int[] easy = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};

    public boolean confusingNumber(int N) {
        if (N == 0)
            return false;
        int tmpN = N;
        int newNum = 0;
        int tmp;
        while (tmpN != 0) {
            newNum *= 10;
            tmp = easy[tmpN % 10];
            if (tmp == -1)
                return false;
            newNum += tmp;
            tmpN /= 10;
        }

        return newNum != N;
    }
}

注意点:

因为需要转换的数字比较少,直接用数组的索引作为映射就行,如果有一个不能转换的直接returnn false , 最后判断转换后的数与原数是否相等.

其它:

这次高校赛服务器异常,重开后有两次初赛

leetcode►2019春季高校赛初赛

1-有序数组中的缺失元素

描述

给出一个有序数组 A，数组中的每个数字都是 独一无二的，找出从数组最左边开始的第 K 个缺失数字。

示例 1：

输入：A = [4,7,9,10], K = 1
输出：5
解释：
第一个缺失数字为 5 。

示例 2：

输入：A = [4,7,9,10], K = 3
输出：8
解释：
缺失数字有 [5,6,8,…]，因此第三个缺失数字为 8 。

示例 3：

输入：A = [1,2,4], K = 3
输出：6
解释：
缺失数字有 [3,5,6,7,…]，因此第三个缺失数字为 6 。

提示:

  • 1 <= A.length <= 50000
  • 1 <= A[i] <= 1e7
  • 1 <= K <= 1e8

解答:

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
public class Solution {
    public int missingElement(int[] nums, int k) {
        int start = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            if (tmp == start + 1) {
                start++;
            } else {
                int minusVal = tmp - start -1;
                if (minusVal >= k)
                    return start + k;
                else {
                    k -= minusVal;
                    start = tmp;
                }
            }
        }
        return start + k;
    }

    public static void main(String[] args) {
        var q = new q2019_04_21比赛1();
        var res1 = q.missingElement(new int[]{4, 7, 9, 10}, 1);
        System.out.println(res1 == 5);
        var res2 = q.missingElement(new int[]{4,7,9,10}, 3);
        System.out.println(res2 == 8);
        var res3 = q.missingElement(new int[]{1,2,4}, 3);
        System.out.println(res3 == 6);
    }
}

注意点:

主要判断数组中两个元素中间缺几个数,如果大于等于k,则直接返回结果,否则进入下一个循环判断

leetcode

707-设计链表

设计链表的实现

   您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例:

1
2
3
4
5
6
7
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

  • 所有值都在 [1, 1000] 之内。
  • 操作次数将在 [1, 1000] 之内。
  • 请不要使用内置的 LinkedList 库。

解答:

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class MyLinkedList {
    class Cell {
        int val = 0;
        Cell next = null;
    }

    Cell head = null;
    Cell tail = null;
    int cnt = 0;

    /**
     * Get the value of the index-th node in the linked 
       list. If the index is invalid, return -1.
     */
    public int get(int index) {
        if (cnt == 0)
            return -1;
        if (index == 0) {
            return head.val;
        } else {
            Cell tmp = GetPreNode(index);
            if (tmp == null || tmp.next == null)
                return -1;
            return tmp.next.val;
        }

    }

    /**
     * Add a node of value val before the first element of 
       the linked list. After the insertion, the new node will be 
       the first node of the linked list.
     */
    public void addAtHead(int val) {
        this.addAtIndex(0, val);
    }

    /**
     * Append a node of value val to the last element of 
       the linked list.
     */
    public void addAtTail(int val) {
        this.addAtIndex(cnt, val);
    }

    /**
     * Add a node of value val before the index-th node
       in the linked list. If index equals to the length 
       of linked list, the node will be appended to the end
       of linked list. If index is greater than the length,
       the node will not be inserted.
     */
    public void addAtIndex(int index, int val) {
        if (index > cnt)
            return;
        if (index < 0)
            index = 0;
        Cell node = new Cell();
        node.val = val;
        if (cnt == 0) {
            head = node;
            tail = node;
        } else if (index == 0) {
            node.next = head;
            head = node;
        } else {
            Cell pre = GetPreNode(index);
            if (pre == null)
                return;
            node.next = pre.next;
            pre.next = node;

        }
        cnt++;
    }

    /**
     * Delete the index-th node in the linked list, 
       if the index is valid.
     */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= cnt)
            return;
        if (index == 0) {
            head = head.next;
        } else {
            Cell pre = GetPreNode(index);
            if (pre == null)
                return;
            if (pre.next != null) {
                pre.next = pre.next.next;
            } else {
                pre.next = null;
            }

        }
        cnt--;
    }

    public Cell GetPreNode(int index) {
        if (index < 0 || index > cnt)
            return null;
        Cell pre = head;
        int tmpCnt = 1;
        while (tmpCnt < index) {
            if (pre.next == null)
                return null;
            pre = pre.next;
            tmpCnt++;
        }
        return pre;
    }

}

主要的坑

  • 要记录当前节点数,每次增加删除节点要加减
  • addAtIndex调用时,如果index参数小于0,要改变其值为0
  • 添加删除节点时候,如果时链条中的,记得连接两头
备忘录

git不常用但有用命令

删除对某些文件的版本管理

  • git rm -r –cached “bin/“
  • git commit -m” remove bin folder all file out of control”
  • 查看结果没问题了再 push

通过命令行创建一个新的远程版本库并推送到远程

  • touch README.md
  • git init
  • git add README.md
  • git commit -m “first commit”
  • git remote add origin ssh://admin@192.168.1.23:29418/qusouti.git
  • git push -u origin master

远程已经存在分支,将本地推送到那

git remote set-url origin http://***
git push

展示某个提交的 iso 标准日期和修改内容

git show –name-status –format=”%ci%n%an%n%s” xxxxxHashxxxxxxx

生成 git ssh id.pub 密钥文件,生成密钥

ssh-keygen -t rsa -C “xxxxx@xx.com”