int-summary

概述

本文下载地址:https://github.com/daiwk/int-collections/blob/master/int-summary.pdf

主要是leetcode相关的题

参考1:【medium常见题】[https://leetcode-cn.com/leetbook/detail/top-interview-questions-medium/](https://leetcode-cn.com/leetbook/detail/ top-interview-questions-medium/)

参考2:【top100】https://leetcode.cn/problem-list/2cktkvj/

参考3:【topint】https://leetcode.cn/problem-list/2ckc81c/

数组和字符串

罗马数字转整数

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符          数值
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.

解答:

  • 第一,如果当前数字是最后一个数字,或者之后的数字比它小的话,则加上当前数字

  • 第二,其他情况则减去这个数字(例如,IV,看到I的时候就是减去I,然后到V就是加V; XL,看到X的时候就是-X,然后到L就是加L)

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> x_map;
        x_map.insert(std::make_pair('I', 1));
        x_map.insert(std::make_pair('V', 5));
        x_map.insert(std::make_pair('X', 10));
        x_map.insert(std::make_pair('L', 50));
        x_map.insert(std::make_pair('C', 100));
        x_map.insert(std::make_pair('D', 500));
        x_map.insert(std::make_pair('M', 1000));
        int res = 0;
        for (int i = 0; i < s.size(); ++i) {
            cout << i << s[i] << endl;
            int val = x_map[s[i]];
            if (i == s.size() - 1 || x_map[s[i+1]] <= x_map[s[i]]) {
                res += val;
            } else {
                res -= val;
            }
        }
        return res;
    }
};

【top100】两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

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

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

解法:

用一个map,key是元素值,value是idx 看新来的这个元素的目标值(tgt - nums[i])在不在map里,在的话把它的value拿出来就行了。。

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

【top100】三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        int size = nums.size();
        vector<vector<int> >res;            // 保存结果(所有不重复的三元组)
        if (size < 3) {
            return res;          // 特判
        }
        std::sort(nums.begin(), nums.end());// 排序(默认递增)
        for (int i = 0; i < size; i++)      // 固定第一个数,转化为求两数之和
        {
            if (nums[i] > 0) { // !!!容易漏掉
                return res; // 第一个数大于 0,后面都是递增正数,不可能相加为零了
            }
            // 去重:如果此数已经选取过,跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 双指针在nums[i]后面的区间中寻找和为0-nums[i]的另外两个数
            int left = i + 1;
            int right = size - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > -nums[i]) {
                    right--;    // 两数之和太大,右指针左移
                } else if (nums[left] + nums[right] < -nums[i]) {
                    left++;     // 两数之和太小,左指针右移
                } else {
                    // 找到一个和为零的三元组,添加到结果中,左右指针内缩,继续寻找
                    vector<int> tmp {nums[i], nums[left], nums[right]};
                    res.push_back(tmp);
                    left++;
                    right--;
                    // 去重:第二个数和第三个数也不重复选取 !!!容易漏掉
                    // 例如:[-4,1,1,1,2,3,3,3], i=0, left=1, right=5
                    while (left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                }
            }
        }
        return res;
    }

矩阵置零

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

    void setZeroes(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        // 用两个辅助数组,存这行和这列是否要变成0,
        // 然后再遍历原矩阵,如果二者有一个要变0,那就变成0
        vector<bool> rows(row, false);
        vector<bool> cols(col, false);
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }    
            }
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (rows[i] || cols[j]) {
                    matrix[i][j] = 0;
                }    
            }
        }
    }

【top100】字母异位词分组

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。

其实就是个倒排

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string> > xmap;
        for (auto& it: strs) {
            string xit = it;
            // 对string进行sort,搞成一个词,扔进map
            sort(xit.begin(), xit.end());
            xmap[xit].emplace_back(it);
        }
        vector<vector<string>> res;
        for (auto& it: xmap) {
            res.emplace_back(it.second);
        }
        return res;
    }

【top100】无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

