一些算法题及答案

报数序列是指一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

/**

     * 暴力枚举法

     * @param nums

     * @param target

     * @return

     */

    public static int[] twoSum(int[] nums, int target) {

        int lgn = nums.length;

        for(int i = 0; i < lgn; i++){

            for(int j = i + 1; j < lgn; j++){

                if(nums[i] + nums[j] == target){

                    return new int[]{i, j};

                }

            }

        }

        return new int[0];

    }

    /**

     * MAP 处理

     * @param nums

     * @param target

     * @return

     */

    public static int[] twoSum1(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {

            int complement = target - nums[i];

            if (map.containsKey(complement)) {

                return new int[] { complement, nums[i] };

            }

            map.put(nums[i], i);

        }

        return new int[0];

    }
1.     1
2.     11
3.     21
4.     1211
5.     111221

2. 两数相加

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

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

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

示例:

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

/**

     * 链表相应位置依次相加,最后处理进位

     * @param l1

     * @param l2

     * @return

     */

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = null;

        ListNode curr = null;

        while (l1 != null || l2 != null){

            if(l1 != null && l2 != null){

                ListNode node = new ListNode(l1.val + l2.val);

                if(curr == null && head == null) head = node;

                curr = initNode(curr, node);

            }else{

                curr = initNode(curr, new ListNode(l1 != null?l1.val:l2.val));

            }

            l1 = l1 != null?l1.next:null;

            l2 = l2 != null?l2.next:null;

        }

        curr = head;

        while (curr != null){

            if(curr.val >= 10){

                curr.val -= 10;

                if(curr.next == null){

                    curr.next = new ListNode;

                }else {

                    curr.next.val += 1;

                }

            }

            curr = curr.next;

        }

        curr = null;

        return head;

    }

    public ListNode initNode(ListNode curr, ListNode newNode){

        if(curr != null){

            curr.next = newNode;

        }

        curr = newNode;

        return curr;

    }

1 被读作  "one 1"  ("一个一") , 即 11
11 被读作 "two 1s" ("两个一"), 即 21
21 被读作 "one 2",  "one 1" ("一个二" ,  "一个一") , 即 1211

3. 寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1nums2

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log。

你可以假设 nums1nums2 不会同时为空。

示例 1:

nums1 = [1, 3]nums2 = [2]则中位数是 2.0

示例 2:

nums1 = [1, 2]nums2 = [3, 4]则中位数是 /2 = 2.5

/**

     * 使用两个排序数据组的归并过程

     * 分别定义两个数组的遍历索引,每次对比提取相应数组的元素

     * 不实际存储归并后的数据,

     * 处理前半数元素即可

     * @param nums1

     * @param nums2

     * @return

     */

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int lgn1 = nums1.length;

        int lgn2 = nums2.length;

        int allLgn = lgn1 + lgn2;

        int middleIndex = allLgn/2;

        int middleLeft = 0,middleRight = 0;

        int index1 = 0;

        int index2 = 0;

        int curr = 0;

        for (int i = 0; i < middleIndex + 1; i++) {

            if(index1 < lgn1 && index2 < lgn2) {

                if (nums1[index1] > nums2[index2]) {

                    curr = nums2[index2];

                    index2++;

                } else {

                    curr = nums1[index1];

                    index1++;

                }

            }else if(index1 < lgn1){

                curr = nums1[index1];

                index1++;

            }else if(index2 < lgn2){

                curr = nums2[index2];

                index2++;

            }

            if(i == middleIndex - 1){

                middleLeft = curr;

            }

            if(i == middleIndex){

                middleRight = curr;

            }

        }

        if(allLgn%2 == 0){

            return (middleLeft + middleRight)/2.0;

        }else {

            return middleRight;

        }

    }

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

4. Z 字形变换

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

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

L   C   I   RE T O E S I I GE   D   H   N

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

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

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4输出: "LDREOEIIECIHNTSG"解释:L     D     RE   O E   I IE C   I H   NT     S     G

