leetcode升级记-初级

最近在努力的找工作，所以开始刷算法题了。昨天突然发现leetcode的官方中文版，但是没有讨论版面，好的一点是探索功能里有刷题指南，适合我这个懒人。好久没写算法了，从初级开始！

然后许个愿可以找到心仪的工作。

数组

从排序数组中删除重复项

给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次,并返回新的长度。

不要另外定义一个数组，您必须通过用 O(1) 额外内存原地修改输入的数组来做到这一点。

示例：

给定数组: nums = [1,1,2],

你的函数应该返回新长度 2, 并且原数组nums的前两个元素必须是1和2
不需要理会新的数组长度后面的元素

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int k = 0;
        int n = nums.size();
        for(int i=1;i<n;i++){
            if(nums[i] != nums[k]){
                nums[++k] = nums[i];
            }
        }
        nums.resize(k+1);
        return k+1;
    }
};

买卖股票的最佳时机 II

假设有一个数组，它的第 i 个元素是一个给定的股票在第 i 天的价格。

设计一个算法来找到最大的利润。你可以完成尽可能多的交易（多次买卖股票）。然而，你不能同时参与多个交易（你必须在再次购买前出售股票）。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for(int i=1; i<prices.size(); i++){
            if(prices[i] > prices[i-1]){
                sum += prices[i] - prices[i-1];
            }
        }
        return sum;
    }
};

旋转数组*

将包含 n 个元素的数组向右旋转 k 步。

例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

注意:

尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。

提示:

要求空间复杂度为 O(1)

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();        
        if(k >= n){
            k %= n;
        }
        if(nums.empty() || k == 0){
            return;
        }
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

注意k大于等于n的情况。

存在重复

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数应该返回 true。如果每个元素都不相同，则返回 false。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.empty()){
            return false;
        }
        set<int> set;
        for(int i=0; i<nums.size(); i++){
            
            if(set.find(nums[i]) != set.end()){
                return true;
            }
            set.insert(nums[i]);
        }
        return false;
    }
};

只出现一次的数字*

给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。

备注：

你的算法应该是一个线性时间复杂度。 你可以不用额外空间来实现它吗？

正常思路是用set或者新建一个不重复的思路，都是额外空间复杂度$O(N)$。分享两个比较诡谲的思路：

1. 异或，可以实现没有额外空间。这个blog对异或解释非常清晰，适合深入了解一下。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        if(nums.size()==1){
            return nums[0];
        }  
        int result = nums[0];
        for(int i=1; i<nums.size(); i++){
            result ^= nums[i];
        }
        return result;
    }
};

1. 这个的空间复杂度是$O(N)$，用python写，就这一行，2333。

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return  2*sum(set(nums)) - sum(nums)

两个数组的交集 II*

给定两个数组，写一个方法来计算它们的交集。

例如:
给定nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

注意：

• 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。

• 我们可以不考虑输出结果的顺序。

跟进:

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1的大小比 nums2小很多，哪种方法更优？
• 如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        vector<int> res;
        for(int i=0; i<nums1.size(); i++){
            map[nums1[i]]++;
        }
        for(int i=0; i<nums2.size(); i++){
            if(map.find(nums2[i]) != map.end() && --map[nums2[i]] >= 0){
                res.push_back(nums2[i]);
            }
        }
        return res;       
    }
};

加一

给定一个非负整数组成的非空数组，给整数加一。

可以假设整数不包含任何前导零，除了数字0本身。

最高位数字存放在列表的首位。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for(int i=n-1; i>=0; i--){
            if(digits[i]++ < 9){
                return digits;
            }else{
                digits[i] %= 10;
            }
        }
        digits[0]++;
        digits.push_back(0);
        return digits;
    }
};

移动零

给定一个数组 nums, 编写一个函数将所有 0 移动到它的末尾，同时保持非零元素的相对顺序。

例如， 定义 nums = [0, 1, 0, 3, 12]，调用函数之后， nums 应为 [1, 3, 12, 0, 0]。

注意事项:

1. 必须在原数组上操作，不要为一个新数组分配额外空间。
2. 尽量减少操作总数。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int count = 0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] == 0){
                count ++;
                nums.erase(nums.begin()+i);
                i--;
            }
        }
        for(int i=0; i<count; i++){
            nums.push_back(0);
        }
    }
};

