一些算法题及答案

2019-03-01 10:13:59来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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];
    }

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(1);
                }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;
    }

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

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

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

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

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/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;
        }
    }

4. Z 字形变换

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

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

L   C   I   R
E T O E S I I G
E   D   H   N

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

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

string convert(string s, int numRows);

示例 1:

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

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     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(i);
            }
            for (int i = 1; i < s.length(); i = i + 2) {
                result += s.charAt(i);
            }
            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));
                sIndex++;
            }
            for (int j = numRows - 2; j > 0 ; j--) {
                if(sIndex == s.length()) break;
                all[j].add(s.charAt(sIndex));
                sIndex++;
            }
            step = step + middleCount;
        }
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < all[i].size(); j++) {
                result += all[i].get(j);
            }
        }
        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 (x != 0){
            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;
    }

6. 回文数

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

 

/**
     * 转化为字符串,一次便利,首末对称位置对比
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        int lgn = s.length();
        for (int i = 0,j = lgn -1; i <= j; i++,j--){
            if(s.charAt(i) == s.charAt(j)){
                continue;
            }else {
                return false;
            }
        }
        return true;
    }

7. 盛最多水的容器

给定 n 个非负整数 a1a2,...,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]) * (i1 - 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(j - i);
            if(tmpArea > area){
                area = tmpArea;
                i++;//正方向前进一步,避免反方向遍历时,重复比较
            }else {
                j--;//反方向前进一步,避免正方向遍历时,重复比较
            }
        }
        return area;
    }

8. 整数转罗马数字

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

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

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

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

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

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

 

public static String intToRoman(int num) {
        if(num > 3999) return "";
        if(num/1000 > 0){
            return dealQianWei(num);
        }else if(num/100 > 0){
            return dealBaiWei(num);
        }else if(num/10 > 0){
            return dealShiWei(num);
        }else {
            return dealGeWei(num);
        }
    }

    /**
     * 千位
     * @param num
     * @return
     */
    public static String dealQianWei(int num){
        return countStr(num/1000, "M") + dealBaiWei(num%1000);
    }

    /**
     * 百位
     * @param num
     * @return
     */
    public static String dealBaiWei(int num){
        int bc = num/100;
        if(bc == 9) return "CM" + dealShiWei(num % 100);
        if(bc == 4) return "CD" + dealShiWei(num % 100);
        int fbc = num/500;
        num = num%500;
        return countStr(fbc, "D") + countStr(num/100, "C") + dealShiWei(num%100);
    }

    /**
     * 十位
     * @param num
     * @return
     */
    public static String dealShiWei(int num){
        int tens = num/10;
        if(tens == 9) return "XC" + dealGeWei(num % 10);
        if(tens == 4) return "XL" + dealGeWei(num % 10);
        int ftens = num/50;
        num = num%50;
        return countStr(ftens, "L") + countStr(num/10, "X") + dealGeWei(num%10);
    }

    /**
     * 个位
     * @param num
     * @return
     */
    public static String dealGeWei(int num){
        if(num == 9) return "IX";
        if(num == 4) return "IV";
        if(num >= 5) return "V" + dealGeWei(num % 5);
        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;
    }

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(num);
        }

        for (Integer num : numList) {
            List<Integer> copy = new ArrayList();
            copy.addAll(numList);
            copy.remove(num);
            List<int[]> tmp = twoSum(copy, -num);
            if(tmp.size()>0){
                for (int[] ints : tmp) {
                    List<Integer> list = new ArrayList(){{add(num);add(ints[0]);add(ints[1]);}};
                    Collections.sort(list);
                    result.add(list);
                }
            }
        }

        return new ArrayList(result);
    }

    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(); i++) {
            int complement = target - nums.get(i);
            if (map.containsKey(complement)) {
                result.add(new int[] { complement, nums.get(i) });
            }
            map.put(nums.get(i), i);
        }
        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 (i1 == i) 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(nums, i)) 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(i) != null) continue;
            return i;
        }
        return max + 1;
    }

12. 接雨水

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

image 

上面是由数组 [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(height);
        
        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(num1) || "".equals(num2) || "0".equals(num1) || "0".equals(num2)) return String.valueOf(0);
        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(i)));
            int innerIndex = 0;
            for (int j = lgn2 - 1; j > -1 ; j--) {
                int second = Integer.parseInt(String.valueOf(num2.charAt(j)));
                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(start){
                sb.append(result[i]);
            }
        }
        return sb.toString();
    }

14. 跳跃游戏 II

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

 

/**
     * 枚举遍历
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        if(nums == null || nums.length == 1) return 0;
        if(nums.length == 2) return 1;

        int steps = Integer.MAX_VALUE/2;
        int initStep = 1;
        if(nums[0] >= nums.length - 1) return 1;
        if(nums[0] == 0) return steps;

        while (initStep <= nums[0]){
            int subNeedStep = jump(Arrays.copyOfRange(nums, initStep, nums.length));
            if(subNeedStep + 1 < steps){
                steps = subNeedStep + 1;
            }
            initStep++;
        }
        return steps;
    }

    /**
     * 每次选择 和下一跳(最大跳值)之和最远的=》递归处理
     * @param nums
     * @return
     */
    public static int jump2(int[] nums) {
        if(nums == null || nums.length == 1) return 0;
        if(nums.length == 2) return 1;

        int steps = Integer.MAX_VALUE/2;
        int initStep = nums[0];
        if(nums[0] >= nums.length - 1) return 1;
        if(nums[0] == 0) return steps;

        int maxSum = 0;
        int fromStep = 1;
        while (initStep > 0){
            if(initStep + nums[initStep] > maxSum){
                fromStep = initStep;
                maxSum = initStep + nums[initStep];
            }
            initStep--;
        }
        steps = 1 + jump2(Arrays.copyOfRange(nums, fromStep, nums.length));
        return steps;
    }

