LeetCode OJ – 第2页 – 柳婼の blog

LeetCode 647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Note:
The input string length won’t exceed 1000.

题目大意：给定一个字符串，计算这个字符串中有多少回文子串。（具有不同start下标或end下标的子字符串即使包含相同的字符也会被计为不同的子字符串。）
分析：对于s[i]来说，检测s[i-j]==s[i+j]是否成立，每一次相等就ans++、检测s[i-j-1]==s[i+j]是否成立，每次成立就ans++，最后返回ans的值～

class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = 0; i + j < n && i - j >= 0 && s[i-j] == s[i+j]; j++) ans++;
            for (int j = 0; i + j < n && i - j - 1 >=0 && s[i-j-1] == s[i+j]; j++) ans++;
        }
        return ans;
    }
};

class Solution {

public:

int countSubstrings(string s) {

int ans = 0, n = s.length();

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

for (int j = 0; i + j < n && i - j >= 0 && s[i-j] == s[i+j]; j++) ans++;

for (int j = 0; i + j < n && i - j - 1 >=0 && s[i-j-1] == s[i+j]; j++) ans++;

}

return ans;

}

};

LeetCode 547. Friend Circles

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
Example 2:
Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.

题目大意：班上有N个学生。有些是朋友，有些则不是。他们的友谊本质上是传递性的。例如，如果A是B的直接朋友，B是C的直接朋友，那么A是C的间接朋友。我们定义了一个朋友圈是一群直接或间接的朋友。给定N * N矩阵M代表班级中学生之间的朋友关系。如果M[i][j] = 1，那么第i和第j个学生是彼此直接的朋友，否则不是，输出所有学生中的朋友圈的总数

分析：用并查集，cnt一开始为n，每个人的父亲也都是自己，将每一对朋友的父亲结点找到，如果他们的父亲结点不是同一个，那么就合并为一个集合，并将cnt-1，最后输出cnt

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size(), cnt = M.size();
        father.resize(n);
        for (int i = 0; i < n; i++) father[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (M[i][j] == 1) {
                    int faA = findFather(i);
                    int faB = findFather(j);
                    if (faA != faB) {
                        father[faA] = father[faB];
                        cnt--;
                    }
                }
                
            }
        }
        return cnt;
    }
private:
    vector<int> father;
    int findFather(int x) {
        return x == father[x] ? x : findFather(father[x]);
    }
};

class Solution {

public:

int findCircleNum(vector<vector<int>>& M) {

int n = M.size(), cnt = M.size();

father.resize(n);

for (int i = 0; i < n; i++) father[i] = i;

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

for (int j = i + 1; j < n; j++) {

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

int faA = findFather(i);

int faB = findFather(j);

if (faA != faB) {

father[faA] = father[faB];

cnt--;

}

return cnt;

}

private:

vector<int> father;

int findFather(int x) {

return x == father[x] ? x : findFather(father[x]);

}

};

LeetCode 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.

题目大意：编写一个有效的算法，在m×n矩阵中搜索一个值。该矩阵具有以下属性：
每行中的整数从左到右依次排列。每列中的整数按从上到下的顺序排列。

分析：对每一行进行binary_serch()，如果能够找到则return true，否则返回false

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size(); i++)
            if (binary_search(matrix[i].begin(), matrix[i].end(), target)) return true;
        return false;
    }
};

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

for(int i = 0; i < matrix.size(); i++)

if (binary_search(matrix[i].begin(), matrix[i].end(), target)) return true;

return false;

}

};

LeetCode 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.

题目大意：编写一个有效的算法，在m×n矩阵中搜索一个值。该矩阵具有以下属性：
每行中的整数从左到右排序。每行的第一个整数大于前一行的最后一个整数。

分析：对每一行进行二分搜索，如果找到了就返回true否则返回false～

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size(); i++)
            if (binary_search(matrix[i].begin(), matrix[i].end(), target)) return true;
        return false;
    }
};

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

for(int i = 0; i < matrix.size(); i++)

if (binary_search(matrix[i].begin(), matrix[i].end(), target)) return true;

return false;

}

};

LeetCode 655. Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules:

The row number m should be equal to the height of the given binary tree.
The column number n should always be an odd number.
The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
Each unused space should contain an empty string “”.
Print the subtrees following the same rules.
Example 1:
Input:
1
/
2
Output:
[[“”, “1”, “”],
[“2”, “”, “”]]
Example 2:
Input:
1
/ \
2 3
\
4
Output:
[[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“”, “”, “4”, “”, “”, “”, “”]]
Example 3:
Input:
1
/ \
2 5
/
3
/
4
Output:

