面试经典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题-day14】

      目录 19.删除链表的倒数第N个结点  82.删除排序链表中的重复元素Ⅱ  61. 旋转链表  86.分隔链表  146.LRU缓存 19.删除链表的倒数第N个结点 题意: 给你一个链表,删除链表的倒数第  n   个结点,并且返回链表的头结点。 【输入样例】head = [1,2,3,4,5],n=2 【输出样例】[1,2,3,5

    2024年02月11日
    浏览(43)
  • 【LeetCode-面试经典150题-day23】

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

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

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

    2024年02月11日
    浏览(36)
  • 算法训练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日
    浏览(75)
  • LeetCode150道面试经典题-- 快乐数(简单)

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

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

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

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

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

    2024年02月03日
    浏览(41)
  • Leetcode面试经典150题刷题记录 —— 数学篇

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

    2024年01月21日
    浏览(60)
  • leetcode每日一题——189.轮转数组(面试经典150题)

    189. 轮转数组 - 力扣(LeetCode) 给定一个整数数组  nums ,将数组中的元素 向右轮转  k   个位置 ,其中  k   是非负数。 示例1: 示例2: 1 = nums.length = 105 -231 = nums[i] = 231 - 1 0 = k = 105        对题目进行分析可知,我们需要根据轮转量k,将数组后面的k个元素按照原来的顺

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

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

    2024年02月14日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包