LeetCode 467. Unique Substrings in Wraparound String

Dec 5, 2016

题目描述:

Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

1
2
3
4
5
Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

1
2
3
4
Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

1
2
3
Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

动态规划题目. dp[i]记录以p[i]为结尾的符合要求的子串的长度. 为了防止重复, 用另一个数组tail以字母为索引保存结果中以某个字母结尾的最长的子串的长度. 当p[i]与p[i-1]是连续的时候, p[i]=p[i-1]; 否则p[i]=1. 再检查tail[p[i]-'a']与dp[i]的大小关系, 若tail[p[i]-'a']>=dp[i], 说明p[i]结尾的所有子串都已经在结果中了; 否则更新tail[p[i]-'a']=dp[i], 增加结果集中以p[i]这个字母结尾的子串的数量. 最后再对tail数组求和就得到结果. 时间复杂度O(n).

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 {
public:
    int findSubstringInWraproundString(string p) {
        if(p.empty()) return 0;
        vector<int> dp(p.length(), 0);
        vector<int> tail(26, 0);
        dp[0] = 1;
        tail[p[0] - 'a'] = 1;
        for(int i = 1; i < p.length(); i++){
            if((p[i - 1] != 'z' && p[i] == p[i - 1] + 1) || (p[i - 1] == 'z' && p[i] == 'a')){
                dp[i] = dp[i - 1] + 1;
            }
            else{
                dp[i] = 1;
            }
            int index = p[i] - 'a';
            tail[index] = max(tail[index], dp[i]);
        }
        int ans = 0;
        for(auto i : tail){
            ans += i;
        }
        return ans;
    }
};

LeetCode 201. Bitwise AND of Numbers Range

Dec 4, 2016

题目描述:

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

位运算题目. 两个数m与n, 从最高位开始往低位看的话, 前面的许多位是相同的, 从某一位开始变得不同, 而这之后的所有位在结果中必然为0(因为中间肯定出现了0和1). 我们把m和n相减后得到的值就是这个阈值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int minus = n - m + 1;
        int re = 0;
        for(int i = 0; i < 31; i++){
            int t = 1 << i;
            if(minus > t){
                re = re & (~t);
            }
            else{
                if((t & m) & (t & n)){
                    re = re | t;
                }
                else{
                    re = re & (~t);
                }
            }
        }
        return re;
    }
};

LeetCode 200. Number of Islands

Dec 4, 2016

题目描述:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

1
2
3
4
11110
11010
11000
00000

Answer: 1

Example 2:

1
2
3
4
11000
11000
00100
00011

Answer: 3

使用BFS遍历即可.

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
class Solution {
    vector<vector<int>> visited;
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        if(grid[0].empty()) return 0;
        int islandNum = 0;
        visited = vector<vector<int>>(grid.size(), vector<int>(grid[0].size(), false));
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == '1' && !visited[i][j]) {
                    BFS(grid, i, j);
                    ++islandNum;
                }
            }
        }
        return islandNum;
    }
    
    void BFS(vector<vector<char>> &g, int x, int y){
        visited[x][y] = true;
        g[x][y] = '0';
        queue<pair<int, int>> BFS;
        BFS.push(pair<int, int>(x, y));
        while(!BFS.empty()){
            pair<int, int> pos = BFS.front();
            int curX = pos.first, curY = pos.second;
            if(curX - 1 >= 0 && g[curX - 1][curY] == '1' && !visited[curX - 1][curY]){
                BFS.push(pair<int, int>(curX - 1, curY));
                visited[curX - 1][curY] = true;
            }
            if(curX + 1 < g.size() && g[curX + 1][curY] == '1' && !visited[curX + 1][curY]){
                BFS.push(pair<int, int>(curX + 1, curY));
                visited[curX + 1][curY] = true;
            }
            if(curY - 1 >= 0 && g[curX][curY - 1] == '1' && !visited[curX][curY - 1]){
                BFS.push(pair<int, int>(curX, curY - 1));
                visited[curX][curY - 1] = true;
            }
            if(curY + 1 < g[0].size() && g[curX][curY + 1] == '1' && !visited[curX][curY + 1]){
                BFS.push(pair<int, int>(curX, curY + 1));
                visited[curX][curY + 1] = true;
            }
            
            BFS.pop();
        }
    }
};

LeetCode 199. Binary Tree Right Side View

Dec 4, 2016

题目描述:

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree,

1
2
3
4
5
6
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

