truetime1.5 多个网络

avatar

注意事项：
When you are using multiple networks, you must use the syntax
ttSendMsg([network receiver], data, length, priority)
Otherwise, network 1 will be assumed as the default.

k1_init.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function k1_init

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

offset = 0;
period = 1;
prio = 1;
ttCreatePeriodicTask('k1_task', offset, period, prio, 'k1_task');

% Initialize network
ttCreateInterruptHandler('k1_handle', prio, 'k1_handle');
ttInitNetwork(1,1, 'k1_handle');


k1_task.m文件

1
2
3
4
5
6
7

function [exectime, data] = k1_task(seg, data)

disp('k1 send');
ttSendMsg([1 2],[1 1;1 -1],80);  
exectime = -1;

k1_handle.m文件

1
2
3
4
5
6
7
function [exectime,data] = k1_handle(seg,data)

m = ttGetMsg();
disp('k1');
disp(m);
exectime = -1;

k2_init.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function k2_init

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

offset = 0;
period = 1;
prio = 1;
%ttCreatePeriodicTask('k2_task', offset, period, prio, 'k2_task');

% Initialize network
ttCreateInterruptHandler('k2_handle', prio, 'k2_handle');
ttInitNetwork(1,2, 'k2_handle');

k2_handle.m文件

1
2
3
4
5
6
7
8
9
10
function [exectime,data] = k2_handle(seg,data)

m = ttGetMsg(1);

disp('==================')
disp('k2');
disp(m);
disp('==================')
exectime = -1;

k3_init.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function k3_init

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

offset = 1.5;
period = 2;
prio = 1;
ttCreatePeriodicTask('k3_task', offset, period, prio, 'k3_task');

% Initialize network
ttCreateInterruptHandler('k3_handle', prio, 'k3_handle');
ttInitNetwork(2, 1, 'k3_handle');

k3_task.m文件

1
2
3
4
5
6
function [exectime, data] = k3_task(seg, data)

disp('k3 send');
ttSendMsg([2 2], [3 3;3 -1], 80);
exectime = -1;

k3_handle.m文件

1
2
3
4
5
6
7
function [exectime,data] = k3_handle(seg,data)

m = ttGetMsg();
disp('k3');
disp(m);
exectime = -1;

k4_init.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
function k4_init

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

offset = 0;
period = 1;
prio = 1;

% Initialize network
ttCreateInterruptHandler('k4_handle', prio, 'k4_handle');
ttInitNetwork(2,2,'k4_handle');

k4_handle.m文件

1
2
3
4
5
6
7
8
9
10
function [exectime,data] = k4_handle(seg,data)

m = ttGetMsg(2);

disp('================')
disp('k4');
disp(m);
disp('================')
exectime = -1;

展开全文 >>

truetime1.5 线性网络

avatar

k1_init.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function k1_init

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

offset = 0;
period = 1;
prio = 1;
ttCreatePeriodicTask('k1_task', offset, period, prio, 'k1_task');

% Initialize network
ttCreateInterruptHandler('k1_handle', prio, 'k1_handle');
ttInitNetwork(2,1, 'k1_handle');%必须在truetime network的两端连接的kernel都初始化网络号（本例为2），该网络号才可以使用。
%另外本例中的1是接入的端口号

%在truetime network的两端，输入端口的只和输出端口的值不能相同。


k1_task.m

1
2
3
4
5
6
7

function [exectime, data] = k1_task(seg, data)

disp('k1 send');
ttSendMsg([2 2],[1 1;1 -1],80);%向network number为2的网络的2号接收端口发送信息  
exectime = -1;

k1_handle.m文件

1
2
3
4
5
function [exectime,data] = k1_handle(seg,data)

disp('k1');
exectime = -1;

k2_init.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function k2_init

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

offset = 0;
period = 1;
prio = 1;

% Initialize network
ttCreateInterruptHandler('k2_handle', 1, 'k2_handle');
ttInitNetwork(2,2, 'k2_handle');