15. 全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
 
/**
     * 递归处理
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if(nums.length == 1) {
            result.add(new ArrayList(){{add(nums[0]);}});
            return result;
        }
        for (int num : nums) {
            int[] tmp = new int[nums.length - 1];
            int index = 0;
            for (int i = 0; i < nums.length; i++) {
                if(num == nums[i]) continue;
                tmp[index] = nums[i];
                index++;
            }
            List<List<Integer>> sub = permute(tmp);
            sub.stream().forEach(item->item.add(num));
            result.addAll(sub);
        }
        return result;
    }

给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
 
/**
     * 递归处理
     * Set 处理重复
     * @param nums
     * @return
     */
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if(nums.length == 1) {
            result.add(new ArrayList(){{add(nums[0]);}});
            return result;
        }
        for (int num : nums) {
            int[] tmp = new int[nums.length - 1];
            int index = 0;
            for (int i = 0; i < nums.length; i++) {
                if(num == nums[i] && index == i) continue;
                tmp[index] = nums[i];
                index++;
            }
            List<List<Integer>> sub = permuteUnique(tmp);
            sub.stream().forEach(item->item.add(num));
            result.addAll(sub);
        }
        Set<List<Integer>> sets = new HashSet();
        result.stream().forEach(item->sets.add(item));
        return new ArrayList(sets);
    }

16. 旋转图像

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明:

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

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵,使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
 
public static void rotate(int[][] matrix) {
        int step = matrix.length;
        int[][] tmp = new int[step][step];
        for (int i = 0; i < step; i++) {
            for (int j = 0; j < step; j++) {
                tmp[i][j] = matrix[step - j - 1][i];
            }
        }
        for (int i = 0; i < step; i++) {
            for (int j = 0; j < step; j++) {
                matrix[i][j] = tmp[i][j];
            }
        }
    }

17. 字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明:

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

 

public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList();
        if(strs == null ||strs.length == 0) return result;
        if(strs.length == 1){
            result.add(Arrays.asList(strs[0]));
            return result;
        }

        Map<String, List<String>> maps = new HashMap();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String sorted = Arrays.toString(arr);
            if(maps.get(sorted) != null){
                maps.get(sorted).add(str);
            }else {
                maps.put(sorted, new ArrayList(){{add(str);}});
            }
        }
        maps.remove(null);
        return maps.values().stream().collect(Collectors.toList());
    }

18. Pow(x, n)

实现 pow(x, n) ,即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2

-2

 = 1/2

2

 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

 

/**
     * 快速降幂 避免递归过深造成栈溢出
     * @param x
     * @param n
     * @return
     */
    public static double power(double x, int n) {
        if(!(x > -100 && x < 100)) return 0;
        if(!(n <= Integer.MAX_VALUE && n >= Integer.MIN_VALUE)) return 0;

        if(x == 0) return 0;
        if(x == 1) return 1;
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -1) return 1/x;

        if(n > 1 || n < -1){
            double nextValue = power(x, n / 2);
            return (n % 2 == 0 ? 1 : (n > 0 ? x : 1/x)) * nextValue * nextValue;
        }
        return x;
    }

19. 进制转换

进制转换 十进制 =》 62进制
这里所谓62进制是指采用0~9A~Za~z等62个字符进行编码(按ASCII顺序由小到大)。
 
public static String BASE = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    public static String transfer(int num) {
        int scale = 62;
        StringBuilder sb = new StringBuilder();

        while (num > 0) {
            //余数对照进制基本位 BASE 放到相应位置
            sb.append(BASE.charAt(num % scale));
            //除处理下一进位
            num = num / scale;
        }

        sb.reverse();

        return sb.toString();
    }

20. 报数

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

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

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

给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。

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

 

public static String countAndSay(int n) {
        if(n < 1 || n > 30) return "";
        int start = 1;
        String report = "1";
        String result = "";
        while (start < n ){
            result = "";
            for (int i = 0; i < report.length();) {
                int c = i;
                int count = 1;
                while (c + 1 < report.length()){
                    if(report.charAt(c) != report.charAt(c + 1)){
                        break;
                    }
                    count++;
                    c++;
                }
                result += String.valueOf(count) + String.valueOf(report.charAt(i));
                i = i + count;
            }
            report = result;
            start++;
        }

        return report;
    }

 

待续 。。。 。。。

 

项目地址:https://github.com/windwant/windwant-service/tree/master/algorithm


原文链接:https://www.cnblogs.com/niejunlei/p/10451333.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:JDBC_时间处理_Date_Time_Timestamp区别_随机日期生成

下一篇:垃圾收集器和内存分配策略