双指针

   int lengthOfLongestSubstring(string s) {
        set<char> set_char;
        int res = 0;
        // 双指针,两个指针都从头开始
        for (int i = 0, j = 0; i < s.size() && j < s.size(); ) {
            if (set_char.find(s[j]) != set_char.end()) {
                //找到重复了,那就把起始的扔了
                set_char.erase(s[i]);
                ++i;
            } else {
                if (j - i + 1 > res) {
                    res = j - i + 1;
                }
                set_char.insert(s[j]);
                //没重复的,右指针继续往前找
                ++j;
            }
        }
        
        return res;
    }

【top100】寻找两个正序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 nums1 和 nums2 不同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

解答:

方法1(复杂度O(m+n)):

先归并两个数组,再取中点,归并的复杂度是O(m+n),参考第88题https://leetcode-cn.com/problems/merge-sorted-array/description/

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> tmp;
        int m = nums1.size();
        int n = nums2.size();
        int total_size = n + m;
        tmp.resize(total_size);
        // 倒着来
        int i = m - 1;
        int j = n - 1;
        // 如果有重复的,也要复制两遍
        while (j >= 0) {
            if (i < 0) {
                // 如果i数组遍历完了,要把j数据剩下的全部拷过来,记住是<j+1
                for(int k = 0; k < j + 1; ++k) {
                    tmp[k] = nums2[k];
                }
                break;
            }
            if (nums2[j] > nums1[i]) {
                // 留大的下来,留谁的就谁的指针--
                // 注意是i + j + 1
                tmp[i + j + 1] = nums2[j];
                j--;
            } else {
                tmp[i + j + 1] = nums1[i];
                i--;
            }
        }
        if (j < 0) {
            // 同理,j遍历完了就把i剩下的搞过来
            for(int k = 0; k < i + 1; ++k) {
                tmp[k] = nums1[k];
            }
        }
        // 以上是归并两个数组的方法
        if (total_size % 2 != 0) {
            return tmp[total_size / 2];
        } else {
            return (tmp[total_size / 2 - 1] + tmp[total_size / 2]) *1.0 / 2;
        }
    }

方法2:二分查找

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/

最长公共前缀

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

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

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

注意这里说的是前缀,不是子序列,所以两个str都从0开始,同一个指针一起移动就行。。可以只遍历短的长度

另外,随着遍历的字符串变多,公共前缀是会变短的,变成0就可以return,如果完了还不是0,那就是要的了

另外,不用str[i]和str[i+1]比较再和prefix,直接str[i]和prefix比较就行,这样循环简单点

    string longestCommonPrefix(vector<string>& strs) {
        string comm_prefix = strs[0];
        for (int i = 0; i < strs.size(); ++i) {
            lcp_sub(strs[i], comm_prefix);
            if (comm_prefix == "") {
                return comm_prefix;
            }
        }
        return comm_prefix;
    }
    void lcp_sub(const string &a, string& b) {
        int len = min(a.length(), b.length());
        int i = 0;
        while(i < len) {
            if (a[i] != b[i]) {
                break;
            }
            ++i;
        }
        if (a[i] != b[i]) {
            b = b.substr(0, i);
        } else {
            b = b.substr(0, i + 1);
        }
    }

有点绕,还是抄答案吧:

    string longestCommonPrefix(vector<string>& strs) {
        string comm_prefix = strs[0];
        for (int i = 0; i < strs.size(); ++i) {
            lcp_sub(strs[i], comm_prefix);
            if (comm_prefix == "") {
                return comm_prefix;
            }
        }
        return comm_prefix;
    }
    void lcp_sub(const string &a, string& b) {
        int len = min(a.length(), b.length());
        int i = 0;
        // while一起判断了,就不用再对i i+1处理了。。
        while (i < len && a[i] == b[i]) {
            ++i;
        }
        b = b.substr(0, i);
    }

存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。

    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> xset;
        for(auto& i: nums) {
            if (xset.count(i)) {
                return true;
            }
            xset.emplace(i);
        }
        return false;
    }

整数反转

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

示例:

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:

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

解答

写一个valid函数,记得参数变成long,然后去看这个long是不是在int32的范围里