% Initialize the TRUETIME network interface. If the kernel should be connected to
% several networks, this function must be called several times. This function is
% used both for wired and wireless networks.
% 初始化TRUETIME网络接口。如果内核需要连接到多个网络，这个函数必须被多次调用。
% 但是后面的中断处理函数暂时没有被调用，不知道什么原因。

ttCreateInterruptHandler('k2_handle_unused', 2, 'k2_handle_unused');%这个中断处理函数将不会被执行
ttInitNetwork(3,1, 'k2_handle_unused');


k2_handle.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
function [exectime,data] = k2_handle(seg,data)

   disp('===========call k2_handle handle===========')
   m = ttGetMsg(2);
   disp('==================')
   disp('k2');
   disp(m);
   disp('==================')
   m(1)=2;
   ttSendMsg([3 1],m,80);  %向network number为3的网络的1号接收端口发送信息  

exectime = -1;

k2_handle_unused.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function [exectime,data] = k2_handle_unused(seg,data)

disp('===========call k2_handle_unused handle===========')
%这个函数没有被调用，调节了优先级好像也没有用

% m = ttGetMsg(2);
% disp('==================')
% disp('k2');
% disp(m);
% disp('==================')
% m(1)=2;
% ttSendMsg([3 1],m,80);  
exectime = -1;

k3_init.m文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function k3_init

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

offset = 0;
period = 1;
prio = 1;

% Initialize network
ttCreateInterruptHandler('k3_handle', prio, 'k3_handle');
ttInitNetwork(3,1, 'k3_handle');


k3_handle.m文件

1
2
3
4
5
6
7
8
9
10
function [exectime,data] = k3_handle(seg,data)

m = ttGetMsg(3);
disp('==================')
disp('k3');
disp(m);
disp('==================')
exectime = -1;


展开全文 >>

truetiem仿真工具使用记录

avatar

node_init1.m文件，truetime kernel1 的初始化函数文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function node_init1

% Distributed control system: sensor node
%
% Samples the plant periodically and sends the samples to the 
% controller node.

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

% Create sensor task
% data.y = 0;
offset = 0;
period = 0.1;
prio = 1;
ttCreatePeriodicTask('sendTask', offset, period, prio, 'periodicTask1');

% Initialize network
ttCreateInterruptHandler('receiveHanlder1', prio, 'messageReceiveHandler1');
ttInitNetwork(1, 'receiveHanlder1');%这里的1对应于truetime network子系统的输入端口

周期性任务periodicTask1.m

1
2
3
4
5
6

function [exectime, data] = periodicTask1(seg, data)

ttSendMsg(2, 666, 80);  %这里的网络号码2与子系统的接口一一对应，即与subsystem的Out2端口相对应。
exectime = -1;

中断处理程序messageReceiveHandler1.m

1
2
3
4
function [exectime,data]=messageReceiveHandler1(seg,data)

exectime = -1;

node_init2.m文件，truetime kernel2 的初始化函数文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function node_init2

% Distributed control system: sensor node
%
% Samples the plant periodically and sends the samples to the 
% controller node.

% Initialize TrueTime kernel
ttInitKernel(0, 0, 'prioFP'); % nbrOfInputs, nbrOfOutputs, fixed priority

% Create sensor task
% data.y = 0;
% offset = 0;
% period = 0.010;
prio = 1;
% ttCreatePeriodicTask('sendTask', offset, period, prio, 'periodicTask1',data);

% Initialize network
ttCreateInterruptHandler('receiveHanlder2', prio, 'messageReceiveHandler2');
ttInitNetwork(2, 'receiveHanlder2');%这里的2对应于truetime network子系统的输入端口

中断处理程序messageReceiveHandler2.m

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function [exectime,data]=messageReceiveHandler2(seg,data)


switch seg,
 case 1,  
    msg = ttGetMsg;
    disp('node 2 receive msg=');
    disp(msg);
    % 再发出去
    ttSendMsg(1, msg, 80);%这里的号码与输出端口号一一对应，如果只有一个端口默认为1
    exectime = -1;
end

展开全文 >>

