很早就想在上面刷题,但是后来路偏了,跑去弄公众号了。现在借着考研来刷题,顺便提前温习一下数据结构的一些算法和C++的用法。

20200402

给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 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) {
        int len = nums.size();
        for(int i=0;i < len - 1;i++)
        {
            for(int j = i+1;j < len;j++)
            {
                if(nums[i]+nums[j]==target)
                    return {i,j};
            }
        }
        return {};
    }
};


20200404

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

雨水图

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        int size = height.size();
        for(int i = 1;i < size - 1;i++)
        {
            int max_left = 0,max_right = 0;
            for(int j = i;j >= 0;j--)
            {
                max_left = max(max_left,height[j]);
            }
            for(int m = i;m < size;m++)
            {
                max_right = max(max_right,height[m]);
            }
            sum+=min(max_left,max_right)-height[i];
        }
        return sum;
    }
};


20200405

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例:

输入: 123
输出: 321

输入: -123
输出: -321

输入: 120
输出: 21

class Solution {
public:
    int reverse(long int x) {
        int y = 0;
        int i = 1;
        if(x < 0)
        {
            i = -1;
        }
        int m = abs(x);
        if(m >= 10)
        {
            while(m >= 10)
            {
                int b = 0;
                b = m%10;
                m = (m-b)/10;
                y = y*10 + b;
            }
            y = y*10+m;
        }
        else
        {
            y=m;
        }
        return i*y;
    }
};


20200407

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

class Solution {
public:
    bool isPalindrome(int x) {
        int m = x;
        long long n = 0;
        if(x < 0)
            return false;
        else
            while(m!=0)
            {
                n = m%10 + n*10;
                m = (m-m%10)/10;
            }
            if(n == x)
                return true;
            else
                return false;
    }
};


20200412

罗马数字包含以下七种字符: IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做II ,即为两个并列的 1。12 写做XII ,即为X + II 。 27 写做XXVII, 即为XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做IIII,而是IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:
输入: "III"
输出: 3

示例 2:
输入: "IV"
输出: 4

示例 3:
输入: "IX"
输出: 9

示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

class Solution {
public:
    int value = 0;
    int num(int a)
    {
        switch(a)
        {
            case 'I':value=1;break;
            case 'V':value=5;break;
            case 'X':value=10;break;
            case 'L':value=50;break;
            case 'C':value=100;break;
            case 'D':value=500;break;
            case 'M':value=1000;break;
            default :break;
        }
        return value;
    }
    int romanToInt(string s) {

        int add = 0,sub = 0;
        for(int i = 0;i < s.size()-1;++i)
        {
            if(num(s[i]) < num(s[i+1]))
                sub-=num(s[i]);
            else
                add+=num(s[i]);
        }
        add+=num(s.back());
        return add+sub;
    }
};


20200413

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0) return "";
        for(int i=0;i<strs[0].size();i++)
            for(int j=1;j<strs.size();j++)
                if(strs[0][i] != strs[j][i])               
                    return strs[0].substr(0,i);
        return strs[0];
    }
};


20200418

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i=0;i < s.size();i++)
        {
            if(st.empty()&&(s[i] == ')' || s[i] == '}' || s[i] == ']'))
                return false;
            else if(s[i] == ')' || s[i] == '}' || s[i] == ']')
            {
                if(s[i]-st.top()==1||s[i]-st.top() == 2) //ASCII码相差1或2
                    st.pop();
                else
                    return false;
            }
            else
                st.push(s[i]);
        }
        return st.empty();
    }
};

20200420

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;
        if(l1->val <= l2->val)
        {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
};


给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

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

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = 0;
        if(!nums.size()) return 0;
        for(int i = 0;i < nums.size();i++)
        {
            if(nums[i] != val)
            {
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
};


20200421

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        int i = 0,j=0;
        while(haystack[i] != '\0' && needle[j] != '\0')
        {
            if(haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else
            {
                i = i-j+1;
                j=0;
            }
        }
        if(needle[j]=='\0')
            return i-j;
        return -1;
    }
};

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

示例 3:
输入: [1,3,5,6], 7
输出: 4

示例 4:
输入: [1,3,5,6], 0
输出: 0

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int i=0;
        for(i ;i < nums.size();i++)
        {
            if(nums[i] >= target)
                return i;
        }
        return i;
    }
};

「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下:

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
    1 被读作  "one 1"  ("一个一") , 即 11。
  6. 被读作 "two 1s" ("两个一"), 即 21。
  7. 被读作 "one 2",  "one 1" ("一个二" ,  "一个一") , 即 1211。

给定一个正整数 n(1 ≤ n ≤ 30),输出外观数列的第 n 项。

注意:整数序列中的每一项将表示为一个字符串。

示例 1:
输入: 1
输出: "1"
解释:这是一个基本样例。

示例 2:
输入: 4
输出: "1211"
解释:当 n = 3 时,序列是 "21",其中我们有 "2" 和 "1" 两组,"2" 可以读作 "12",也就是出现频次 = 1 而 值 = 2;类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起,也就是 "1211"。

class Solution {
public:
    string countAndSay(int n) {
        string result = "1";
        for(int i=1;i<n;i++)
        {
            result = add(result);
        }
        return result;
    }

    string add(string s)
    {
        int num = 1;
        string str1 = "\0";
        for(int i = 0;i<s.size();i++)
        {
            if(s[i]==s[i+1])
                num++;
            else
            {
                str1+= num+'0';
                str1+= s[i];
                num=1;
            }
        }
        return str1;
    }
};


