Welcome to BeckoninGshy's Bolg

LeetCode-22-括号生成

22. 括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

Solution：

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:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        putone("",n,n,result);
        return result;
    }
    void putone(string item, int left, int right, vector<string> &result){
       if(left == 0 && right == 0){
           result.push_back(item);
           return;
       }
        //只要left还能放。
        if(left > 0){
            putone(item+ "(",left-1,right,result);
        }
        //left放的比right多，
        if(left < right){
            putone(item+ ")",left,right-1,result);
        }
    }
};

使用递归+回溯来解决。

该题主要是要找放括号的时机。

首先要先放左括号。

第二，只要放左括号的个数比右括号多，就可以放右括号。

阅读更多
LeetCode-190-颠倒二进制位

190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

输入: 00000010100101000001111010011100

输出: 00111001011110000010100101000000

解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t t = 0;
        int i = 32;
        while(i--){
            t <<= 1;
            //获得原数第一位的状态。
            int a = n&1;
            //将该状态赋给该数第一位。
            t |= a;
            //原数右移。
            n >>= 1;
        }
        return t;
    }
};

思路：

初始化一个全位置为0的数，将原数的最后一位赋给该数的最后一位，原数右移，该数左移，如此32次。

阅读更多
LeetCode-167-两数之-I--输入有序数组

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> a;
        int lower = 0;
        int higher = numbers.size()-1;
        while(lower < higher){
            if(numbers[lower] + numbers[higher] < target){
                lower++;
            }else if(numbers[lower] + numbers[higher] > target){
                higher--;
            }else{
                a.push_back(lower+1);
                a.push_back(higher+1);
                break;
            }
        }
        return a;
    }
};

使用双指针技巧，一个从前扫描，一个从后扫描。符合条件退出。

阅读更多
LeetCode-191-位1的个-&- 231-2的幂

191. 位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

Solution1：

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

思路：

将每一位移到最后一位检查是否为1，到0为止，最后返回个数。

由于是无符号整型，每次都会执行32次，所以时间复杂度是O(1)。

Solution2（优化）：

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

看了官方题解，这种方法是每一次将最后一个1给消除。这样顶多执行k次，k就为1的个数。这样就又优化了一点点计算。

eg：

11010 & 11001 = 11000

11000 & 10111 = 10000

10000 & 01111 = 0

231. 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

有了上面的思路：

这道题就可以写成这样：

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && !(n & (n-1));
    }
};

2的n次方在二进制中就是只有1个位置是1，其他全是0（对于正数）。

阅读更多
LeetCode-142-环形链-II

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

Solution1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        std::set<ListNode*> node_set;
        while(head){
            if(node_set.find(head) == node_set.end()){
                node_set.insert(head);
            }else{
                return head;
            }
            head = head->next;
        }
        return NULL;
    }
};

与141号问题的Solutions1一个思路，直接使用set。只不过返回的是结点不是boolean值罢了。

Solutions2:
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
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode * head1 = head;
        ListNode * slow = head;
        ListNode * fast = head;
        //fast走一步，slow走两步
        while(fast){
            slow = slow->next;
            fast = fast->next;
            if(fast){
                fast = fast->next;
            }else{ //没有环退出
                return NULL;
            }
            //有环退出循环
            if(fast == slow){
                break;
            }
        }
        //说明有环
        while(head1 && fast){
            if(head1 == fast){
                return fast;
            }
            head1 = head1->next;
            fast = fast->next;
            
        }
        //不会走到这步，只是为了保证函数正常运行
        return NULL;
    }
};
思路：

这种方法只会使用O(1)的空间。

该方法的思路需要一点数学基础：

在一个有环的链表中，slow指针与fast指针相遇，从该相遇的位置开始，与链表的头位置开始，两者走同样的步数，如果两者相交，就走到了环的开始位置。

image

阅读更多
LeetCode-153-寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

1
2
输入: [3,4,5,1,2]
输出: 1

示例 2:

1
2
输入: [4,5,6,7,0,1,2]
输出: 0

Solution：

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 findMin(vector<int>& nums) {
        int lo = 0;
        int hi = nums.size()-1;
        while(lo < hi){
            int mid = (lo+hi)/2;
            //如果比右边大，说明在逆序数组中。
            //从mid位置的下一个元素继续查找。
            if(nums[mid] > nums[hi]){
                lo = mid+1;
            }
            //如果不比右边的大，说明已在正序数组中。
            // 缩小右边的范围。
            else{
                hi = mid;
            }
        }
        //hi == lo
        return nums[lo];
    }
};