需要注意的是vector的erase删除后指向了下一个元素，对连续两个0的情况就是失效了，所以需要把i退回去。

两数之和*

给定一个整数数列，找出其中和为特定值的那两个数。

你可以假设每个输入都只会有一种答案，同样的元素不能被重用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        vector<int> result;
        for(int i=0; i<nums.size(); i++){
            if(map.find(target - nums[i]) != map.end()){
                result.push_back(map[target - nums[i]]);
                result.push_back(i);
                break;
            }
            map[nums[i]] = i;
        }
        return result;
    }
};

典型运用hashmap的例子。

有效的数独

判断一个数独是否有效，根据：Sudoku Puzzles - The Rules。

数独部分填了数字，空的部分用 '.' 表示。

一个部分填充是有效的数独。

说明:
一个有效的数独（填了一部分的）不一定是可解的，只要已经填的数字是有效的即可。

旋转图像*

给定一个 n × n 的二维矩阵表示一个图像。

将图像旋转 90 度（顺时针）。

注意：

你必须在原矩阵中旋转图像，请不要使用另一个矩阵来旋转图像。

例 1:

给出的输入矩阵 = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

旋转输入矩阵，使其变为 :
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

例 2:

给出的输入矩阵 =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

旋转输入矩阵，使其变为 :
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int a = 0, b = 0;
        int c = n-1, d = n-1;
        while(a<c){
            rotateEdge(matrix,a++,b++,c--,d--);
        }
    }
    void rotateEdge(vector<vector<int>>& m, int a, int b, int c,int d){
        int times = d - b;
        for(int i=0; i!= times; i++){
            int temp = m[a][b+i];
            m[a][b + i] = m[c - i][b];
			m[c - i][b] = m[c][d - i];
			m[c][d - i] = m[a + i][d];
            m[a+i][d] = temp;
        }
    }
};

这是一个扣边界的题，思路就是从外面到里面一圈一圈的旋转。

字符串

反转字符串

请编写一个函数，其功能是将输入的字符串反转过来。

示例：

输入：s = "hello"
返回："olleh"

class Solution {
public:
    string reverseString(string s) {
        int i=0, j = s.size()-1;
        while(i<j){
            swap(s[i++],s[j--]);
        }
        return s;
    }
};

头尾交换直到走到中间停止。

颠倒整数

给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

class Solution {
public:
    int reverse(int x) {
        int orig = x;
        int result = 0;
        while(orig){
            int dig = orig % 10;
            int temp = dig + result * 10;
            orig /= 10;
            if(temp / 10 != result){
                result = 0;
                break;
            }
            result = temp;
        }
        return result;
    }
};

注意要考虑溢出的情况。

字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> map;
        for(int i=0; i<s.size(); i++){
            map[s[i]]++;
        }
        for(int i=0; i<s.size(); i++){
            if(map[s[i]] == 1){
                return i;
            }
        }
        return -1;
    }
};

利用map实现

链表

删除链表的结点

请编写一个函数，使其可以删除某个链表中给定的（非末尾的）节点，您将只被给予要求被删除的节点。

比如：假设该链表为 1 -> 2 -> 3 -> 4 ，给定您的为该链表中值为 3 的第三个节点，那么在调用了您的函数之后，该链表则应变成 1 -> 2 -> 4 。

class Solution {
public:
    void deleteNode(ListNode* node) {
        *node = *node->next;
    }
};

删除链表的倒数第N个结点

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head){
            return nullptr;
        }
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *fast = &dummy, *slow = &dummy;
        for(int i=0; i<n; i++){
            fast = fast->next;
        }
        while(fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode *del = slow->next;
        slow->next = slow->next->next;
        delete del;
        
        return dummy.next;
    }
};

利用快慢指针实现，快指针先走n步，当快指针走到最后时慢指针所在就是要删除的结点。

回文链表

请检查一个链表是否为回文链表。

进阶：
你能在 O(n) 的时间和 O(1) 的额外空间中做到吗？

环形链表

给定一个链表，判断链表中否有环。

补充：
你是否可以不用额外空间解决此题？

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != NULL && fast->next->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

快慢指针问题，如果有环一定会相遇，相当于跑步套圈。

树

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶节点的最长路径上的节点数。

