精华内容
下载资源
问答
  • 文章目录前言两数之和旋转图像有效的数独反转字符串 前言 这篇排不了那么多题了,有点麻烦。 两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们...


    前言

    这篇排不了那么多题了,有点麻烦。

    两数之和

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

    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

    你可以按任意顺序返回答案。

    示例 1:

    输入:nums = [2,7,11,15], target = 9
    输出:[0,1]
    解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2jrse/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    思路:不得不说,哈希表是真的挺好用的。

    vector<int> twoSum(vector<int>& nums, int target) {
            map<int, int> hashmap;
            for (int i = 0; i < nums.size(); ++i)
                if (hashmap.count(target - nums[i]))
                    return {hashmap[target - nums[i]], i};
                else
                    hashmap[nums[i]] = i;
            return {};
        }
    

    旋转图像

    给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

    你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

    在这里插入图片描述

    输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出:[[7,4,1],[8,5,2],[9,6,3]]
    

    (这题直接给我干懵了,就是那种,明明有思路,但是就是写不出来的感觉,非常之糟糕。)

    思路:从外围第一层开始,一层一层旋转。
    一层一层里面也分了好多个数,就一个一个数的去旋转。

    这样听起来可能会有好多的维度,就搞得有点乱了,乱则生变呐。
    最后,我想明白了,从最简单的一个元素的旋转开始,到一层,再到一个整体。
    慢慢也就解决了。


    void rotate(vector<vector<int>>& matrix) {
    	
            int sz = matrix.size();
            int first = 0;	//圈层起点
            int end = sz - 1;	//圈层终点
            int circle = sz/2;	//圈数
    
    		//整体旋转
            for (int a = 0; a < circle; a++) {
            	//单层旋转
                for (int i = 0; i < (end-first); i++) {
      				//单个元素旋转
                    int temp = matrix[first][first+i];
                    matrix[first][first+i] = matrix[end-i][first];
                    matrix[end-i][first] = matrix[end][end-i];
                    matrix[end][end-i] = matrix[first+i][end];
                    matrix[first+i][end] = temp;
                }
                first++;
                end--;
            }
        }
    

    有效的数独

    请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。

    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
    

    数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    在这里插入图片描述

    输入:board = 
    [["5","3",".",".","7",".",".",".","."]
    ,["6",".",".","1","9","5",".",".","."]
    ,[".","9","8",".",".",".",".","6","."]
    ,["8",".",".",".","6",".",".",".","3"]
    ,["4",".",".","8",".","3",".",".","1"]
    ,["7",".",".",".","2",".",".",".","6"]
    ,[".","6",".",".",".",".","2","8","."]
    ,[".",".",".","4","1","9",".",".","5"]
    ,[".",".",".",".","8",".",".","7","9"]]
    输出:true
    

    这个就让人很难受,调试都不好调,然后我就发现了Python是个好东西,可以润滑我们的工作。
    不信你把这个破矩阵拿到二维vector里面去试试。

    那这个我也没什么好的想法,就老老实实一条一条来嘛。

    bool isValidSudoku(vector<vector<char>>& board) {
            vector<vector<int>> row (9, vector<int>(9,0));
            vector<vector<int>> col (9, vector<int>(9,0));
            vector<vector<int>> box (9, vector<int>(9,0));
    
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    if(board[i][j] == '.'){
                        continue;
                    }
                    int val = board[i][j] - '1';
                    int box_index = (i/3) * 3 + j/3;
                    if(row[i][val] == 0 && col[j][val] == 0 && box[box_index][val] == 0){
                        row[i][val] = 1;
                        col[j][val] = 1;
                        box[box_index][val] = 1;
                    }
                    else{
                        return false;
                    }
                }
            }
            return true;
        }
    

    反转字符串

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

    不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

    你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhbqj/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    来了一个简单的,这头尾双指针就好。

    void reverseChar(vector<char>& s,int begin,int end){
            char temp = s[begin];
            s[begin] = s[end];
            s[end] = temp;
        }
    
        void reverseString(vector<char>& s) {
            int i = 0,j = s.size()-1;
            while(i<j){
                reverseChar(s,i,j);
                i++;
                j--;
            }    
        }
    

    下午还有事儿,今天先到这儿。

    展开全文
  • 文章目录前言删除排序数组中的重复项买卖股票的最佳时机 ...算法很好的话当初也不至于连笔试都不敢参加。 不说废话了,从头刷起。 删除排序数组中的重复项 给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使

    前言

    今天本来要写模板编程的,但是,网上对模板编程的争论不休,我一时也拿不定主意。
    这些都是次要的,最主要的是,我拿不定主意,就会瞎学。
    并不是说有学无害,跟你说这些的人是害你的。
    学,就要时间成本,我们是没有别的东西要学了吗?算法很好的话当初也不至于连笔试都不敢参加。

    不说废话了,从头刷起。


    删除排序数组中的重复项

    给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

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

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    示例:

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

    思路都在注释中了,在原数组上维护一个二次数组,将第一次出现的数往前提:

    int removeDuplicates(vector<int>& nums) {
          int sz = nums.size();
          if(sz == 0)	//首先,不排除数组长度为0的情况
            return 0;
            
          int sz2 = 1;	//sz2纪录留下来的元素数
          int flag = nums[0];	//由于是有序列表,flag用来纪录当前所处位置的数值
          for(int i = 1;i<sz;i++){
              if(nums[i] != flag){	//如果前后数值不同,那就进来吧
                if(i > sz2)	//i>sz2,说明中间有了重复项
                    nums[sz2] = nums[i];	//那就把i处提到前面去
                sz2++;	//sz2继续往后走
                flag = nums[i];	//切换一个flag了
              }
          }  
          return sz2;
        }
    

    买卖股票的最佳时机 II

    给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。

    设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

    注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

    示例 1:

    输入: prices = [7,1,5,3,6,4]
    输出: 7
    解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
         随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3

    示例 2:

    输入: prices = [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
         注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
    

    示例 3:

    输入: prices = [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    思路其实也很简单,就是不断的寻找波峰和波谷。
    那波峰和波谷又要怎么找,因为我根本不知道什么时候波峰,什么时候波谷,先波峰还是先波谷,中间迭代多少次也不知道。
    没事的,波峰波谷在这么转,都在波里面,那就有办法。


    代码实现(思路都在注释里了):

    int maxProfit(vector<int>& prices) {
            int i = 1;
            int sz = prices.size();
            int buy = prices[0];
            int sell = buy;
            int price = 0;
    
            while(i<sz){
                //当股票一路上涨
                while(i<sz && prices[i]>=prices[i-1]){
                    sell = prices[i];
                    i++;
                }
                //涨停板
                price+=(sell-buy);
                //当股票开始一路下跌
                while(i<sz && prices[i]<=prices[i-1]){
                    buy = prices[i];
                    i++;
                }
                //跌完就该回去了
            }
            return price;
        }
    

    旋转数组

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    进阶:

    尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
    

    示例 1:

    输入: nums = [1,2,3,4,5,6,7], k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1: [7,1,2,3,4,5,6]
    向右旋转 2: [6,7,1,2,3,4,5]
    向右旋转 3: [5,6,7,1,2,3,4]
    

    示例 2:

    输入:nums = [-1,-100,3,99], k = 2
    输出:[3,99,-1,-100]
    解释: 
    向右旋转 1: [99,-1,-100,3]
    向右旋转 2: [3,99,-1,-100]
    

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    思路:这个还要多说吗?左右手翻转定理嘛。
    现在跟我伸出左手右手,背面向下,左右手平移互换位置。这就是我们的旋转嘛。

    别急。
    我们现在将左手翻转,再将右手翻转。
    接着,将两只手作为整体翻转(有一只手会比较别扭,调整一下),认真看看,跟前面是不是一样的。


    所以,代码实现:

     void rotate(vector<int>& nums, int k) {
        int sz = nums.size();
        if(k<sz)
            sz -= k
        else
            sz-=(k%sz);
                
        reverse(nums.begin(),nums.begin()+sz);
        reverse(nums.begin()+sz,nums.end());
        reverse(nums.begin(),nums.end());
    }
    

    存在重复元素

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

    如果存在一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false 。

    示例 1:

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

    示例 2:

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

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x248f5/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    思路:思路其实很明确,但是我想试一下哈希表。

    bool containsDuplicate(vector<int>& nums) {
            unordered_set<int> us;
            for(int x:nums){
                if(us.find(x)!=us.end())
                    return true;
                us.insert(x);
            }
            return false;
        }
    

    只出现一次的数字

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

    说明:

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

    思路:这题不想浪费时间,位运算,不了解位运算的小伙伴建议整体的去了解一下,很重要的。

    int singleNumber(vector<int>& nums) {
            int x = nums[0];
            for(int i = 1;i<nums.size();i++)
                x = x^nums[i];
            return x;
    
        }
    

    不再赘言。


    两个数组的交集 II

    给定两个数组,编写一个函数来计算它们的交集。

    示例 1:

    输入:nums1 = [1,2,2,1], nums2 = [2,2]
    输出:[2,2]
    

    示例 2:

    输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出:[4,9]
    

    说明:

    输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。
    我们可以不考虑输出结果的顺序。
    

    进阶:

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

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    思路:思路很多,比方说先排个序啥的。
    但是,我不用,我就要用哈希表,诶,就是练。

    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            unordered_map<int,int> um;
            int sz1 = nums1.size();
            int sz2 = nums2.size();
    
            vector<int> temp;
    
            if(sz1>sz2){
                for(int x:nums1)    //将大的插入哈希表
                    um[x]+=1;
    
                for(int y:nums2){
                    if(um[y]>0){    //如果找到了
                        temp.push_back(y);
                        um[y]--;
                    }
                }
            }
            else{
               for(int x:nums2)    //将大的插入哈希表
                    um[x]+=1;
    
                for(int y:nums1){
                    if(um[y]>0){    //如果找到了
                        temp.push_back(y);
                        um[y]--;
                    }
                } 
            }
            return temp;
        }
    

    加一

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

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

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

    示例 1:

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

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    这个题啊,其实正常情况暴力求解,但是不排除那种一串9的。
    其实对于一串就可以当做特例来解决,但是我没那兴趣。

    我就想先将数组翻转过来,头部加个1,在转回去,诶,就是玩儿、

    vector<int> plusOne(vector<int>& digits) {
            reverse(digits.begin(),digits.end());
            int i = 0;
            while(i<digits.size()){
                if(digits[i]!=9){
                    digits[i]+=1;
                    reverse(digits.begin(),digits.end());
                    return digits;
                }
                else
                    digits[i] = 0;
                i++;
            }
            digits.push_back(1);
            reverse(digits.begin(),digits.end());
            return digits;
        }
    

    移动零

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

    示例:

    输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]
    

    说明:

    必须在原数组上操作,不能拷贝额外的数组。
    尽量减少操作次数。
    

    那这不就是快慢指针吗?

    void moveZeroes(vector<int>& nums) {
    
            int fast = 0;
            int slow = 0;
    
            int sz = nums.size();
    
            while (slow < sz) {
                while (slow < sz && nums[slow] != 0)
                    slow++;
    
                if (fast <= slow)
                    fast = slow + 1;
    
                for (; fast < sz; fast++) {
                    if (nums[fast] != 0) {
                        int temp = nums[slow];
                        nums[slow] = nums[fast];
                        nums[fast] = temp;
                        break;
                    }
                }
                slow++;
            }
        }
    

    一篇八题。本篇结束。


    展开全文
  • 文章目录整数反转字符串中的第一个唯一字符有效的字母异位词验证回文串给定一个正整数 n ,输出外观数列的第 n 项。最长公共前缀 整数反转 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。...


    整数反转

    给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

    如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。
    假设环境不允许存储 64 位整数(有符号或无符号)。

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnx13t/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    这,老老实实做不就好了吗?

    int reverse(int x) {
            int rev = 0;
            while (x != 0) {
                int pop = x % 10;
                x /= 10;
                if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
                if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
                rev = rev * 10 + pop;
            }
            return rev;
        }
    

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

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

    思路:先读取字符串存入哈希表中,再遍历字符串看看哪个字符出现的最早。

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

    有效的字母异位词

    给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

    示例 1:

    输入: s = "anagram", t = "nagaram"
    输出: true
    

    示例 2:

    输入: s = "rat", t = "car"
    输出: false
    

    说明:
    你可以假设字符串只包含小写字母。

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    思路:用哈希表还是有点麻烦,还是直接vector上吧。

    bool isAnagram(string s, string t) {
            vector<int> a(26);
            for(char c:s)
                a[c-97]+=1;
            
            for(char c:t)
                a[c-97]-=1;
            
            for(int x:a)
                if(x!=0)
                    return false;
            
            return true;
        }
    

    验证回文串

    给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

    说明:本题中,我们将空字符串定义为有效的回文串。

    示例 1:

    输入: "A man, a plan, a canal: Panama"
    输出: true
    

    示例 2:

    输入: "race a car"
    输出: false
    

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    思路很直接,双指针没什么好说的。
    回头全部写完会去跟别人的解法对比一下。

    bool isPalindrome(string s) {
            int sz = s.size();
            for(int i = 0;i<sz;i++,sz--){
                while(s[i]<48 || (s[i]>58 && s[i]<65) || (s[i]>90 && s[i]<97) || s[i]<122){
                    i++;
                }
                while(s[sz]<48 || (s[sz]>58 && s[sz]<65) || (s[sz]>90 && s[sz]<97) || s[sz]<122){
                    sz--;
                }
                if(i<sz){
                    if(s[i]!=s[sz])
                        return false;
                }
            }
            return true;
        }
    

    给定一个正整数 n ,输出外观数列的第 n 项。

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

    你可以将其视作是由递归公式定义的数字字符串序列:

    countAndSay(1) = "1"
    countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。
    

    前五项如下:

    1.     1
    2.     11
    3.     21
    4.     1211
    5.     111221
    第一项是数字 1 
    描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"
    描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"
    描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"
    描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"
    

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnpvdm/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    思路:
    从“1”开始往上叠加。

    string countAndSay(int n) {
            string s = '1'
            char flag = s[0];
            int count = 0;
            string temp;
            for(int i = 0;i<s.size();i++){
                if(s[i] == flag)
                    count++;
                else{
                    temp.append(itoa(count))
                    flag = s[i];
                    count = 0;
    
                }
            }
        }
    

    最长公共前缀

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

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

    示例 1:

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

    示例 2:

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

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnmav1/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    思路:先按照字符串长度进行排序,之后对排过序的字符串取最长公共前缀子串。

    static bool compare(const string &a, const string &b){
            return a.size()<b.size();
        }
        string longestCommonPrefix(vector<string>& strs) {
            sort(strs.begin(), strs.end(),compare);
            if(strs.size()==0 || strs[0].size()==0 ){
                return "";
            }
            for(int i=0;i<strs[0].size();i++){
                for(int j=1;j<strs.size();j++){
                    if(strs[j][i]!=strs[j-1][i]){
                        return strs[0].substr(0,i);
                    }
                }
            }
            return strs[0];
        }
    
    展开全文
  • 文章目录删除链表中的节点删除链表的倒数第N个节点反转链表回文链表 删除链表中的节点 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。 ...

    删除链表中的节点

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。

    示例 1:

    输入:head = [4,5,1,9], node = 5
    输出:[4,1,9]
    解释:给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
    

    示例 2:

    输入:head = [4,5,1,9], node = 1
    输出:[4,5,9]
    解释:给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
    

    提示:

    链表至少包含两个节点。
    链表中所有节点的值都是唯一的。
    给定的节点为非末尾节点并且一定是链表中的一个有效节点。
    不要从你的函数中返回任何结果。
    

    作者:力扣 (LeetCode)
    链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnarn7/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    其实一开始我也没看太懂这个函数签名是什么意思,然后慢慢就懂了。

    void deleteNode(ListNode* node) {
            node->val = node->next->val;
            node->next = node->next->next;
        }
    

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

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

    进阶:你能尝试使用一趟扫描实现吗?

    思路:快慢指针。
    先用快指针前进n,再用两个指针同时前进,这时候快指针到尾就是慢指针倒数第n的距离了。

    ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode * fast = head;
            ListNode * slow = head;
            for(;n>0;n--)
                fast = fast->next;
            
            if(fast == NULL)
                return head->next;
            while(fast->next != NULL && slow->next->next != NULL){
                slow = slow->next;
                fast = fast->next;
            }
    
            slow->next = slow->next->next;
    
            return head;
        }
    

    反转链表

    思路:尾插法,这个真的又给我搞晕了。。。

    ListNode* reverseList(ListNode* head) {
            ListNode* prev = nullptr;
            ListNode* curr = head;
            while (curr) {
                ListNode* next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    

    回文链表

    请判断一个链表是否为回文链表。

    从中间解开,后面半部分翻转。
    然后开始一一匹配呗。

    bool func(ListNode* node, int n, int depth) {
            if (n % 2 && depth == n / 2) {
                return true;
            }
            if (n % 2 == 0 && depth == n / 2 - 1) {
                int temp = node -> next -> val;
                node -> next = node -> next -> next;
                return temp == node -> val;
            }
            int future = func(node->next, n, depth + 1);
            node -> next = node -> next -> next;
            int ret = node -> val == node -> next -> val;
            node -> next = node -> next -> next;
            return ret && future;
        }
        bool isPalindrome(ListNode* head) {
            int n = 0;
            auto p = head;
            while (p) {
                n ++;
                p = p -> next;
            }
            if (n == 0 || n == 1) return true;
            return func(head, n, 0);
        }
    
    展开全文

空空如也

空空如也

1 2 3 4
收藏数 69
精华内容 27
关键字:

lc算法刷题