我用DFS对二叉树进行遍历, 先遍历右节点再遍历左节点. 把每次遍历到的新的一层的第一个节点加入结果中.

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
/**
 * 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<int> rightSideView(TreeNode* root) {
        if(!root) return vector<int>();
        vector<int> ans;
        DFS(root, ans, 1);
        return ans;
    }
    
    void DFS(TreeNode *node, vector<int> &ans, int level){
        if(!node) return;
        if(level > ans.size()){
            ans.push_back(node->val);
        }
        DFS(node->right, ans, level + 1);
        DFS(node->left, ans, level + 1);
    }
};

LeetCode 463. Island Perimeter

Dec 3, 2016

题目描述:

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

1
2
3
4
5
6
7
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

遍历整个二维数组, 对于每块陆地, 计算该块陆地与"水域"接触的边的数量, 这个数量范围为[0,4], 岛屿的总周长等于每块陆地与水域接触的边的数量之和.

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
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int ans = 0;
        if(grid.empty() || grid[0].empty()) return 0;
        int row = grid.size(), col = grid[0].size();
        
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 1)
                    ans += getPerimeter(grid, i, j);
            }
        }
        return ans;
    }
    
    int getPerimeter(vector<vector<int>>& grid, int x, int y){
        int ans = 0;
        int row = grid.size(), col = grid[0].size();
        if(x == 0 || grid[x - 1][y] == 0){
            ans++;
        }
        if(x == row - 1 || grid[x + 1][y] == 0){
            ans++;
        }
        if(y == 0 || grid[x][y - 1] == 0){
            ans++;
        }
        if(y == col - 1 || grid[x][y + 1] == 0){
            ans++;
        }
        return ans;
    }
};

LeetCode 462. Minimum Moves to Equal Array Elements II

Dec 3, 2016

题目描述:

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array’s length is at most 10,000.

Example:

1
2
3
4
5
6
7
8
9
10
Input:
[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

这道题我的首先思路是先找到最终每个元素所等于的值再计算需要的步数.

先考虑三个数$a_1 \ge a_2 \ge a_3$, 我们要找一个数$n$使得$|a_1-n|+|a_2-n|+|a_3-n|$最小. 比较容易想到$n$应该在区间$[a_1,a_3]$之间, 所以我们假设一个新的$n$, 满足$a_1 \ge a_2+n \ge a_3$, $a_2+n$就是我们要找的值. 这时我们要使$[a_1-(a_2+n)] + |n| + [(a_2 + n) - a_3]$最小. $$ [a_1-(a_2+n)] + |n| + [(a_2 + n) - a_3] = a_1 - a_3 + |n| $$ 发现在$n=0$的时候才能取到最小值$a_1 - a_3$, 所以最终每个元素应有的值是原来所有元素的值的中位数.

以上是奇数的情况, 那么偶数的时候中位数有两个候选. 我们再假设$a_1 \ge a_2 \ge a_3 \ge a_4$, 当选择$a_2$作为最后的目标时, 总步数为$(a_1 - a_2) + (a_2 - a_3) + (a_2 - a_4) = a_1 - a_3 +a_2 - a_4$, 当选择$a_3$作为最后目标时, 总步数为$(a_1 - a_3) + (a_2 - a_3) + (a_3 - a_4) = a_1 - a_3 + a_2 - a_4$, 两种情况是相同, 因此我们只要随便选一个就可以了.

关于找到中位数, 不需要使用sort对所有数据进行排序, 可以使用nth_element来节省时间.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minMoves2(vector<int>& nums) {
        int midIndex = nums.size() / 2;
        nth_element(nums.begin(), nums.begin() + midIndex, nums.end());
        int mid = nums[midIndex];
        int ans = 0;
        for(auto i : nums){
            ans += abs(i - mid);
        }
        return ans;
    }
};

LeetCode 198. House Robber

Nov 20, 2016

题目描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

简单的动态规划问题. 相邻的房子不能同时入侵, 所以如果前一个房子入侵过了, 当前的房子就不能入侵.

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
            return nums[0];
        int dp[nums.size()];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

LeetCode 191. Number of 1 Bits

Nov 20, 2016

题目描述:

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

位运算.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while(n > 0){
            if(n & 1)
                ret++;
            n = n >> 1;
        }
        
        return ret;
    }
};

LeetCode 190. Reverse Bits

Nov 20, 2016

题目描述:

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

翻转一个32位整数的每一个位.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        for(int i = 0; i < 16; i++){
            swapIntBit(n, i);
        }
        return n;
    }

    void swapIntBit(uint32_t &n, int i){
        uint32_t b1 = n & (1 << i);
        uint32_t b2 = n & (((unsigned int)0x80000000) >> i);
        n &= ~(1 << i);
        n &= ~(((unsigned int)0x80000000) >> i);
        n |= b1 << (31 - i * 2);
        n |= b2 >> (31 - i * 2);
    }
};

LeetCode 189. Rotate Array

Nov 18, 2016

题目描述:

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

循环右移, 没啥好说的…可以选择一起移动, 也可以选择一个元素一个元素移动; 前者时间复杂度低, 后者空间复杂度低.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        vector<int> tmp(nums.begin(), nums.begin() + (nums.size() - k));
        nums.erase(nums.begin(), nums.begin() + (nums.size() - k));
        for(auto i : tmp){
            nums.push_back(i);
        }
    }
};