某个算法题及答案美高梅4858官方网站

作者:编程技术
输入: 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

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

    }

翻译

 

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;

            return result;

        }

        Map<String, List<String>> maps = new HashMap();

        for (String str : strs) {

            char[] arr = str.toCharArray();

            Arrays.sort;

            String sorted = Arrays.toString;

            if(maps.get != null){

                maps.get.add;

            }else {

                maps.put(sorted, new ArrayList(){{add;

            }

        }

        maps.remove;

        return maps.values().stream().collect(Collectors.toList;

    }

数数并报数

难度系数:容易

数数并报数顺序按如下规律开始递增:
1,11,21,1211,111221,……

1 读作“1个1”11
11 读作“2个1”21
21 读作“1个21个1”得1211

给定一个整数n,生成第n个序列。

注意:数字序列应该用字符串表示。

示例 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;

    }

每日算法——leetcode系列


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

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;

    }

标签: C 算法 LeetCode 字符串 递归

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

22. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下。注意 1 不对应任何字母。

美高梅4858官方网站 1

示例:

输入:"23"输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

输入:"234"

输出:

[aeg, ceg, beh, aei, beg, aeh, cei, ceh, bei, bfg, afh, afg, cfh, bdg, bfi, adh, cfg, bfh, adg, afi, cdh, bdi, cdg, cfi, bdh, adi, cdi].

说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

public static Map<Integer, String> maps = new HashMap(){{

        put(2, "abc"); put(3, "def"); put(4, "ghi"); put(5, "jkl"); put(6, "mno"); put(7, "pqrs"); put(8, "tuv"); put(9, "wxyz");

    }};

    public static List<String> letterCombinations(String digits) {

        int size = digits.length();

        if(digits == null || digits.length return new ArrayList<>();

        Set<String> coms = new HashSet();

        if(size == 1){

            String ele = maps.get(Integer.parseInt;

            for (int i = 0; i < ele.length {

                coms.add(String.valueOf(ele.charAt;

            }

        }else if(size == 2){

            String left = maps.get(Integer.parseInt(String.valueOf(digits.charAt;

            String right = maps.get(Integer.parseInt(String.valueOf(digits.charAt;

            for (int k = 0; k < left.length {

                for (int l = 0; l < right.length {

                    coms.add(String.valueOf(left.charAt   String.valueOf(right.charAt;

                }

            }

        }else {

            String left = maps.get(Integer.parseInt(String.valueOf(digits.charAt;

            List<String> subs = letterCombinations(digits.substring(1, digits.length;

            subs.stream().forEach(item->{

                for (int l = 0; l < left.length {

                    coms.add(String.valueOf(left.charAt   item);

                }

            });

        }

        return new ArrayList<>;

    }

思路

此题我觉得英文的表面意思跟实际要的不一样。
题意:数上次字符串中的连续出现数值的个数, 将这些字符串拼接起来

  • n=1时,输出字符串1;
  • n=2时,因为上次字符串1,1连续出现1次,就是1个1,所以输出11;
  • n=3时,由于上次字符串11,其中1连续出现两次,就是2个1,所以输出21;
  • n=4时,由于上次字符串是21,其中2出现1次,1出现1次,所以输出1211;
  • n=5时,由于上次字符串1211,第个1连续出现1次为11,第二个2连续出现1次为12,第三个1跟第四个1连续出现了2次,为21,所以输出111221
输入: 1
输出: "1"

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;

    }

代码

#include <iostream>
#include <sstream>
using namespace std;

class Solution {

public:
     string countAndSay(int n) {
        if(n == 1){
            return "1";
        }
        //递归调用
         string str = countAndSay(n-1);
        int len = static_cast<int>(str.length());
        int count = 1;
        stringstream s;
        for(int i = 0; i < len;   i){
            if(str[i] == str[i 1]){
                count  ;
            } else {
                s << count << str[i];

                count = 1;
            }
        }
        return s.str();
    }
};

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

12. 接雨水

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

美高梅4858官方网站 2

上面是由数组 [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;

    }

问题 Count and Say

Difficulty: Easy

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

class Solution {
public:
    string countAndSay(int n) {

    }
};

示例 2:

25. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,cd ,使得 a b c d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。满足要求的四元组集合为:[  [-1,  0, 0, 1],  [-2, -1, 1, 2],  [-2,  0, 0, 2]]

/**

     * 四数之和

     * @param nums

     * @param target

     * @return

     */

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

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

        List<Integer> numList = new ArrayList();

        for (int num : nums) {

            numList.add;

        }

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

            List<Integer> copy = new ArrayList();

            copy.addAll;

            copy.remove(numList.get;

            List<List<Integer>> threes = threeSum(copy, target - numList.get;

            final int finalI = i;

            threes.forEach(item -> {

                item.add(nums[finalI]);

                Collections.sort;

                sets.add;

            });

        }

        return new ArrayList;

    }

    /**

     * 三数之和

     * @param nums

     * @param target

     * @return

     */

    public static List<List<Integer>> threeSum(List<Integer> nums, int target) {

        if(nums == null || nums.size 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, target - num);

            if(tmp.size{

                for (int[] ints : tmp) {

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

                    Collections.sort;

                    result.add;

                }

            }

        }

        return new ArrayList;

    }

    /**

     * 两数之和

     * @param nums

     * @param target

     * @return

     */

    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;

    }

待续 。。。 。。。

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

24. 有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

//括号映射

    public static Map<String, String> maps = new HashMap(){{

        put("}", "{");

        put("]", "[");

        put(")", ";

        put("{", "}");

        put("[", "]");

        put("(", ")");

    }};

    public static boolean isValid {

        if(s == null || s.length return false;

        if(s.length return true;

        int index = 1;

        //当前字符

        char focus = s.charAt;

        //存储非相邻匹配的符号

        List<String> unmap = new LinkedList();

        while (index < s.length

            //相邻对比

            if(String.valueOf(s.charAt.equals(maps.get(String.valueOf{

                //处理存储的非相邻匹配的符号匹配

                int lIndex = unmap.size() - 1;

                if(lIndex > 0) {

                    unmap.remove;

                }

                while (lIndex > 0){

                    index  ;

                    lIndex--;

                    //倒序遍历匹配

                    if(unmap.get.equals(maps.get(String.valueOf(s.charAt){

                        //匹配上则删除list中元素

                        unmap.remove;

                        continue;

                    }else {

                        //匹配不上则加入到list中

                        unmap.add(String.valueOf(s.charAt;

                        index--;

                        break;

                    }

                }

                index  ;

                if(index >= s.length return true;

                focus = s.charAt;

                index  ;

            }else {

                //相邻不匹配则加入到 list中以供后续使用

                if(s.substring.contains(String.valueOf(maps.get(String.valueOf && (index   1 < s.length &&s.substring(index   1).contains(String.valueOf(maps.get(String.valueOf(s.charAt)){

                    //第一次非相邻的时候添加头一个元素

                    if(unmap.size {

                        unmap.add(String.valueOf;

                    }

                    unmap.add(String.valueOf(s.charAt;

                    focus = s.charAt;

                    index  ;

                }else{

                    return false;

                }

            }

        return false;

    }

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

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

    }

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;

    }

项目地址:

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;

        }

    }

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;

    }

20. 报数

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

1.     12.     113.     214.     12115.     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 != report.charAt{

                        break;

                    }

                    count  ;

                    c  ;

                }

                result  = String.valueOf   String.valueOf(report.charAt;

                i = i   count;

            }

            report = result;

            start  ;

        }

        return report;

    }

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

            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;

            sub.stream().forEach(item->item.add;

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

            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;

            sub.stream().forEach(item->item.add;

            result.addAll(sub);

        }

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

        result.stream().forEach(item->sets.add;

        return new ArrayList;

    }

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;

    }

18. Pow

实现 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 return 0;

        if return 1;

        if return 1;

        if return x;

        if return 1/x;

        if(n > 1 || n < -1){

            double nextValue = power;

            return (n % 2 == 0 ? 1 : (n > 0 ? x : 1/x)) * nextValue * nextValue;

        }

        return x;

    }

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;

            if (result > Integer.MAX_VALUE) return 0;

            if (result < Integer.MIN_VALUE) return 0;

            x = x/10;

        }

        return (int) result;

    }

21. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"输出: "bb"

public static String longestPalindrome(String s) {

        if(s == null || s.length() == 1 || s.length return s;

        if(s.length return s.charAt == s.charAt?s:String.valueOf(s.charAt;

        String maxP = "";

        //中间索引

        int middle = (s.length/2;

        //字符串长度奇偶 判别

        boolean dmiddle = s.length()%2 == 0 && s.charAt == s.charAt(middle   1);

        //遍历使用临时中间字符索引

        int tmpMiddle = middle;

        //紧邻元素接次判断

        int initJudge = 1;

        //每次判断中间最长回文字符

        String tp = "";

        //最开始 判断是否偶长度

        boolean first = true;

        //中间字符逐次左移判断

        while (tmpMiddle > 0) {

            initJudge = 1;

            //左右指针

            int lindex = tmpMiddle - 1, rindex = tmpMiddle   (first && dmiddle?2:1);

            while (lindex > -1 && rindex < s.length {

                if(initJudge == 1) {

                    //左边紧邻接次判断

                    if (s.charAt == s.charAt(tmpMiddle)) {

                        lindex--;

                        initJudge  ;

                    }

                    //右边紧邻接次判断

                    if (s.charAt == s.charAt(tmpMiddle   (first && dmiddle?1:0))) {

                        rindex  ;

                        initJudge  ;

                    }

                    initJudge = initJudge>1?1:0;

                    first = false;

                    tp = s.substring(lindex   1, rindex);

                    continue;

                }

                //对称位置判断

                if (s.charAt == s.charAt {

                    lindex--;

                    rindex  ;

                    tp = s.substring(lindex   1, rindex);

                    continue;

                }

                tp = s.substring(lindex   1, rindex);

                break;

            }

            if(tp.length() > maxP.length{

                maxP = tp;

            }

            tmpMiddle--;

        }

        tmpMiddle = middle;

        tp = "";

        first = false;

        //中间字符逐次右移判断

        while (tmpMiddle < s.length {

            initJudge = 1;

            //左右指针

            int lindex = tmpMiddle - 1, rindex = tmpMiddle   (first && dmiddle?2:1);

            while (lindex > -1 && rindex < s.length {

                if(initJudge == 1) {

                    //左边紧邻接次判断

                    if (s.charAt == s.charAt(tmpMiddle)) {

                        lindex--;

                        initJudge  ;

                    }

                    //右边紧邻接次判断

                    if (s.charAt == s.charAt(tmpMiddle   (first && dmiddle?1:0))) {

                        rindex  ;

                        initJudge  ;

                    }

                    initJudge = initJudge>1?1:0;

                    tp = s.substring(lindex   1, rindex);

                    continue;

                }

                //对称位置判断

                if (s.charAt == s.charAt {

                    lindex--;

                    rindex  ;

                    tp = s.substring(lindex   1, rindex);

                    continue;

                }

                tp = s.substring(lindex   1, rindex);

                break;

            }

            if(tp.length() > maxP.length{

                maxP = tp;

            }

            tmpMiddle  ;

        }

        return maxP;

    }

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

            }

        }

    }

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;

    }

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;

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

    }

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 = numP0;

        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 = numP;

        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;

    }

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;

    }

23. 删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

public static ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode first = head;

        //subIndex 第n个元素的索引

        int index = 0, subIndex = 0;

        List<ListNode> list = new ArrayList();

        while (first != null){

            list.add;

            if(index - subIndex > n){

                subIndex  ;

            }

            index  ;

            first = first.next;

        }

        if(list.size return null;

        if(list.size return null;

        if(list.size return list.get;

        //处理移除

        list.get.next = list.get.next.next;

        return list.get;

    }

本文由分分快三计划发布,转载请注明来源

关键词: 答案 算法 每日算法