/**

     * 定义目标行数个链表,如示例,每次中间间隔的 numRows - 2 个列表逐个填充一个值

     * 便利给定的字符串,依次处理,直到末尾

     * @param s

     * @param numRows

     * @return

     */

    public static String convert(String s, int numRows) {

        if(numRows == 1){

            return s;

        }

        String result = "";

        if(numRows == 2){

            result = "";

            for (int i = 0; i < s.length(); i = i + 2) {

                result += s.charAt;

            }

            for (int i = 1; i < s.length(); i = i + 2) {

                result += s.charAt;

            }

            return result;

        }

        int middleCount = numRows - 2;

        List[] all = new LinkedList[numRows];

        for (int i = 0; i < numRows; i++) {

            all[i] = new LinkedList<>();

        }

        int sIndex = 0;

        int step = 0;

        while (sIndex < s.length{

            for (int i = 0; i < numRows; i++) {

                if(sIndex == s.length break;

                all[i].add(s.charAt;

                sIndex++;

            }

            for (int j = numRows - 2; j > 0 ; j--) {

                if(sIndex == s.length break;

                all[j].add(s.charAt;

                sIndex++;

            }

            step = step + middleCount;

        }

        for (int i = 0; i < numRows; i++) {

            for (int j = 0; j < all[i].size {

                result += all[i].get;

            }

        }

        return result;

    }

注意:整数顺序将表示为一个字符串。

5. 整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123输出: 321

示例 2:

输入: -123输出: -321

示例 3:

输入: 120输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

/**

     * 数据范围判断

     * @param x

     * @return

     */

    public static int reverse(int x) {

        double result = 0;

        while {

            result = result * 10 + x%10;

            if (result > Integer.MAX_VALUE) return 0;

            if (result < Integer.MIN_VALUE) return 0;

            x = x/10;

        }

        return (int) result;

    }

示例 1:

6. 回文数

判断一个整数是否是回文数。回文数是指正序和倒序读都是一样的整数。

/**

     * 转化为字符串,一次便利,首末对称位置对比

     * @param x

     * @return

     */

    public static boolean isPalindrome(int x) {

        String s = String.valueOf;

        int lgn = s.length();

        for (int i = 0,j = lgn -1; i <= j; i++,j--){

            if(s.charAt == s.charAt{

                continue;

            }else {

                return false;

            }

        }

        return true;

    }
输入: 1
输出: "1"

7. 盛最多水的容器

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

/**

     * 枚举

     * @param height

     * @return

     */

    public static int maxArea(int[] height) {

        int area = 0, lgn = height.length;

        if(lgn < 2) return 0;

        for (int i = 0; i < lgn; i++) {

            for (int i1 = i + 1; i1 < lgn; i1++) {

                int tmpArea = (height[i]>height[i1]?height[i1]:height[i]) * ;

                if(tmpArea > area){

                    area = tmpArea;

                }

            }

        }

        return area;

    }

    /**

     * 双指针

     * @param height

     * @return

     */

    public static int maxArea2(int[] height) {

        int area = 0, lgn = height.length;

        if(lgn < 2) return 0;

        for (int i = 0, j = lgn - 1; i < j; ) {

            int tmpArea = (height[i]>height[j]?height[j]:height[i]) * Math.abs;

            if(tmpArea > area){

                area = tmpArea;

                i++;//正方向前进一步,避免反方向遍历时,重复比较

            }else {

                j--;//反方向前进一步,避免正方向遍历时,重复比较

            }

        }

        return area;

    }

示例 2:

8. 整数转罗马数字

罗马数字包含以下七种字符: IVXLCDM

字符          数值I             1V             5X             10L             50C             100D             500M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X

  • II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 VX 的左边,来表示 4 和 9。
  • X 可以放在 LC 的左边,来表示 40 和 90。
  • C 可以放在 DM 的左边,来表示 400 和 900。

给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。

public static String intToRoman(int num) {

        if(num > 3999) return "";

        if(num/1000 > 0){

            return dealQianWei;

        }else if(num/100 > 0){

            return dealBaiWei;

        }else if(num/10 > 0){

            return dealShiWei;

        }else {

            return dealGeWei;

        }

    }

    /**

     * 千位

     * @param num

     * @return

     */

    public static String dealQianWei(int num){

        return countStr(num/1000, "M") + dealBaiWei;

    }

    /**

     * 百位

     * @param num

     * @return

     */

    public static String dealBaiWei(int num){

        int bc = num/100;

        if return "CM" + dealShiWei(num % 100);

        if return "CD" + dealShiWei(num % 100);

        int fbc = num/500;

        num = num%500;

        return countStr(fbc, "D") + countStr(num/100, "C") + dealShiWei;

    }

    /**

     * 十位

     * @param num

     * @return

     */

    public static String dealShiWei(int num){

        int tens = num/10;

        if(tens == 9) return "XC" + dealGeWei;

        if(tens == 4) return "XL" + dealGeWei;

        int ftens = num/50;

        num = num%50;

        return countStr(ftens, "L") + countStr(num/10, "X") + dealGeWei;

    }

    /**

     * 个位

     * @param num

     * @return

     */

    public static String dealGeWei(int num){

        if return "IX";

        if return "IV";

        if(num >= 5) return "V" + dealGeWei;

        return countStr(num, "I");

    }

    public static String countStr(int count, String num){

        if(count == 0) return "";

        String result = "";

        for (int i = 0; i < count; i++) {

            result += num;

        }

        return result;

    }
输入: 4
输出: "1211"

class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if not n : return False
        if n < 1:return False
        if n == 1: return '1'
        if n == 2: return '11'

        start = '11' 
        for i in range(3,n+1):  #从第3次开始循环至数字n-1结束
            tmp = ''            
            index = 0           
            for i in range(len(start)-1):   #循环到 start字符串长度减一结束,防止下标溢出
                if start[i] == start[i+1]:
                    index += 1               
                else:
                    index +=1               
                    tmp += str(index)+start[i]  #str(index) ==1 ,start[i] 当前数值
                    index = 0                 #index 归零

            index +=1
            tmp += str(index) + start[i+1]  #根据前面的index来判断最后一位是否和前一位相等,相等就加index+1,不等就是0+1,然后加上上一次循环字符串的最后一位
            start = tmp          #内循环结束后,为下次循环的start赋值
        return tmp

9. 三数之和

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

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

注意:利用上面的两数值和

public static List<List<Integer>> threeSum(int[] nums) {

        if(nums == null || nums.length < 3) return new ArrayList();

        Set<List<Integer>> result = new HashSet<>();

        List<Integer> numList = new ArrayList();

        for (int num : nums) {

            numList.add;

        }

        for (Integer num : numList) {

            List<Integer> copy = new ArrayList();

            copy.addAll;

            copy.remove;

            List<int[]> tmp = twoSum(copy, -num);

            if(tmp.size{

                for (int[] ints : tmp) {

                    List<Integer> list = new ArrayList(){{add;add;add;}};

                    Collections.sort;

                    result.add;

                }

            }

        }

        return new ArrayList;

    }

    public static List<int[]> twoSum(List<Integer> nums, int target) {

        List<int[]> result = new ArrayList();

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.size {

            int complement = target - nums.get;

            if (map.containsKey(complement)) {

                result.add(new int[] { complement, nums.get;

            }

            map.put(nums.get;

        }

        return result;

    }

 

10. 最接近的三数之和

给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

public static int threeSumClosest(int[] nums, int target) {

        int min = Integer.MAX_VALUE;

        int ele1 = 0, ele2 = 0, ele3 = 0;

        for (int i = 0; i < nums.length; i++) {

            for (int i1 = 0; i1 < nums.length; i1++) {

                if  continue;

                for (int i2 = 0; i2 < nums.length; i2++) {

                    if (i2 == i1 || i2 == i) continue;

                    int sum = Math.abs(nums[i] + nums[i1] + nums[i2] - target);

                    if (sum < min) {

                        min = sum;

                        ele1 = nums[i];

                        ele2 = nums[i1];

                        ele3 = nums[i2];

                    }

                }

            }

        }

        return ele1 + ele2 + ele3;

    }

11. 缺失的第一个正数

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 1:

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

示例 2:

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

示例 3:

输入: [7,8,9,11,12]输出: 1

/**

     * 数组操作

     * @param nums

     * @return

     */

    public static int firstMissingPositive(int[] nums) {

        int max = 0;

        for (int i = 0; i < nums.length; i++) {

            if(nums[i] < 0) continue;

            if(nums[i] > max){

                max = nums[i];

            }

        }

        max = max == Integer.MAX_VALUE?max:max + 2;

        for (int i = 1; i < max; i++) {

            if(contains continue;

            return i;

        }

        return max + 1;

    }

    public static boolean contains(int[] nums, int ele){

        for (int i = 0; i < nums.length; i++) {

            if(nums[i] == ele) return true;

        }

        return false;

    }

    /**

     * map操作

     * @param nums

     * @return

     */

    public static int firstMissingPositive1(int[] nums) {

        Map<Integer, Integer> vs = new HashMap<>();

        int max = 0;

        for (int i = 0; i < nums.length; i++) {

            if(nums[i] < 0) continue;

            if(nums[i] > max){

                max = nums[i];

            }

            vs.put(nums[i], i);

        }

        max = max == Integer.MAX_VALUE?max:max + 2;

        for (int i = 1; i < max; i++) {

            if(vs.get != null) continue;

            return i;

        }

        return max + 1;

    }

12. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

图片 1

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6

/**

     * 分割

     * @param height

     * @return

     */

    public static int trap(int[] height) {

        //最大索引位置

        int maxIndex = findMax;



        int lsubMaxindex = maxIndex, rsubMaxIndex = maxIndex;

        int area = 0;

        //左边处理

        while (lsubMaxindex > 0){

            int tmpMax = lsubMaxindex;

            lsubMaxindex = findMax(Arrays.copyOfRange(height, 0, tmpMax));

            area += height[lsubMaxindex] * (tmpMax - lsubMaxindex - 1);

            for (int i = lsubMaxindex + 1; i < tmpMax; i++) {

                area -= height[i] * 1;

            }

        }

        //右边处理

        while (rsubMaxIndex < height.length - 1){

            int tmpMax = rsubMaxIndex;

            rsubMaxIndex = tmpMax + findMax(Arrays.copyOfRange(height, tmpMax + 1, height.length)) + 1;

            area += height[rsubMaxIndex] * (rsubMaxIndex - tmpMax - 1);

            for (int i = tmpMax + 1; i < rsubMaxIndex; i++) {

                area -= height[i] * 1;

            }

        }

        return area;

    }

    public static int findMax(int[] nums){

        int max = 0, maxIndex = 0;

        for (int i = 0; i < nums.length; i++) {

            if(nums[i] > max){

                max = nums[i];

                maxIndex = i;

            }

        }

        return maxIndex;

    }

13. 字符串相乘

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

示例 1:

输入: num1 = "2", num2 = "3"输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"输出: "56088"

说明:

  1. num1num2 的长度小于110。
  2. num1num2 只包含数字 0-9
  3. num1num2 均不以零开头,除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型(比如 BigInteger)直接将输入转换为整数来处理
public static String multiply(String num1, String num2) {

        if(num1 == null || num2 == null || "".equals || "".equals || "0".equals || "0".equals return String.valueOf;

        int lgn1 = num1.length(), lgn2 = num2.length();

        int[] result = new int[lgn1 + lgn2];

        int resultIndex = result.length - 1;

        for (int i = lgn1 - 1; i > -1 ; i--) {

            int first = Integer.parseInt(String.valueOf(num1.charAt;

            int innerIndex = 0;

            for (int j = lgn2 - 1; j > -1 ; j--) {

                int second = Integer.parseInt(String.valueOf(num2.charAt;

                int plus = first * second;

                result[resultIndex - innerIndex] += plus%10;

                if(plus >= 10) {

                    result[resultIndex - innerIndex - 1] += plus / 10;

                }

                innerIndex++;

            }

            resultIndex--;

        }

        //处理进位

        StringBuilder sb = new StringBuilder();

        for (int i = result.length - 1; i >= 0; i--) {

            if(result[i]>=10) {

                result[i - 1] += result[i]/10;

                result[i] %= 10;

            }

        }

        //提取有效位

        boolean start = false;

        for (int i = 0; i < lgn1 + lgn2 ; i++) {

            if(!start && result[i] != 0){

                start = true;

            }

            if{

                sb.append(result[i]);

            }

        }

        return sb.toString();

    }

本文由金沙官网线上发布于编程,转载请注明出处:一些算法题及答案

您可能还会对下面的文章感兴趣: