发表于   |  

参考了 《挑战程序设计竞赛》 第二版 P88

　　并查集可以高效地进行如下操作：

  • 查询元素a和元素b是否属于同一组
  • 合并a和b所在的组

　　下面看下并查集常用方法init, find, unit, same的代码

阅读全文 »

发表于   |   分类于   |  

Gopl Chaper 01 要点

-Go是编译型语言，当你运行go run hello.go，会经历编译，链接，执行。

  • Go原生支持Unicode编码。

  • Go通过package的概念组织代码，每个源代码文件属于某个package。

  • package main比较特殊，它定义了单独执行的程序，而不是一个库，因此main包是程序的入口。

  • 可以使用import的方式引入其它package，但要注意不要少引入或多余引入package，这样程序将不能编译通过。

  • Go不允许未使用的局部变量存在

  • 一个function由关键字func，名字，参数列表，返回列表，函数体

  • Go语言中的语句不需要分号在结尾，除非多条语句写在一行

  • 注意{要跟func在同一行

  • 变量通过var定义：

    1
    var s, sep string

　　变量可以在定义时初始化，也可以不进行初始化，未进行初始化的，如果是整数，默认值0，string默认值是 空串""

阅读全文 »

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/rotate-image/

　　将正方形矩阵顺时针旋转90度，要求空间复杂度O(1)

题目分析

　　纯的数学坐标变换就可以，倒换4个元素的位置，位置下标算清楚就可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int n = matrix.length;
        for (int i = n - 1, row = 0; i >= 1; i -= 2, row++) {  // i表示当前行需要有多少个元素做移动
            for (int j = row; j < row + i; j++) {
                int tmp = matrix[row][j];
                matrix[row][j] = matrix[2 * row + i - j][row];
                matrix[2 * row + i - j][row] = matrix[row + i][2 * row + i - j];
                matrix[row + i][2 * row + i - j] = matrix[j][row + i];
                matrix[j][row + i] = tmp;
            }             
        }
    }
}