class Solution {
public:
    bool valid(long x) { // 注意,这里要是long
        if (x > 0) {
            if (x >= pow(2, 31) -1)
                return false;
        }
        if (x < 0) {
            if (x <= -pow(2, 31)) {
                return false;
            }
        }
        return true;
    }

    int reverse(int x) {
        long tmp = 0;
        // 开始判断一下范围
        if (!valid(x)) {
            return 0;
        }
        bool flag = true;
        // 统一变成正数,处理完如果原来是负的再变回去
        if (x < 0) {
            x = -x;
            flag = false;
        }
        while (x != 0) {
            tmp *= 10; // tmp向左移一位
            tmp += x % 10; // 取出x的最低位
            x /= 10; // x往右移一位
        }
        if (flag == false) {
            tmp = -tmp;
        }
        // 结束再判断一下范围
        if (valid(tmp)) {
            return tmp;
        }
        return 0; 
};

【top100】只出现一次的数字

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

异或:

  • 任何数和 0 做异或运算,结果仍然是原来的数

  • 任何数和其自身做异或运算,结果是 0

  • 异或运算满足交换律和结合律

所以

a^b^a=a^a^b=(a^a)^b=0^b=b

所以把所有数异或一遍就是那个只出现一次的数了。。

    int singleNumber(vector<int>& nums) {
        int res = 0; // 初始化为0
        for (auto& i: nums) {
            res ^= i;
        }
        return res;
    }

【top100】有效的括号

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

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。

  • 左括号必须以正确的顺序闭合。

  • 注意空字符串可被认为是有效字符串。

示例 1:

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

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

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

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

输入: "{[]}"
输出: true

解答:

注意一定要先判断st.size()>0再取top,不然会出错

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char, char> mp;
        // 先用map存一下左右括号的映射关系,
        // 因为是栈,遇到右括号才想着pop,所以key是右括号!!
        mp.insert(std::make_pair('}', '{'));
        mp.insert(std::make_pair(']', '['));
        mp.insert(std::make_pair(')', '('));
        for (int i = 0; i < s.size(); i++) {
            if (mp.find(s[i]) != mp.end() && 
                st.size() > 0 && 
                mp[s[i]] == st.top()) {
                st.pop();
            } else {
                st.push(s[i]);
            }
        }
        if (st.size() == 0) return true;
        return false;
    }
};

基础的括号匹配

https://www.luogu.com.cn/problem/P1739

假设一个表达式有英文字母(小写)、运算符(+,—,*,/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回“YES”;否则返回“NO”。表达式长度小于255,左圆括号少于20个。

输入格式
一行:表达式

输出格式
一行:“YES” 或“NO”

解答:

栈的思想,可以不用栈,用一个变量top,遇到左括号++,右括号--,看最后是不是0

注意:

如果先出现了右括号,前面没有左括号的时候(top=0时出现了右括号),直接是NO

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
char c;
int top = 0;
int main()
{
    for(; ; )
    {
        cin >> c;
        if (c == '@') break;
        if (c == '(') top++;
        else if( c==')' && top > 0) {
            top--;
        } else if(c==')') {
            cout << "NO";
            return 0;
        }
    }
    if(top == 0) {
        cout<<"YES";
    } else {
        cout<<"NO";
    }
    return 0;
}

回文数

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

示例 1:

输入: 121
输出: true
示例 2:

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

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

解答

为了避免数字反转可能导致的溢出问题,为什么不考虑只反转 数字的一半?毕竟,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。

例如,输入 1221,我们可以将数字“1221”的后半部分从“21”反转为“12”,并将其与前半部分“12”进行比较,因为二者相同,我们得知数字 1221 是回文。

  • 特判

所有负数都不可能是回文,例如:-123 不是回文,因为 - 不等于 3

!!!!尾数能被10整除,即尾数是0的也不行,因为首位不是0

  • 反转

对于数字 1221,如果执行 1221 % 10,我们将得到最后一位数字 1,要得到倒数第二位数字,我们可以先通过除以 10 把最后一位数字从 1221 中移除,1221 / 10 = 122,再求出上一步结果除以10的余数,122 % 10 = 2,就可以得到倒数第二位数字。如果我们把最后一位数字乘以10,再加上倒数第二位数字,1 * 10 + 2 = 12,就得到了我们想要的反转后的数字。 如果继续这个过程,我们将得到更多位数的反转数字。

所以,每次把上一次的数字*10加上这一次的最后一位数字,然后x/=10把这次的尾数扔掉

现在的问题是,我们如何知道反转数字的位数已经达到原始数字位数的一半?

  • 终止

我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当除完的原始数字不大于反转后的数字时,就意味着我们已经处理了一半位数的数字。

例如,原数字是4123,反转到321>41的时候,就到一半了;如果原数字是412,反转到21>4的时候也到一半了。也就是反转的位数比剩下的多,肯定到一半了。或者,原数字是1234,反转到34>12

举个是回文数的例子,原数字是3223,32==32,break了;原数字121,12>1,break掉

当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。

例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123

由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。所以对于奇数位,就是判断x==revertedNumber/10

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0 || (x % 10 == 0 && x != 0)) { //边界!!
            return false;
        }
        int revertedNumber = 0;
        while(x > revertedNumber) { // 大于
            revertedNumber = revertedNumber * 10 + x % 10; // 这么判断 
            x /= 10;
        }
        return (x == revertedNumber || x == revertedNumber / 10);
    }
};