使用二分法。

当中间元素比右边界要大时，说明在逆序数组中，这时，令lo = mid + 1。

否则说明在顺序数组中，不断缩小范围直到 lo = hi 时，返回。

阅读更多
LeetCode-136-只出现一次的数字

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

Solution：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0;
        for(int i = 0; i < nums.size(); i++){
            a = a ^ nums[i];
        }
        return a;
    }
};

使用异或来消除相同的元素。
异或：
两数相同，异或为0；
两数不同，异或为1；

  • a ^ a = 0;
  • a ^ 0 = a;
阅读更多
LeetCode-113-路径总-II

113. 路径总和 II

该题为112. 路径总和的升级版

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

Solution1：

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
/**
 * 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<int>> pathSum(TreeNode* root, int sum) {
        vector<int> path;
        vector<vector<int> > result;
        if(root){
            dfs(root,0,sum,path,result);
        } 
        return result;
    }
    
    void dfs(TreeNode* node,int currentsum, int sum,vector<int> &path,vector<vector<int> > &result){
        currentsum += node->val;

        path.push_back(node->val);
        //当到达叶子结点，并且路径之和与sum相同
        if(node && !node->left && !node->right ){
            if(currentsum == sum)
            result.push_back(path);
            return;
        }
        if(node->left){
            dfs(node->left,currentsum,sum,path,result);
            //回溯，还原状态
            path.pop_back();
        }
        if(node->right){
            dfs(node->right,currentsum,sum,path,result);
            //回溯，还原状态
            path.pop_back();
        }
        
    }
};

Solution2：

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
/**
 * 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<int>> pathSum(TreeNode* root, int sum) {
        vector<int> path;
        vector<vector<int> > result;
        preorder(root,0,sum,path,result);
        return result;
    }
    void preorder(TreeNode* node, int currentsum, int sum, vector<int> &path, vector<vector<int> > &result){
        if(!node) return;
        currentsum += node->val;
        path.push_back(node->val);
        if(!node->left && !node->right && currentsum == sum){
            result.push_back(path);
        }
        preorder(node->left,currentsum,sum,path,result);
        preorder(node->right,currentsum,sum,path,result);
        //该步可有可无，因为只会递归到叶子节点才返回，又每次递归都在栈中保留了原来该值的副本。
        // currentsum -= node->val;
        path.pop_back();
    }
};
阅读更多
LeetCode-112-路径总和

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

Solution1:

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
/**
 * 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:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        return dfs(root,0,sum);
    }
    
    bool dfs(TreeNode* node,int currentsum, int sum){
        currentsum += node->val;
        if(node && !node->left && !node->right && currentsum == sum)
            return true;
        bool a = false,b = false;
        if(node->left){
            a = dfs(node->left,currentsum,sum);
        }
        if(node->right){
            b = dfs(node->right,currentsum,sum);
        }
        return a || b;
    }
};

递归终止条件为叶子节点。

阅读更多
LeetCode-107-二叉树的层次遍-II

107. 二叉树的层次遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

该题为 102. 二叉树的层次遍历的进阶版。

有关102. 二叉树的层次遍历的题解，请参考429. N叉树的层序遍历，具体思路是一样的，不再赘述。

Solution1（迭代版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int> > res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int len = q.size();
            vector<int> curLayerNodes;
            TreeNode* t;
            while(len--){
                t = q.front();
                q.pop();
                curLayerNodes.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            res.emplace(res.begin(),curLayerNodes);
        }
        return res;
    }
};

Solution2（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        preorder(root,1,res);
        return res;
    }
    
    void preorder(TreeNode* node, int depth, vector<vector<int>> &res){
        if(!node) return;
        if(res.size() < depth){
            vector<int> t;
            t.push_back(node->val);
            res.emplace(res.begin(), t);
        }else{
            res[res.size()-depth].push_back(node->val);
        }
        preorder(node->left, depth+1, res);
        preorder(node->right, depth+1, res);
    }
};

具体思路就是增加一层，就将该层放到头位置。

vector.emplace()配合vector.begin()实现插到头位置。

阅读更多
首页 归档 标签 关于 搜索