Codes – gongel-coder

字符串

151. 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

 

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"
示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"

输出: "blue is sky the"

示例 2：

输入: " hello world! "

输出: "world! hello"

解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good example"

输出: "example good a"

解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。

输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

class Solution {
    public String reverseWords(String s) {
        String[] str=s.split(" ");
        for(int i=0;i<str.length/2;i++){
            String es=str[i];
            str[i]=str[str.length-i-1];
            str[str.length-i-1]=es;
        }
        return String.join(" ", str).trim().replaceAll("\\s{2,}", " ");
    }
}

class Solution {

public String reverseWords(String s) {

String[] str=s.split(" ");

for(int i=0;i<str.length/2;i++){

String es=str[i];

str[i]=str[str.length-i-1];

str[str.length-i-1]=es;

}

return String.join(" ", str).trim().replaceAll("\\s{2,}", " ");

}

179. 最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]

输出: 210

示例 2:

输入: [3,30,34,5,9]

输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

class Solution {
    //"2"+"12">"12"+"2",所以需要排序
    public String largestNumber(int[] nums) {
        if(nums==null || nums.length==0)
            return "0";
            String[] str=new String[nums.length];
        for(int i=0;i<nums.length;i++){
            str[i]=String.valueOf(nums[i]);
        }
        Arrays.sort(str,new Comparator<String>(){
                public int compare(String o1,String o2){
                    return (o2+o1).compareTo(o1+o2);
                }
            });
        if(str[0].equals("0")){//说明原始数组只有一个元素"0"
            return "0";
        }
        String ans=new String();
        for(int i=0;i<str.length;i++){
            ans+=str[i];
        }
        return ans;
    }
}

class Solution {

//"2"+"12">"12"+"2",所以需要排序

public String largestNumber(int[] nums) {

if(nums==null || nums.length==0)

return "0";

String[] str=new String[nums.length];

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

str[i]=String.valueOf(nums[i]);

}

Arrays.sort(str,new Comparator<String>(){

public int compare(String o1,String o2){

return (o2+o1).compareTo(o1+o2);

}

});

if(str[0].equals("0")){//说明原始数组只有一个元素"0"

return "0";

}

String ans=new String();

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

ans+=str[i];

}

return ans;

}

Collections.sort和Arrays.sort自定义排序/部分排序

归并

315. 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]

输出: [2,1,1,0]

解释:

5 的右侧有 2 个更小的元素 (2 和 1).

2 的右侧仅有 1 个更小的元素 (1).

6 的右侧有 1 个更小的元素 (1).

1 的右侧有 0 个更小的元素.

public class Threehundred_fifteen {
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            ans.add(0);
        }
        int[][] index = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            index[i] = new int[]{nums[i], i};
        }
        merge_sort(index, 0, index.length, ans);
        return ans;
    }

    public void merge_sort(int[][] index, int start, int end, List<Integer> ans) {
        if (end - start <= 1)
            return;
        int mid = start + (end - start) / 2;
        merge_sort(index, start, mid, ans);
        merge_sort(index, mid, end, ans);
        int right = mid;
        for (int i = start; i < mid; i++) {
            while (right < end && index[i][0] > index[right][0])
                right++;
            ans.set(index[i][1], ans.get(index[i][1]) + right - mid);
        }
        Arrays.sort(index, start, end, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
    }
}

public class Threehundred_fifteen {

public List<Integer> countSmaller(int[] nums) {

if (nums == null || nums.length == 0)

return new ArrayList<>();

List<Integer> ans = new ArrayList<>();

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

ans.add(0);

}

int[][] index = new int[nums.length][2];

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

index[i] = new int[]{nums[i], i};

}

merge_sort(index, 0, index.length, ans);

return ans;

}

public void merge_sort(int[][] index, int start, int end, List<Integer> ans) {

if (end - start <= 1)

return;

int mid = start + (end - start) / 2;

merge_sort(index, start, mid, ans);

merge_sort(index, mid, end, ans);

int right = mid;

for (int i = start; i < mid; i++) {

while (right < end && index[i][0] > index[right][0])

right++;

ans.set(index[i][1], ans.get(index[i][1]) + right - mid);

}

Arrays.sort(index, start, end, new Comparator<int[]>() {

@Override

public int compare(int[] o1, int[] o2) {

return o1[0] - o2[0];

}

});

}