【top100】盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

双指针!!

对于i,j两个点,能接的水量是min(num[i],num[j]) * (j - i)

这个时候应该移动的是num[i]和num[j]中较小的那个,因为j-i肯定会变小,

而想要变大,只能min(num[i],num[j])变大,所以要把小的移一下试试,如果小的在左边那就右移,否则同理

    int maxArea(vector<int>& height) {
        // 对于i,j两个点,能接的水量是min(num[i],num[j]) * (j - i)
        // 这个时候应该移动的是num[i]和num[j]中较小的那个,因为j-i肯定会变小,
        // 而想要变大,只能min(num[i],num[j])变大,所以要把小的移一下试试,如果小的在左边那就右移,否则同理
        int max_res = 0;
        int i = 0, j = height.size() - 1;
        while (i < j) {
            int cur_water = min(height[i], height[j]) * (j - i);
            max_res = max(max_res, cur_water);
            if (height[i] >= height[j]) {
                --j;
            } else {
                ++i;
            }
        }
        return max_res;
    }

最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

解法

「最接近」即为差值的绝对值最小

类似三数之和,双指针,固定第一个数,希望剩下b+c最接近target

    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        if (n < 3) {
            return -1;
        }
        sort(nums.begin(), nums.end());
        int dist = INT_MAX;
        int res = INT_MIN;
        for (int i = 0; i < n; ++i) {
            int left = i + 1;
            int right = n - 1;
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    ++left;
                    // 注意,这个和三数之和那题的位置不一样
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                } else if(sum > target) {
                    --right;
                    // 注意,这个和三数之和那题的位置不一样
                    while (left < right && nums[right] == nums[right + 1]) {
                        --right;
                    }
                } else {
                    return sum;
                }
                if (dist > abs(sum - target)) {
                    res = sum;
                    dist = abs(sum - target);
                }
            }
        }
        return res;
    }

Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

P   A   H   N
A P L S I I G
Y   I   R

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数:

示例 2:
输入:s = "PAYPALISHIRING", numRows = 4
输出:"PINALSIGYAHRPI"
解释:
P     I    N
A   L S  I G
Y A   H R
P     I

画个图,直接找出新字符串每一位对应原来的下标

会向下填写 r 个字符,然后向右上继续填写 r−2 个字符(斜线的r扣掉最后一行,和新的第一行的各一个字符),所以变换周期是t=2r-2。

所以第一行的下标都是2r-2的倍数即0+kt,而最后一行就应该是r-1 + kt