[[“”, “”, “”, “”, “”, “”, “”, “1”, “”, “”, “”, “”, “”, “”, “”]
[“”, “”, “”, “2”, “”, “”, “”, “”, “”, “”, “”, “5”, “”, “”, “”]
[“”, “3”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]
[“4”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]]
Note: The height of binary tree is in the range of [1, 10].

题目大意：按照以下规则在一个m * n的二维字符串数组中打印一个二叉树：
行号m应该等于给定二叉树的高度。
列号n应始终为奇数。
根节点的值（以字符串格式）应该放在第一行的正中间。根节点所属的行和列将剩余空间分成两部分（左下部分和右下部分）。您应该在左下角打印左侧子树，并在右下侧打印右侧子树。左下部分和右下部分应该具有相同的尺寸。即使一个子树不存在，而另一个子树不存在，您也不需要为无子树打印任何东西，但仍然需要留下与另一子树相同的空间。但是，如果两个子树都没有，那么你就不需要为它们留下空间。
每个未使用的空间应该包含一个空字符串“”。
按照相同的规则打印子树。

分析：首先计算出树的高度h，然后建立h行、(2的h次方-1)列的字符串数组，进行先序遍历，设立l和r表示当前填充的子树对应的字符串数组的左右下标区域，h表示当前的层数，每次将root->val的值存储入ans[h][mid]中，其中mid=(l+r)/2，然后继续遍历左子树和右子树，将区间分为0～mid-1和mid+1～r，高度h加1，直至遍历完成后返回ans数组～

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<string>> printTree(TreeNode* root) {
        int h = height(root);
        int c = pow(2, h) - 1;
        vector<vector<string>> ans(h, vector<string>(c));
        dfs(root, 0, c-1, 0, ans);
        return ans;
    }
private:
    int height(TreeNode* root) {
        if (root == NULL) return 0;
        return max(height(root->left), height(root->right)) + 1;
    }
    void dfs(TreeNode* root, int l, int r, int h, vector<vector<string>>& ans) {
        if (root == NULL) return;
        if (l > r) return;
        int mid = (l + r) / 2;
        ans[h][mid] = to_string(root->val);
        dfs(root->left, l, mid-1, h+1, ans);
        dfs(root->right, mid+1, r, h+1, ans);
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

vector<vector<string>> printTree(TreeNode* root) {

int h = height(root);

int c = pow(2, h) - 1;

vector<vector<string>> ans(h, vector<string>(c));

dfs(root, 0, c-1, 0, ans);

return ans;

}

private:

int height(TreeNode* root) {

if (root == NULL) return 0;

return max(height(root->left), height(root->right)) + 1;

}

void dfs(TreeNode* root, int l, int r, int h, vector<vector<string>>& ans) {

if (root == NULL) return;

if (l > r) return;

int mid = (l + r) / 2;

ans[h][mid] = to_string(root->val);

dfs(root->left, l, mid-1, h+1, ans);

dfs(root->right, mid+1, r, h+1, ans);

}

};

LeetCode 537. Complex Number Multiplication

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.

Example 1:
Input: “1+1i”, “1+1i”
Output: “0+2i”
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Example 2:
Input: “1+-1i”, “1+-1i”
Output: “0+-2i”
Explanation: (1 – i) * (1 – i) = 1 + i2 – 2 * i = -2i, and you need convert it to the form of 0+-2i.
Note:

The input strings will not have extra blank.
The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

题目大意：给两个复数，求两个数的乘积～

分析：使用sscanf和ssprinf，(m+ni)*(p+qi)=(m*p-n*q)*(n*p+m*q) i

class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        char t[200];
        int m, n, p, q;
        sscanf(a.c_str(), "%d+%di", &m, &n);
        sscanf(b.c_str(), "%d+%di", &p, &q);
        sprintf(t, "%d+%di", (m*p-n*q), (n*p+m*q));
        string ans = t;
        return ans;
    }
};

class Solution {

public:

string complexNumberMultiply(string a, string b) {

char t[200];

int m, n, p, q;

sscanf(a.c_str(), "%d+%di", &m, &n);

sscanf(b.c_str(), "%d+%di", &p, &q);

sprintf(t, "%d+%di", (m*p-n*q), (n*p+m*q));

string ans = t;

return ans;

}

};