翻转二叉树（简单题） 

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

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

层次遍历，自顶向下修改每个节点的左子树和又子树

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(null==root){//根节点为空直接终止
            return null;
        }
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            for (int i = 0; i < queue.size(); i++) {
                TreeNode node = queue.poll();
                if (null != node.left && null != node.right) {//左子树和右子树都不为空，则交换左右子树
                    TreeNode node1 = node.left;
                    node.left = node.right;
                    node.right = node1;
                    queue.add(node.left);
                    queue.add(node.right);
                }else if(null != node.left){//左子树不为空
                    node.right=node.left;
                    node.left=null;
                    queue.add(node.right);
                }else if(null!=node.right){//右子树不为空
                    node.left=node.right;
                    node.right=null;
                    queue.add(node.left);
                }
            }

        }
        return root;
    }
}

水平比两年前还倒退了

1
2
3
4
5
6
7
8
9
10

class Solution {
        public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            TreeNode rightTree = root.right;
            root.right = invertTree(root.left);
            root.left = invertTree(rightTree);
            return root;
        }
    }

展开全文 >>

快排

快排算法

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

package Sorts;

import static Sorts.SortUtils.*;

/**
 * @author Varun Upadhyay (https://github.com/varunu28)
 * @author Podshivalov Nikita (https://github.com/nikitap492)
 * @see SortAlgorithm
 */
class QuickSort implements SortAlgorithm {

    /**
     * This method implements the Generic Quick Sort
     *
     * @param array The array to be sorted
     *              Sorts the array in increasing order
     **/

    @Override
    public <T extends Comparable<T>> T[] sort(T[] array) {
        doSort(array, 0, array.length - 1);
        return array;
    }


    /**
     * The sorting process
     *
     * @param left  The first index of an array
     * @param right The last index of an array
     * @param array The array to be sorted
     **/

    private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
        if (left < right) {
            int pivot = randomPartition(array, left, right);
            doSort(array, left, pivot - 1);
            doSort(array, pivot, right);
        }
    }

    /**
     * Ramdomize the array to avoid the basically ordered sequences
     * 
     * @param array The array to be sorted
     * @param left  The first index of an array
     * @param right The last index of an array
     * @return the partition index of the array
     */

    private static <T extends Comparable<T>> int randomPartition(T[] array, int left, int right) {
        int randomIndex = left + (int)(Math.random()*(right - left + 1));
        swap(array, randomIndex, right);
        return partition(array, left, right);
    }

    /**
     * This method finds the partition index for an array
     *
     * @param array The array to be sorted
     * @param left  The first index of an array
     * @param right The last index of an array
     *              Finds the partition index of an array
     **/

    private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
        int mid = (left + right) >>> 1;
        T pivot = array[mid];

        while (left <= right) {
            while (less(array[left], pivot)) {
                ++left;
            }
            while (less(pivot, array[right])) {
                --right;
            }
            if (left <= right) {
                swap(array, left, right);
                ++left;
                --right;
            }
        }
        return left;
    }

    // Driver Program
    public static void main(String[] args) {

        // For integer input
        Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};

        QuickSort quickSort = new QuickSort();
        quickSort.sort(array);

        //Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111
        print(array);

        String[] stringArray = {"c", "a", "e", "b", "d"};
        quickSort.sort(stringArray);

        //Output => a	b	c	d	e
        print(stringArray);
    }
}

参考文献

所有算法的java实现

展开全文 >>

整数转罗马数字(中等题)

12. 整数转罗马数字

难度中等600

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1:

1
2
输入: num = 3
输出: "III"

示例 2:

1
2
输入: num = 4
输出: "IV"

示例 3:

1
2
输入: num = 9
输出: "IX"

示例 4:

1
2
3
输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

1
2
3
输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • 1 <= num <= 3999

优雅的写法

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
class Solution {
      /**
     * 把罗马数字和整数一一对应，通过while循环判断num值与整数的相减是否大于0，求出罗马数字
     */
    private static int[] nums = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