而中间的第i行,除了k个数外,每一轮间还有一个数,那个数是(k + 1)t-i

    string convert(string s, int numRows) {
        
        int t = 2 * numRows - 2;
        int i = 0;
        if (t == 0) {
            return s;
        }
        int round = s.length() / t;
        string res;
        while (i < numRows) {
            int k = 0;
            int idx = 0;
            if (i == 0) {
                while (k <= round) {
                    idx = k * t;
                    if (idx < s.length()) {
                        res.push_back(s[idx]);
                    }
                    k++;
                }
            } else if (i < numRows -1) {
                k = 0;
                while (k <= round) {
                   idx = i + k * t;
                   if (idx < s.length()) {
                        res.push_back(s[idx]);
                   }
                   idx = (k + 1) * t - i;
                   if (idx > 0 && idx < s.length()) {
                        res.push_back(s[idx]); 
                   }
                   ++k;
                }
            } else {
                k = 0;
                while (k <= round) {
                    idx = numRows - 1 + k * t;
                    if (idx < s.length()) {
                        res.push_back(s[idx]);
                    }
                    k++;
                }
            }
            ++i;
        }
        return res;
    }

标准答案简单很多:

其实就是。。而中间的第i行,除了k个数外,每一轮间还有一个数,那个数是(k + 1)t-i = kt + t-i

这样,就都有kt了

所以就是每个周期塞两个数(不越界的情况下),

第一个数是每个周期的起始下标kt + i

第二个数是kt+t-i

限制一下最后一行和第一行只插入一个数,不然会出问题!!

    string convert(string s, int numRows) {
        int t = 2 * numRows - 2;
        int i = 0;
        if (t == 0) {
            return s;
        }
        int round = s.length() / t;
        string res;
        while (i < numRows) {
            for (int j = 0; j + i < s.length(); j += t) {
                // 循环k轮,枚举每轮的起始下标
                res.push_back(s[j + i]); // 当前周期第一个字符
                // 注意,这里要限制0<i < numRows -1,因为第一行和最后一行只加一个数!!!!!
                if (0 < i && i < numRows - 1 && j + t - i < s.length()) {
                    res.push_back(s[j + t - i]);
                }
            }
            ++i;
        }
        return res;
    }

删除有序数组中的重复项

给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

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

解法

双指针,一快一慢,如果遇到不相等的,那就把快的值复制到慢的下一位,两个指针继续移动。

    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.size(); j++) {
            if (nums[j] != nums[i]) {
                // 不相等,且j比i快,那就说明ij中间可能是一串重复的数,
                // 就把num[j]赋值给num[i+1],然后两个指针都往后移
                nums[i + 1] = nums[j];
                ++i;
            }
        }
        return i + 1;
    }

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

参考https://leetcode.cn/problems/spiral-matrix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-3/

  • 首先设定上下左右边界

  • 其次向右移动到最右,此时第一行因为已经使用过了,可以将其从图中删去,体现在代码中就是重新定义上边界

  • 判断若重新定义后,上下边界交错,表明螺旋矩阵遍历结束,跳出循环,返回答案

  • 若上下边界不交错,则遍历还未结束,接着向下向左向上移动,操作过程与第一,二步同理

  • 不断循环以上步骤,直到某两条边界交错,跳出循环,返回答案

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // 首先设定上下左右边界
        // 其次向右移动到最右,此时第一行因为已经使用过了,可以将其从图中删去,体现在代码中就是重新定义上边界
        // 判断若重新定义后,上下边界交错,表明螺旋矩阵遍历结束,跳出循环,返回答案
        // 若上下边界不交错,则遍历还未结束,接着向下向左向上移动,操作过程与第一,二步同理
        // 不断循环以上步骤,直到某两条边界交错,跳出循环,返回答案
        vector<int> res;
        if (matrix.empty()) {
            return res;
        }
        int up = 0;
        int right = matrix[0].size() - 1;
        int down = matrix.size() - 1;
        int left = 0;
        while(true) {
            for (int i = left; i <= right; ++i) {
                res.push_back(matrix[up][i]);
            }
            if (++up > down) break;
            for (int i = up; i <= down; ++i) {
                res.push_back(matrix[i][right]);
            }
            if (--right < left) break;
            for (int i = right; i >= left; --i) {
                res.push_back(matrix[down][i]);
            }
            if (--down < up) break;
            for (int i = down; i >= up; --i) {
                res.push_back(matrix[i][left]);
            }
            if (++left > right) break;
        }
        return res;
    }

判定字符是否唯一

实现一个算法,确定一个字符串 s 的所有字符是否全都不同。

示例 1:
输入: s = "leetcode"
输出: false 

位运算

其实就是位图,假设当前是b,那1左移'b'-'a'位,和mark&一下,如果是0,说明这一位还没有出现过,那就和mark|一下得到新的mark,反之,不是0的话,就说明这一位之前出现过了

    bool isUnique(string astr) {
        int mark = 0;
        for (auto& i: astr) {
            int bit = i - 'a';
            int res = 1<<bit;
            // 这里要加括号!!因为!=比&的优先级要高。。
            //或者也可以直接 if(res&mark)
            if ((res & mark) != 0) {
                return false;
            }
            mark |= res;
        }
        return true;
    }

第一个错误的版本

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

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

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

二分

    int firstBadVersion(int n) {
        int left = 0, right = n - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid + 1)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
       return left + 1;
    }

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

就是模拟竖式计算。。

    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        string res = "0";
        int m = num1.size(), n = num2.size();
        //遍历num2
        for (int i = n - 1; i >= 0; --i) {
            string cur; // 先都扔原始数字进去,后面一起+'0'
            for (int j = n - 1; j > i; j--) {
                cur.push_back(0); 
            }
            int y = num2.at(i) - '0'; 
            int add = 0; // 进位
            for (int j = m - 1; j >= 0; --j) {
                // 遍历num1
                int x = num1[j] - '0';
                int product = x * y + add;
                cur.push_back(product % 10);
                add = product / 10; //进位
            }
            while (add != 0) {
                // 因为最终可以进好多位,要逐位产出
                cur.push_back(add % 10);
                add /= 10;
            }
            reverse(cur.begin(), cur.end());
            for (auto& i: cur) {
                i += '0';
            }
            res = add_string(res, cur);
        }
        return res;
    }
    string add_string(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1, add = 0;
        string res;
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0? num1.at(i) - '0': 0; //防越界
            int y = j >= 0? num2.at(j) - '0': 0; //防越界
            int result = x + y + add;
            res.push_back(result % 10);
            add = result / 10;
            --i;
            --j;
        }
        reverse(res.begin(), res.end());
        for (auto& i: res) {
            i += '0';
        }
        return res;
    }

【top100】最长连续序列

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

其实只需要每次在哈希表中检查是否存在x−1即可。如果x-1存在,说明当前数x不是连续序列的起始数字,我们跳过这个数。

    int longestConsecutive(vector<int>& vec) {
        unordered_set<int> xset;
        for (auto& i: vec) {
            xset.emplace(i);
        }
        int max_len = 0;
        vector<int> res_vec;
        for (auto& item: xset) {
            vector<int> tmp_vec;
            int tmp_len = 0;
            int i = 0;
            if (!xset.count(item - 1)) {
                while (xset.count(item + i)) {
                    // cout << "aa2 " << i << " " << item-i << endl;
                    tmp_vec.emplace_back(item + i);
                    i++;
                }
            }
            tmp_len += i;
            if (tmp_len > max_len) {
                res_vec.swap(tmp_vec);
            }
            max_len = max(max_len, tmp_len);
        }
        return max_len;
    }

类似的byte面试题

返回一个序列中最长的连续数组

题目描述 Input: ​ [0, 78, 1, 2, -1, 5, 6, 7, 7]​

Output: ​ [-1, 0, 1, 2] ​

自己的解法,能过68/71,超时。。其实两个while可以去掉一个,这样也只能过69/71

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

