面试经典150题【11-20】

这篇具有很好参考价值的文章主要介绍了面试经典150题【11-20】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

面试经典150题【11-20】

388.O(1) 时间插入、删除和获取随机元素

用一个哈希表和一个变长数组组成一个新的数据类型。
获取随机元素的话,直接random一个数然后从数组里取就行。
插入和删除的话,先判断有没有这个数,哈希表里存的是{ 数据:在变长数组中的索引}
插入的话直接插变长数组末尾,然后再在哈希表里插
删除的话,把最后一个元素放到要删除的位置,然后删除最后一个元素即可。哈希里的也要set一下然后删一下。

238.除自身以外数组的乘积

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法,且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

以【1,2,3,4,5】来举例,对于3来说,可以让前面×1×后面
创建一个全为1的数组来代替1
双指针遍历两次,i指针代表前缀和,J指针代表后缀和

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;
        int[] ans=new int[n];
        Arrays.fill(ans,1);
        int beforesum=1,aftersum=1;
        for(int i=0,j=n-1;i<n;i++,j--){
            ans[i] *=beforesum;
            ans[j] *=aftersum;
            beforesum *=nums[i];
            aftersum *=nums[j];
        }
        return ans;
    }
}

134加油站

面试经典150题【11-20】,面试,算法,leetcode
先建立一个差分数组,从头开始累加,累加失败后从失败数的后一位累加。累加N次成功即可。
时间复杂度O(2N)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n=gas.length;
        int []diff=new int[n];
        for(int i=0;i<n;i++){
            diff[i]=gas[i]-cost[i];
        }
       

        int ans=0,i=0;
        while(i<n){
            int sum=0,cnt=0;
            //cnt计数,cnt循环一圈应该是n
            while(cnt<n){
                sum+=diff[(i+cnt)%n];
                if(sum<0){
                    break;
                }
                cnt++;
            }

            if(cnt==n){
                return i;
            }else{
                //跳到负数之后的一位
                i+=cnt+1;
            }
        }

        return -1;
       

    }
}

135.分发糖果

面试经典150题【11-20】,面试,算法,leetcode
先从左往右遍历一遍,再从右往左遍历(赋值的时候应该赋值Max)

class Solution {
    public int candy(int[] ratings) {
        int []ans=new int[ratings.length];
        ans[0]=1;
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                ans[i]=ans[i-1]+1;
            }else{
                ans[i]=1;
            }
        }
        for(int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                ans[i]=Math.max(ans[i],ans[i+1]+1);
            }
        }
        int sum=0;
        for(int i=0;i<ratings.length;i++){
            sum+=ans[i];
        }
        return sum;

    }
}

或者用left[] 和right[] 两个数组来分别遍历两次
然后ans[]= Max(left,right)
这样也是满足从左到右和从右到左两个规则的最小值。

42. 接雨水

面试经典150题【11-20】,面试,算法,leetcode
方法一:先算一个leftMax数组,再算一个rightMax数组。然后每个格子的存储水的量就等于
min(leftMax,rightMax) - height

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

如果是想调整为0(1)的空间复杂度的话,也是记录leftMax和rightMax两个变量。
当左边最高比右边最高低的时候,利用漏桶效应,是左边最高减去本地的height。
右边同理。

      while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }

13.罗马数字

面试经典150题【11-20】,面试,算法,leetcode
IV是15,所以是5-1,则后一个比前一个数字大,则前一个数字是减法。
否则就是加法,最后一个数字肯定是加法。

class Solution {
    public int romanToInt(String s) {
         int sum = 0;
        int preNum = symbolValues.get(s.charAt(0));
        for(int i = 1;i < s.length(); i ++) {
            int num = symbolValues.get(s.charAt(i));
            if(preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }

    Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};
}

12.整数 转 罗马数字

硬编码没意义

58.最后一个单词的长度

没意思,注意一下最后可能有空格,先写个while循环把空格排除掉就行

14.最长公共前缀

面试经典150题【11-20】,面试,算法,leetcode
无论是什么算法,肯定是O(MN)的复杂度。
依次遍历所有的字符串,选择求取公共字符串函数(目前的公共字符串,下一个普通字符串)即可

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空,直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 初始公共前缀为第一个字符串
        String commonPrefix = strs[0];

        // 遍历剩余的字符串
        for (int i = 1; i < strs.length; i++) {
            // 比较当前字符串与当前最长公共前缀,更新最长公共前缀
            commonPrefix = getCommonPrefix(commonPrefix, strs[i]);

            // 如果最长公共前缀已经为空,直接返回
            if (commonPrefix.equals("")) {
                return "";
            }
        }

        // 返回最长公共前缀
        return commonPrefix;
    }

    // 辅助函数,用于获取两个字符串的公共前缀
    private String getCommonPrefix(String str1, String str2) {
        int index = 0;
        // 找到两个字符串的公共前缀的长度
        while (index < str1.length() && index < str2.length() && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        // 返回公共前缀
        return str1.substring(0, index);
    }
}

151.反转字符串中的单词

先把前后的空格删了,再从后到前提取每一个单词,再拼接所有的单词。
“ hello world ”–>“world hello”文章来源地址https://www.toymoban.com/news/detail-834159.html

class Solution {
    public static String reverseWords(String s) {
        StringBuilder ans = new StringBuilder();
        s = s.trim(); // 删除首尾的空格
        int j = s.length() - 1, i = j; // 开始的时候ij两个指针都在最右边
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ')
                i--; // 搜索单词的最前面
            ans.append(s.substring(i + 1, j + 1) + " "); // 把新单词添加上
            while (i >= 0 && s.charAt(i) == ' ')
                i--; // 搜索单词的最后面
            j = i;
        }
        return ans.toString().trim();
    }
}

到了这里,关于面试经典150题【11-20】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-面试经典150题-day23】

    目录 108. 将有序数组转换为二叉搜索树  148.排序链表  427.建立四叉树  23.合并K个升序链表   108. 将有序数组转换为二叉搜索树 题意: 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「

    2024年02月09日
    浏览(44)
  • LeetCode面试经典150题(day 1)

    LeetCode是一个免费刷题的一个网站,想要通过笔试的小伙伴可以每天坚持刷两道算法题。 接下来,每天我将更新LeetCode面试经典150题的其中两道算法题,一边巩固自己,一遍希望能帮助到有需要的小伙伴。 88.合并两个有序数组 给你两个按  非递减顺序  排列的整数数组  nu

    2024年02月11日
    浏览(37)
  • LeetCode面试经典150题(day 2)

    26. 删除有序数组中的重复项 难度: 简单    给你一个  升序排列  的数组  nums  ,请你  原地  删除重复出现的元素,使每个元素  只出现一次  ,返回删除后数组的新长度。元素的  相对顺序  应该保持  一致  。然后返回  nums  中唯一元素的个数。 考虑  nums  的唯一

    2024年02月11日
    浏览(47)
  • 算法训练day11Leetcode20有效的括号1047删除字符串中所有相邻重复项150逆波兰表达式求值

    https://leetcode.cn/problems/valid-parentheses/description/ https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html 判断右括号后忘记pop 括号匹配是使用栈解决的经典问题。 如果还记得编译原理的话,编译器在 词法分析的过程中处理括号、花括号等这个符号的逻辑,也是使用了栈

    2024年01月17日
    浏览(76)
  • LeetCode150道面试经典题-- 快乐数(简单)

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」  定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为  1,那么这个数就是快乐数。 如果

    2024年02月12日
    浏览(40)
  • Leetcode面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年01月16日
    浏览(72)
  • Leetcode面试经典150题刷题记录 —— 数学篇

    Leetcode面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试经典

    2024年01月21日
    浏览(70)
  • Leetcod面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年02月03日
    浏览(43)
  • LeetCode150道面试经典题-合并两个有序数组(简单)

    题目: 给你两个按 非递减顺序 排列的整数数组  nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对

    2024年02月14日
    浏览(44)
  • 【leetcode面试经典150题】29.三数之和(C++)

    【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致) 给你一个整数数组 

    2024年04月13日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包