20200422

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max = INT_MIN;
        for(int i = 0;i<nums.size();i++)
        {
            int sum = 0;
            for(int j = i;j<nums.size();j++)
            {
                sum+=nums[j];
                if(sum > max)
                    max = sum;
            }
        }
        return max;
    }
};

给定一个仅包含大小写字母和空格 ' ' 的字符串 s,返回其最后一个单词的长度。如果字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词,请返回 0 。

说明:一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

示例:
输入: "Hello World"
输出: 5

class Solution {
public:
    int lengthOfLastWord(string s) {
        int sum = 0;
        int len = s.size();
        for(int i = len-1;i>=0;i--)
        {
            if(s[i]!=' ')
                sum++;
            else
                if(sum!=0)
                    return sum;
        }
        return sum;
    }
};

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i = digits.size()-1;i>=0;i--)
        {
            digits[i]++;
            if(digits[i]!=10)
                return digits;
            else
                digits[i]=0;
        }
        digits.insert(digits.begin(),1);
        return digits;
    }
};


20200423

给你两个二进制字符串,返回它们的和(用二进制表示)。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:
输入: a = "11", b = "1"
输出: "100"

示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

class Solution {
public:
    string addBinary(string a, string b) {
        int lena = a.size();
        int lenb = b.size();
        while(lena < lenb)
        {
            a = '0'+a;
            lena++;
        }
        while(lenb< lena)
        {
            b = '0'+b;
            lenb++;
        }
        for(int i = lena-1;i>0;i--)
        {
            a[i] = a[i] - '0' + b[i];
            if(a[i] >= '2')
            {
                a[i] = (a[i] - '0')%2 + '0';
                a[i-1]=a[i-1]+1;
            }
        }
        a[0] = a[0] - '0' + b[0];
        if(a[0] >= '2')
        {
            a[0] = (a[0] - '0')%2 + '0';
            a = '1'+a;
        }
        return a;
    }
};


20200424

假设你正在爬楼梯。需要 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) {
       long long sum[] = {1,1,0};
       for(int i = 1;i <= n;i++)
       {
            sum[2] = sum[1] + sum[0];
            sum[0] = sum[1];
            sum[1] = sum[2];
       }
       return sum[0];
    }

    };

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:
输入: 1->1->2
输出: 1->2

示例 2:
输入: 1->1->2->3->3
输出: 1->2->3

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* i = head;
        ListNode* j = head;
        if(head==NULL) return 0;
        while(j!=NULL)
        {
            if(i->val!=j->val)
            {
                i->next=j;
                i=i->next;
            }
            j = j->next;
        }
        i->next = NULL;
        return head;
    }
};

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
 
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

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


20200425

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:
输入:

       1         1
      / \       / \
     2   3     2   3

    [1,2,3],   [1,2,3]

输出: true

示例 2:
输入:

       1          1
      /           \
     2             2

    [1,2],     [1,null,2]

输出: false

示例 3:
输入:

       1         1
      / \       / \
     2   1     1   2

    [1,2,1],   [1,1,2]

输出: false

/**
 * 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 isSameTree(TreeNode* p, TreeNode* q) {
        if(!p&&!q) return true;
        if(!p || !q) return false;
        return (p->val == q->val)&&(isSameTree(p->left,q->left))&&(isSameTree(p->right,q->right));
    }
};

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [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

 

/**
 * 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 isSymmetric(TreeNode* root) {
        if(!root) return true;
        return (down(root->left,root->right));
    }
private:
    bool down(TreeNode* root1,TreeNode* root2)
    {
        if(!root1 && !root2) return true;
        if(!root1 || !root2) return false;
        if(root1->val != root2->val) return false;
        return (down(root1->left,root2->right)&&down(root1->right,root2->left));
    }
};

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

/**
 * 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:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

20200426

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

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

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为:

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

/**
 * 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>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        getres(root,0,res);
        reverse(res.begin(),res.end());
        return res;
    }
    void getres(TreeNode* node,int level,vector<vector<int>>& res)
    {
        if(!node) return;
        if(res.size()==level) res.push_back({});
        res[level].push_back(node->val);
        if(node->left) getres(node->left,level+1,res);
        if(node->right) getres(node->right,level+1,res);
    }
};

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

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

示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5


/**
 * 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:
    TreeNode* sortedArrayToBST(vector<int>& nums) {

        if(nums.size()==0) return NULL;
        if(nums.size()==1) return new TreeNode(nums[0]);

        int mid = (nums.size())/2;
        TreeNode* node = new TreeNode(nums[mid]);

        vector<int> nums_left(nums.begin(),nums.begin()+mid);
        node->left=sortedArrayToBST(nums_left);

        vector<int> nums_right(nums.begin()+mid+1,nums.end());
        node->right=sortedArrayToBST(nums_right);

        return node;
    }
};

20200429

给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

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

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

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

返回 false 。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int d = abs(deepth(root->left)-deepth(root->right));
        return (d<=1)&&isBalanced(root->left)&&isBalanced(root->right);
    }
    int deepth(TreeNode* root)
    {
        if(!root) return 0;
        return max(deepth(root->left),deepth(root->right))+1;
    }
};

20200430

给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度2.

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int level=1;
        if(!root->left && !root->right) return level;
        if(!root->right) return minDepth(root->left)+level;
        if(!root->left) return minDepth(root->right)+level;
        return min(minDepth(root->left),minDepth(root->right))+level;
    }
};

Last modification:April 30, 2020
如果觉得我的文章对你有用,请随意赞赏