pair<vector<int>, int> get_max_len(const vector<int>& vec) {
    unordered_set<int> xset;
    for (auto& i: vec) {
        xset.emplace(i);
    }
    int max_len = 0;
    vector<int> res_vec;
    for (auto& item: xset) {
        vector<int> tmp_vec;
        int tmp_len = 0;
        int i = 0;
        // 可以只留一个while
        while (xset.count(item - i)) {
            // cout << "aa1 " << i << " " << item-i << endl;
            tmp_vec.emplace_back(item - i);
            i++;
        }
        tmp_len += i;
        
        i = 1;
        while (xset.count(item + i)) {
            // cout << "aa2 " << i << " " << item-i << endl;
            tmp_vec.emplace_back(item + i);
            i++;
        }
        tmp_len += i -1;
        if (tmp_len > max_len) {
            res_vec.swap(tmp_vec);
        }
        max_len = max(max_len, tmp_len);
    }
    return {res_vec, max_len};
}

int main() {
    vector<int> vec {0, 78, 1,2,-1,5,6,7,7};
    auto res = get_max_len(vec);
    cout << res.second << endl;
    cout << "=====" << endl;
    for (const auto&i: res.first) {
        cout << i << endl;
    }

    return 0;
}

优化后的解法:

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

pair<vector<int>, int> get_max_len(const vector<int>& vec) {
    unordered_set<int> xset;
    for (auto& i: vec) {
        xset.emplace(i);
    }
    int max_len = 0;
    vector<int> res_vec;
    for (auto& item: xset) {
        vector<int> tmp_vec;
        int tmp_len = 0;
        int i = 0;
//        // 可以只留一个while
//        while (xset.count(item - i)) {
//            // cout << "aa1 " << i << " " << item-i << endl;
//            tmp_vec.emplace_back(item - i);
//            i++;
//        }
//        tmp_len += i;

//        i = 1;
        if (!xset.count(item - 1)) {
            while (xset.count(item + i)) {
                // cout << "aa2 " << i << " " << item-i << endl;
                tmp_vec.emplace_back(item + i);
                i++;
            }
        }
//        tmp_len += i -1;
        tmp_len += i;
        if (tmp_len > max_len) {
            res_vec.swap(tmp_vec);
        }
        max_len = max(max_len, tmp_len);
    }
    return {res_vec, max_len};
}

int main() {
    vector<int> vec {0, 78, 1,2,-1,5,6,7,7};
    auto res = get_max_len(vec);
    cout << res.second << endl;
    cout << "=====" << endl;
    for (const auto&i: res.first) {
        cout << i << endl;
    }

    return 0;
}

【top100】最长有效括号

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 2:

输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"

解法

可以是dp也可以是栈

栈的解法就是栈里放的是int,而不是左右括号

始终保持栈底元素为当前已经遍历过的元素中最后一个没有被匹配的右括号的下标

  • 遇到左括号,把下标扔进栈里

  • 遇到右括号

    • 弹出栈顶,表示有左括号和它匹配上了,弹出之后

      • 如果栈为空,说明当前右括号没人和他匹配,就把它的下标扔进去,这就满足了最后一个没有被匹配的右括号的下标

      • 如果栈不空,当前右括号下标减掉栈顶就是以这个右括号结尾的最长有效括号长度。。

如果一开始栈为空,第一个字符为左括号的时候我们会将其放入栈中,这样就不满足提及的「最后一个没有被匹配的右括号的下标」,为了保持统一,我们在一开始的时候往栈中放入一个值为 -1 的元素

如上图,先-1入栈,然后遇到(,就扔一个0进去,然后i=1的时候,栈顶的0其实和它是匹配的,就扔掉,这个时候1-(-1)就是2了,其实就是扔掉的那对括号的长度

    int longestValidParentheses(string s) {
        int max_res = 0;
        stack<int> stk;
        stk.push(-1);// 如上所述,为了保证栈底一直是xxx的右括号
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                stk.push(i);
            } else if (s[i] == ')') {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    max_res = max(max_res, i - stk.top());
                }
            }
        }
        return max_res;
    }

【top100】滑动窗口最大值

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值