案例：
给出二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回最大深度为 3 。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL){
            return 0;
        }
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return left > right ? (left + 1) : (right + 1);
    }
};

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

一个二叉搜索树有如下定义：

• 左子树只包含小于当前节点的数。
• 右子树只包含大于当前节点的数。
• 所有子树自身必须也是二叉搜索树。

示例 1：

  2
 / \
1   3

二叉树[2,1,3], 返回 true.

示例 2：

  1
 / \
2   3

二叉树 [1,2,3], 返回 false.

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == NULL) return true;
        stack<TreeNode*> toVisit;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while(cur || !toVisit.empty()){
            if(cur){
                toVisit.push(cur);
                cur = cur->left;
            }else{
                cur = toVisit.top();
                toVisit.pop();
                if(pre != NULL && cur->val <= pre->val){
                    return false;
                }
                pre = cur;
                cur = cur->right;
            }
        }
        return true;
    }
};

对称二叉树

给定一个二叉树，检查它是否是它自己的镜像（即，围绕它的中心对称）。

例如，这个二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是:

  1
 / \
2   2
 \   \
 3    3

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return isSymmetric(root->left, root->right);
    }
    bool isSymmetric(TreeNode* left, TreeNode* right) {
        if(left == NULL && right == NULL) return true;
        if(left == NULL || right == NULL) return false;
        if(left->val != right-> val) return false;
        if(left->val == right->val){
            return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
        }
    }
};

二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。 （即zhu’ceng’de，从左到右访问）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果为：

[
  [3],
  [9,20],
  [15,7]
]

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> queue;
        vector<int> level;
        if(root == NULL) return res;
        queue.push(root);
        while(!queue.empty()){
            level.clear();
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode* node = queue.front();
                queue.pop();
                level.push_back(node->val);
                if(node->left){
                    queue.push(node->left);
                }
                if(node->right){
                    queue.push(node->right);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

此题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例:

给定有序数组: [-10,-3,0,5,9],

一种可行答案是：[0,-3,9,-10,null,5]，它可以表示成下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return NULL;
        int mid = n/2;
        TreeNode* root = new TreeNode(nums[mid]);
        if(n == 1) return root;
        vector<int> left(nums.begin(),nums.begin()+mid);
        vector<int> right(nums.begin()+mid+1,nums.end());
        root->left = sortedArrayToBST(left);
        root->right = sortedArrayToBST(right);
        return root;
    }
};

排序和搜索

合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1中，使得 num1 成为一个有序数组。

注意:

你可以假设 nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。在 nums1 和 nums2 中初始化的元素的数量分别是 m 和 n。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        while(m > 0 && n > 0){
            if(nums1[m-1] >= nums2[n-1]){
                nums1[m+n-1] = nums1[m-1];
                m--;
            }else{
                nums1[m+n-1] = nums2[n-1];
                n--;
            }
        }
        while(n > 0){
            nums1[n-1] = nums2[n-1];
            n--;
        }
    }
};

第一个错误的版本

你是产品经理，目前正在领导一个团队开发一个新产品。不幸的是，您的产品的最新版本没有通过质量检查。由于每个版本都是基于之前的版本开发的，所以错误版本之后的所有版本都是不好的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出第一个错误的版本，导致下面所有的错误。

你可以通过 bool isBadVersion(version) 的接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。您应该尽量减少对 API 的调用次数。

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int mid,left = 1,right = n;
        while(left < right){
            mid = left + ((right-left)>>1);
            isBadVersion(mid) ? (right = mid) : (left = mid + 1);
        }
        return right;
    }
};

这个时间卡的很严，最开始二分也没过去，后来把中点的求法改了以后才过的。

动态规划

爬楼梯

你正在爬楼梯。需要 n 步你才能到达顶部。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方式可以爬到楼顶呢？

注意：给定 n 将是一个正整数。

示例 1：

输入： 2
输出： 2
说明： 有两种方法可以爬到顶端。

1.  1 步 + 1 步
2.  2 步

示例 2：

输入： 3
输出： 3
说明： 有三种方法可以爬到顶端。

1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        int a = 1;
        int b = 2;
        int c = a + b;
        while(n>3){
            a = b;
            b = c;
            c = a+b;
            n--;
        }
        return c;
    }
};

明天继续….