    private static String[] strings = new String[] {
            "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
    };

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (num > 0) {
            if (num - nums[i] >= 0) {
                sb.append(strings[i]);
                num -= nums[i];
            } else {
                i++;
            }
        }
        return sb.toString();
    }
}

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

public class RomanNumber {
    public static void main(String[] args) {
        String s=intToRoman(1994);
        System.out.println(s);
    }
    public static String intToRoman(int num) {
        StringBuilder bd=new StringBuilder();
        int cur=0;
        String s="";
        while(num>0){
            int val=num%10;
            num=num/10;
            switch (cur){
                case 0:
                    s=getStringVal(val,"I","V","X");
                    bd.insert(0,s);
                    break;
                case 1:
                    s=getStringVal(val,"X","L","C");
                    bd.insert(0,s);

                    break;
                case 2:
                    s=getStringVal(val,"C","D","M");
                    bd.insert(0,s);

                    break;
                case 3:
                    s=getStringVal(val,"M","","");
                    bd.insert(0,s);

                    break;
            }
            cur++;
        }

        return bd.toString();
    }


    /**
     * 罗马数字的组成形式
     * @param val 每一位的值
     * @param one 单位1
     * @param five 5的值
     * @param ten  10的值
     * @return
     */
    public static String getStringVal(int val,String one,String five,String ten){
        if(val<4){//小于4时是单位1的组合
            StringBuilder stringBuilder=new StringBuilder();
            for(int i=0;i<val;i++){
                stringBuilder.append(one);
            }
            return stringBuilder.toString();
        }else if(val==4){//4是单位1和5的组合
            return one+five;
        }else if(val==5){//直接返回5
            return five;
        }else if(val<9){//6-8是5和单位1的组合
            StringBuilder stringBuilder=new StringBuilder();
            stringBuilder.append(five);
            for(int i=0;i<val-5;i++){
                stringBuilder.append(one);
            }
            return stringBuilder.toString();
        }else if(val==9){//9是单位1和10的组合
            return one+ten;
        }else {//直接返回10
            return ten;
        }
    }
}

膜拜大佬的写法，用时击败99%

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
class Solution {
      /**
     * 把罗马数字和整数一一对应，通过while循环判断num值与整数的相减是否大于0，求出罗马数字
     */
    private static int[] nums = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

    private static String[] strings = new String[] {
            "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
    };

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (num > 0) {
            if (num - nums[i] >= 0) {
                sb.append(strings[i]);
                num -= nums[i];
            } else {
                i++;
            }
        }
        return sb.toString();
    }
}

参考文献

评论区大佬算法使我快乐😍

展开全文 >>

9*9数独问题（困难题）

37. 解数独

难度困难761

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

img

一个数独。

img

答案被标成红色。

提示：

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

回溯

使用boolean数组记录行、列、以及9*9宫格的数字的index

膜拜大佬的代码

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
public class Sudoku {

    public void solveSudoku(char[][] board) {
        /**
         * 记录某行，某位数字是否已经被摆放
         */
        boolean[][] row = new boolean[9][9];
        /**
         * 记录某列，某位数字是否已经被摆放
         */
        boolean[][] col = new boolean[9][9];
        /**
         * 记录某 3x3 宫格内，某位数字是否已经被摆放
         */
        boolean[][] block = new boolean[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {//如果数字不为空
                    int num = board[i][j] - '1';//将数字转换成下标
                    row[i][num] = true;//在第i行，该数字已经被使用
                    col[j][num] = true;//在第j列，该数字已经被使用
                    // blockIndex = i / 3 * 3 + j / 3，取整
                    block[i / 3 * 3 + j / 3][num] = true;//块下标
                }
            }
        }
        dfs(board, row, col, block, 0, 0);
    }
    private boolean dfs(char[][] board, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j) {
        // 找寻空位置
        while (board[i][j] != '.') {
            // 第i行找完了
            if (++j >= 9) {
                // 行数加一
                i++;
                // 列数置0
                j = 0;
            }
            if (i >= 9) {
                return true;
            }
        }//移动下标到空位置
        for (int num = 0; num < 9; num++) {
            int blockIndex = i / 3 * 3 + j / 3;//块下标
            if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) {//在第i行没有用到过，在第j列没有遇到过并且在块中没有遇到过数字num
                // 递归
                board[i][j] = (char) ('1' + num);//将下标重新转换成数字
                row[i][num] = true;//第i行num被使用
                col[j][num] = true;//第j列num被使用
                block[blockIndex][num] = true;//在下标为i / 3 * 3 + j / 3的块中num被使用
                if (dfs(board, row, col, block, i, j)) {//回溯添加空数字
                    return true;
                } else {
                    // 回溯
                    row[i][num] = false;
                    col[j][num] = false;
                    block[blockIndex][num] = false;
                    board[i][j] = '.';
                }
            }
        }
        return false;
    }

    private void printBoard(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        Sudoku solution = new Sudoku();
        solution.printBoard(board);
        solution.solveSudoku(board);
        solution.printBoard(board);
    }
}