327. 区间和的个数

给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3 
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:

最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,

输出: 3

解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

package gongel_first;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Threehundred_twentySeven {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0)
            return 0;
        List<Long> list = new ArrayList<>();
        list.add(Long.valueOf(0));
        for (int i = 0; i < nums.length; i++) {
            list.add(list.get(i) + nums[i]);
        }
        return merge_sort(list, 0, list.size(), lower, upper);
    }

    private int merge_sort(List<Long> list, int start, int end, int lower, int upper) {
        if (end - start <= 1)
            return 0;
        int mid = (start + end) / 2;
        int cnt = merge_sort(list, start, mid, lower, upper) + merge_sort(list, mid, end, lower, upper);
        int right1 = mid, right2 = mid;
        for (int i = start; i < mid; i++) {
            while (right1 < end && list.get(right1) - list.get(i) < lower)
                right1++;
            while (right2 < end && list.get(right2) - list.get(i) <= upper)
                right2++;
            cnt += right2 - right1;
        }
        Collections.sort(list.subList(start, end));
        return cnt;
    }
}

package gongel_first;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

public class Threehundred_twentySeven {

public int countRangeSum(int[] nums, int lower, int upper) {

if (nums == null || nums.length == 0)

return 0;

List<Long> list = new ArrayList<>();

list.add(Long.valueOf(0));

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

list.add(list.get(i) + nums[i]);

}

return merge_sort(list, 0, list.size(), lower, upper);

}

private int merge_sort(List<Long> list, int start, int end, int lower, int upper) {

if (end - start <= 1)

return 0;

int mid = (start + end) / 2;

int cnt = merge_sort(list, start, mid, lower, upper) + merge_sort(list, mid, end, lower, upper);

int right1 = mid, right2 = mid;

for (int i = start; i < mid; i++) {

while (right1 < end && list.get(right1) - list.get(i) < lower)

right1++;

while (right2 < end && list.get(right2) - list.get(i) <= upper)

right2++;

cnt += right2 - right1;

}

Collections.sort(list.subList(start, end));

return cnt;

}

线段树

数组下标[i, j]–>线段树[i, (i+j)/2]和[(i+j)/2+1, j]

线段树数组空间为4*len(arr)=4n,证明如下：

预备：二叉树用满二叉树存储

情况一：所有的元素都在最后一层，则分支节点个数为n-1，共需要2n-1空间，已经为满二叉树，不需要补空间；

情况二：只有2个节点在最有一层，另外n-2个节点在倒数第二层，则需要对这n-2个节点补充左右孩子，则需要2(n-2)=2n-4，原始二叉树共有2n-1个节点，那么一共有2n-1+2n-4=4n-5<4n；

综上：开4n空间

307. 区域和检索 – 数组可修改

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:

数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9

update(1, 2)

sumRange(0, 2) -> 8

说明:

数组仅可以在 update 函数下进行修改。

你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

class NumArray {
    public static int[] tree;
    public static int[] nums;
    public static int len;

    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0)
            return;
        this.len = nums.length;
        this.nums = nums;
        this.tree = new int[4 * len];
        buildTree(1, 0, len - 1);
    }

    //start/end是数组的下标，current/left_node/right_node为树的下标
    public void buildTree(int current, int start, int end) {
        if (start == end)
            tree[current] = nums[start];
        else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            buildTree(left_node, start, mid);
            buildTree(right_node, mid + 1, end);
            tree[current] = tree[left_node] + tree[right_node];
        }
    }

    public void update(int i, int val) {
        updateTree(1, 0, len - 1, i, val);
    }

    public void updateTree(int current, int start, int end, int pos, int val) {
        if (start == end) {
            nums[pos] = val;
            tree[current] = val;
        } else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            if (start <= pos && pos <= mid)
                updateTree(left_node, start, mid, pos, val);
            else
                updateTree(right_node, mid + 1, end, pos, val);
            tree[current] = tree[left_node] + tree[right_node];
        }

    }

    public int sumRange(int i, int j) {
        return sumTree(1, 0, len - 1, i, j);
    }

    public int sumTree(int current, int start, int end, int left, int right) {
        if (right < start || left > end)//需要求解的区间不在[start,end]内
            return 0;
        else if (left <= start && right >= end)//[left,right]将[start,end]包含，已经没必要向子节点走了
            return tree[current];
        else if (start == end)
            return tree[current];
        else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            return sumTree(left_node, start, mid, left, right) + sumTree(right_node, mid + 1, end, left, right);
        }
    }
}

