bytedance算法题集

bytedance

1、最长公共前缀

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

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

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:

输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明:

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

解题思路:

首先,以字符串数组中的第一个元素作为基准串,然后用这个基准串每个字符去匹配剩下元素对应的位置的字符,只要遇到不相等的那么就直接返回最终的结果

class Solution {
    public String longestCommonPrefix(String[] strs) {
           if(strs == null || strs.length == 0) {
               return "";
           }
           if(strs.length == 1) {
               return strs[0];
           }
           String targetStr = strs[0];//取出第一个元素作为基准串
           StringBuilder sb = new StringBuilder();
           for(int i = 0; i < targetStr.length(); i++) {//然后用基准串中的每个字符都与剩下元素中对应的位置字符比较
               int j;
               for(j = 1; j < strs.length; j++) {
                   if(i >= strs[j].length() || targetStr.charAt(i) != strs[j].charAt(i)){
                       return sb.toString();
                   }
               }
               if(j >= strs.length) {
                  sb.append(String.valueOf(targetStr.charAt(i)));
               }
           }
           return sb.toString();
    }
}

2、只出现一次的数字

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

说明:

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

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

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

解题思路:

首先,善于利用题目已知条件,只存在一个出现一次元素,其余元素都出现了两次,所以想到了异或位运算。因为一个数与相同数异或两次还是原来的📚,那么最终结果就是只剩下出现一次元素的值了。

class Solution {
    public int singleNumber(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int result = nums[0];
        for(int i = 1; i < nums.length; i++) {
            result ^= nums[i];
        }
        return result;
    }
}

3、旋转数组

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

示例 1:

输入: [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:

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

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

解题思路:

这个方法基于这个事实:当我们旋转数组 k 次, k%nk%n 个尾部元素会被移动到头部,剩下的元素会被向后移动。

在这个方法中,我们首先将所有元素反转。然后反转前 k 个元素,再反转后面 n-kn−k 个元素,就能得到想要的结果。

假设 n=7n=7 且 k=3k=3 。

原始数组                  : 1 2 3 4 5 6 7
反转所有数字后             : 7 6 5 4 3 2 1
反转前 k 个数字后          : 5 6 7 4 3 2 1
反转后 n-k 个数字后        : 5 6 7 1 2 3 4 --> 结果
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while(start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

4、两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解题思路:

我们首先从最低有效位也就是列表 l1l1 和 l2l2 的表头开始相加。由于每位数字都应当处于 0 \ldots 90…9 的范围内,我们计算两个数字的和时可能会出现 “溢出”。例如,5 + 7 = 125+7=12。在这种情况下,我们会将当前位的数值设置为 22,并将进位 carry = 1carry=1 带入下一次迭代。进位 carrycarry 必定是 00 或 11,这是因为两个数字相加(考虑到进位)可能出现的最大和为 9 + 9 + 1 = 199+9+1=19。


   转载规则


《bytedance算法题集》 mikyou 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
Android中Retrofit2框架源码解析 Android中Retrofit2框架源码解析
Android中Retrofit2框架源码解析一、Retrofit简介1、阐述 Retrofit是一个基于Restful的HTTP网络请求框架(实际上内部真正网络请求是交由OkHttp去实现的),换句话说Retrofit实际上是一个负责网络
2020-02-03
下一篇 
排序 排序
一、排序算法阐述算法里边最常用也是最基本的就是排序算法和查找算法了,本文主要讲解算法里边最经典的十大排序算法。在这里我们根据他们各自的实现原理以及效率将十大排序算法分为两大类: 非线性比较类排序:非线性是指算法的时间复杂度不能突破(nlog
  目录