膜拜

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

class Solution {
    public void solveSudoku(char[][] board) {
        if(board==null||board.length<=0||board[0].length<=0) return;
        char[] nums={'1','2','3','4','5','6','7','8','9'};//可放元素
        dfs(board,0,0,nums);
    }

    boolean dfs(char[][] board,int x,int y,char[] nums){
        if(y>=board[0].length) return dfs(board,x+1,0,nums);//一行找完了，找下一行
        if(x>=board.length) return true;//行列都找完了，结束
        if(board[x][y]!='.') return dfs(board,x,y+1,nums);//有数字，找下一个格子
        for(char num:nums){//依次遍历可放入的元素
            if(check(board,x,y,num)){//如果可选
                board[x][y]=num;//填入
                if(dfs(board,x,y+1,nums)){//下一个可填，也就是从最后一个格子依次返回的都是true
                    return true;
                }else{//回溯
                    board[x][y]='.';
                }
            }
        }
        return false;
    }

    boolean check(char[][] board,int x,int y,char c){//判断当前元素是否可放（x,y）位置
        for(int i=0;i<board.length;i++){//横竖
            if(board[x][i]==c||board[i][y]==c) return false;
        }
        for(int i=x/3*3;i<x/3*3+3;i++){//找到九宫格左上元素，依次遍历
            for(int j=y/3*3;j<y/3*3+3;j++){
                if(board[i][j]==c) return false;
            }
        }
        return true;
    }
}

参考文献

评论区代码Angus-Liu

评论区代码ʌoɹǝz

展开全文 >>

二叉树的中序遍历(递归和非递归方法)（中等题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
 private List<Integer> list=new ArrayList<>();
 public List<Integer> inorderTraversal(TreeNode root) {
     if(null!=root){
         inorderTraversal(root.left);
         list.add(root.val);
         inorderTraversal(root.right);
     }
     return list;
 }


非递归方法，使用栈，先把左子树上的每个节点加入
出栈时遍历，如果有右子树，再把右子树加入栈中，如果右子树有左子树，继续添加左子树，
直至遍历完成。

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
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    ArrayDeque<TreeNode> stack=new ArrayDeque<>();
    if(null!=root){
        stack.push(root);
    }else{//如果树为空，直接跳出
        return list;
    }

    TreeNode node=root;
    while(null!=node.left){//将左子树上的节点都加入栈
        stack.push(node.left);
        node=node.left;
    }

    while(!stack.isEmpty()){//栈不为空，遍历栈的节点的值，然后如果有右子树，则将右子树的左子树连续入栈，直至没有左子树入栈
       TreeNode node1=stack.pop();
       list.add(node1.val);

       if(null!=node1.right){//右子树不为空
           stack.push(node1.right);//将右子树入栈
           node1=node1.right;//切换到右子树
           while(node1.left!=null){//继续加入右子树的左子树
               stack.push(node1.left);
               node1=node1.left;
           }
       }
    }
    return list;
}

评论区大佬的简洁写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    list.add(cur.val);
                    cur = cur.right;
                }
            }
            return list;
        }
    }

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走