class NumArray {

public static int[] tree;

public static int[] nums;

public static int len;

public NumArray(int[] nums) {

if (nums == null || nums.length == 0)

return;

this.len = nums.length;

this.nums = nums;

this.tree = new int[4 * len];

buildTree(1, 0, len - 1);

}

//start/end是数组的下标，current/left_node/right_node为树的下标

public void buildTree(int current, int start, int end) {

if (start == end)

tree[current] = nums[start];

else {

int left_node = 2 * current;

int right_node = 2 * current + 1;

int mid = (start + end) / 2;

buildTree(left_node, start, mid);

buildTree(right_node, mid + 1, end);

tree[current] = tree[left_node] + tree[right_node];

}

public void update(int i, int val) {

updateTree(1, 0, len - 1, i, val);

}

public void updateTree(int current, int start, int end, int pos, int val) {

if (start == end) {

nums[pos] = val;

tree[current] = val;

} else {

int left_node = 2 * current;

int right_node = 2 * current + 1;

int mid = (start + end) / 2;

if (start <= pos && pos <= mid)

updateTree(left_node, start, mid, pos, val);

else

updateTree(right_node, mid + 1, end, pos, val);

tree[current] = tree[left_node] + tree[right_node];

}

public int sumRange(int i, int j) {

return sumTree(1, 0, len - 1, i, j);

}

public int sumTree(int current, int start, int end, int left, int right) {

if (right < start || left > end)//需要求解的区间不在[start,end]内

return 0;

else if (left <= start && right >= end)//[left,right]将[start,end]包含，已经没必要向子节点走了

return tree[current];

else if (start == end)

return tree[current];

else {

int left_node = 2 * current;

int right_node = 2 * current + 1;

int mid = (start + end) / 2;

return sumTree(left_node, start, mid, left, right) + sumTree(right_node, mid + 1, end, left, right);

}

线段树详解

【数据结构】线段树（Segment Tree）

线段树开4N空间证明

processon

桶排序

347. 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

示例 2:

输入: nums = [1], k = 1

输出: [1]

说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。

你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

public class Threehundred_fortySeven {
    /**
     * 桶排序
     * 出现频率为frequency的元素放到下标为frequency的桶中
     * 时间复杂度为O(n)
     */
    public List<Integer> topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums)
            map.put(num, map.getOrDefault(num, 0) + 1);
        List<Integer>[] bucket = new ArrayList[nums.length + 1];
        for (int key : map.keySet()) {//出现频率为frequency的元素放到下标为frequency的桶中
            int frequency = map.get(key);
            if (bucket[frequency] == null)
                bucket[frequency] = new ArrayList<>();
            bucket[frequency].add(key);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = nums.length; i > 0 && ans.size() < k; i--) {
            if (bucket[i] == null)
                continue;
            if (bucket[i].size() <= (k - ans.size()))
                ans.addAll(bucket[i]);
            else
                ans.addAll(bucket[i].subList(0, k - ans.size()));
        }
        return ans;
    }
}

public class Threehundred_fortySeven {

/**

* 桶排序

* 出现频率为frequency的元素放到下标为frequency的桶中

* 时间复杂度为O(n)

public List<Integer> topKFrequent(int[] nums, int k) {

if (nums == null || nums.length == 0)

return new ArrayList<>();

Map<Integer, Integer> map = new HashMap<>();

for (int num : nums)

map.put(num, map.getOrDefault(num, 0) + 1);

List<Integer>[] bucket = new ArrayList[nums.length + 1];

for (int key : map.keySet()) {//出现频率为frequency的元素放到下标为frequency的桶中

int frequency = map.get(key);

if (bucket[frequency] == null)

bucket[frequency] = new ArrayList<>();

bucket[frequency].add(key);

}

List<Integer> ans = new ArrayList<>();

for (int i = nums.length; i > 0 && ans.size() < k; i--) {

if (bucket[i] == null)

continue;

if (bucket[i].size() <= (k - ans.size()))

ans.addAll(bucket[i]);

else

ans.addAll(bucket[i].subList(0, k - ans.size()));

}

return ans;

}

朋友圈DFS/并查集

547. 朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：

N 在[1,200]的范围内。
对于所有学生，有M[i][i] = 1。
如果有M[i][j] = 1，则有M[j][i] = 1。

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入:

[[1,1,0],

[1,1,0],

[0,0,1]]

输出: 2

说明：已知学生0和学生1互为朋友，他们在一个朋友圈。

第2个学生自己在一个朋友圈。所以返回2。

示例 2:

输入:

[[1,1,0],

[1,1,1],

[0,1,1]]

输出: 1

说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意：

N 在[1,200]的范围内。

对于所有学生，有M[i][i] = 1。

如果有M[i][j] = 1，则有M[j][i] = 1。

package gongel_first;

public class Fivehundred_fortySeven {
    /**
     * 法一：DFS
     * 求连通图的数量
     * 与 200 岛屿问题 有不同的地方，连通图问题和上色问题的区别
     * 本题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->1
     * 200题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->4
     */
    private void dfs(int[][] M, int i, boolean[] visited, int m) {
        for (int j = 0; j < m; j++) {
            if (M[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(M, j, visited, m);
            }
        }
    }

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int m = M.length;
        int n = M[0].length;
        boolean[] visited = new boolean[m];
        int numFriends = 0;
        for (int i = 0; i < m; i++) {
            if (!visited[i]) {
                dfs(M, i, visited, m);
                numFriends++;
            }
        }
        return numFriends;
    }

    /**
     * 法二：并查集
     */
    private int findFather(int[] father, int son) {
        while (son != father[son]) {//初始化时自己为自己的父亲，如果现在自己不是自己的父亲， 说明自己找到了真正的父亲，那需要一直循环找到祖先
            son = father[son];
        }
        return son;
    }

    public int findCircleNum2(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int[] father = new int[200];
        int numFriends = 0;
        //初始化
        for (int i = 0; i < M.length; i++)
            father[i] = i;
        for (int i = 0; i < M.length; i++) {
            for (int j = i + 1; j < M.length; j++) {//只需要考虑上三角矩阵，因为这是无向图----对称矩阵
                if (M[i][j] == 1) {
                    int fatherI = findFather(father, i);
                    int fatherJ = findFather(father, j);
                    if (fatherI != fatherJ)
                        father[fatherI] = fatherJ;
                }
            }
        }
        for (int i = 0; i < M.length; i++) {
            if (father[i] == i)
                numFriends++;
        }
        return numFriends;
    }
}

package gongel_first;

public class Fivehundred_fortySeven {

/**

* 法一：DFS

* 求连通图的数量

* 与 200 岛屿问题有不同的地方，连通图问题和上色问题的区别

* 本题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->1

* 200题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->4

private void dfs(int[][] M, int i, boolean[] visited, int m) {

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

if (M[i][j] == 1 && !visited[j]) {

visited[j] = true;

dfs(M, j, visited, m);

}

public int findCircleNum(int[][] M) {

if (M == null || M.length == 0 || M[0].length == 0)

return 0;

int m = M.length;

int n = M[0].length;

boolean[] visited = new boolean[m];

int numFriends = 0;

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

if (!visited[i]) {

dfs(M, i, visited, m);

numFriends++;

}

return numFriends;

}

/**

* 法二：并查集

private int findFather(int[] father, int son) {

while (son != father[son]) {//初始化时自己为自己的父亲，如果现在自己不是自己的父亲，说明自己找到了真正的父亲，那需要一直循环找到祖先

son = father[son];

}

return son;

}

public int findCircleNum2(int[][] M) {

if (M == null || M.length == 0 || M[0].length == 0)

return 0;

int[] father = new int[200];

int numFriends = 0;

//初始化

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

father[i] = i;

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

for (int j = i + 1; j < M.length; j++) {//只需要考虑上三角矩阵，因为这是无向图----对称矩阵

if (M[i][j] == 1) {

int fatherI = findFather(father, i);

int fatherJ = findFather(father, j);

if (fatherI != fatherJ)

father[fatherI] = fatherJ;

}

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

if (father[i] == i)

numFriends++;

}

return numFriends;

}

连通分量的个数（两种方法）

一	二	三	四	五	六	日
« 8月
						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