一些算法题及答案

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

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;

    }

示例 2:

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;

    }

示例 1:

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

 

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;

    }

最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。

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;

    }
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

class Solution:
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        last = len(digits) - 1
        for i in range(len(digits)):
            if digits[last] == 9:
                digits[last] = 0
                last -= 1
            else :
                digits[last] = digits[last]+1
                break
        if max(digits) == 0:
            digits.insert(0,1)
        return digits

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

    }

你可以假设除了整数 0 之外,这个整数不会以零开头。

22. 电话号码的字母组合

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

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

图片 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<>;

    }

给定一个非负整数组成的非空数组,在该数的基础上加一,返回一个新的数组。

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;

    }

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;

    }

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;

    }

待续 。。。 。。。

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

    }

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;

    }

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;

    }

相关文章