力扣刷题

码云地址

简单难度

[1] 两数之和

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

每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

nums = [2, 7, 11, 15]

target = 9

返回 [0, 1]

解法一：

枚举 一个数x，再通过遍历剩下数组来寻找 target-x

• 第一个循环中，i 从 0 开始，到 n-2 结束
• 第二次循环中，i 从 i+1 开始，到 n-1 结束

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

解法二：

使用 HashMap，将 nums[i]作为键，i作为值。

好处是：可以使用 map.containsKey方法判断 target-value 是否在已有的 map中存在

• 注意：在添加数据时，应先进行判断。好处是：可以避免出现 自己+自己 = target的情况

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

[7] 整数反转

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

输入: 123

输出: 321

输入: -123

输出: -321

输入: 120

输出: 21

注意:

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

解法一：

将数字中的每一位都单独取出来放到集合中，然后再对每一位数字进行拼接，拼成反转后的数字。

此时需要注意：拼接的时候判断数字是否会超出 int数的上限，因此需要在拼之前判断。

class Solution {
    public int reverse(int x) {
        if (x == Integer.MAX_VALUE || x == Integer.MIN_VALUE) return 0;
        boolean flag = x > 0 ? true : false;
        LinkedList<Integer> list = new LinkedList<>();
        x = Math.abs(x);
        while (x / 10 > 0) {
            list.add(x % 10);
            x = x / 10;
        }
        list.add(x);

        int answer = 0;
        // System.out.println(list);
        while (!list.isEmpty()) {
            int pop = list.pop();

            // System.out.println(pop);

            if (answer > (Integer.MAX_VALUE / 10)) {
                return 0;
            } else if (answer == (Integer.MAX_VALUE / 10) && pop > 7) {
                return 0;
            }

            answer = (answer * 10) + pop;

        }

//        return answer;
        return flag == true ? answer : -answer;
    }
}

解法二：

边获取每个位置的数，边拼接，只需要一次循环即可

class Solution {
    public int reverse(int x) {
        // 定义反转后的数的值
        int rev = 0;
        while (x != 0) {
            // 削下来一位数
            int pop = x % 10;
            // 改变原数
            x /= 10;
            // 判断拼接否是否会溢出
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            // 数字拼接
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

中等难度

[2] 两数相加

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

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

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

解法一：

使用 BigInteger的运算，先从链表中获取数据，然后进行计算，最后再生成一个新链表。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder n1 = new StringBuilder();
        StringBuilder n2 = new StringBuilder();
        ListNode p = l1, q = l2;

        while (p != null) {
            n1.append(p.val + "");
            p = p.next;

        }
        n1 = n1.reverse();

        while (q != null) {
            n2.append(q.val + "");
            q = q.next;

        }
        n2 = n2.reverse();

        BigInteger m1 = new BigInteger(n1.toString());
        BigInteger m2 = new BigInteger(n2.toString());

        BigInteger val = m1.add(m2);

        char[] vals = val.toString().toCharArray();
        int len = vals.length;
        ListNode l3 = new ListNode(Integer.parseInt(String.valueOf(vals[len - 1])));
        for (int k = 0; k < len - 1; k++) {
            ListNode m = new ListNode(Integer.parseInt(String.valueOf(vals[k])));
            m.next = l3.next;
            l3.next = m;
        }

        return l3;

    }
}

解法二：

针对每个位次进行求和，并与当前位置的进位值相加。

如果两个链表长度不同，短的那部分就用 0 来替换

在遍历结束后，判断最后有没有进位，如果有，就再加一个结点

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

[3] 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

输入: s = "abcabcbb"

输出: 3 // abc

输入: s = "bbbbb"

输出: 1 // b

输入: s = "pwwkew"

输出: 3 // wke

输入: s = ""

输出: 0

思想：

• 针对子串问题，采用滑动窗体法
  • 设置左右指针，分别执向子串的首尾
  • 以指针的滑动表示子串的取值
  • 设立集合记录子串的值

解法一

采用HashMap存储每个子串中的字符，键为字符，值为出现的位置

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) return 0;

        int len = s.length();
        int left = 0, right = 0, max = 0;
		// HashMap记录每个字符和下标
        HashMap<Character, Integer> map = new HashMap<>();

        // 快指针右移
        for (; right < len; right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                // 慢指针右移
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            max = Math.max(max, right - left + 1);

        }
        return max;

    }
}

解法二：

采用HashSet存储单个字符

• 首次出现的字符添加
• 已有字符出现时，删除最早的字符

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

[5] 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad"

输出："bab"

输入：s = "cbbd"

输出："bb"

输入：s = "a"

输出："a"

输入：s = "ac"

输出："a"

解法一

暴力枚举

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();

        // 枚举所有长度大于1的子串
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    private boolean validPalindromic(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

解法二：

中心扩散法

• 枚举所有可能的回文子串的中心位置
• 中心位置可能是一个字符也可能是两个
• 记录最长回文子串的相关变量

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";

        int len = s.length();

        int maxLen = 1;
        int begin = 0;

        char[] charArray = s.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            // 将位置传过去，作为回文子串的中心，并获取长度
            int oddLen = expandAroundCenter(charArray, i, i);
            int evenLen = expandAroundCenter(charArray, i, i + 1);

            int curMax = Math.max(oddLen, evenLen);

            if (curMax > maxLen) {
                maxLen = curMax;
                begin = i - (maxLen - 1) / 2;
            }
        }
        return s.substring(begin, begin + maxLen);
    }


    private int expandAroundCenter(char[] arr, int i, int j) {
        while (i >= 0 && j < arr.length) {
            if (arr[i] != arr[j])
                break;
            i--;
            j++;
        }
        // 跳出循环后，i和j分别在满足条件的子串的左和右边，所以 要 -1
        return j - i - 1;
    }
}

解法三：

动态规划

• 如果一个字符串是回文串，那么它去掉左右两端字符后依旧是回文串
  • 状态：dp[i][j] 表示子串 s[i..j]是否为回文子串
  • 得到状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
  • 边界条件：j - 1 - (i + 1) +1 < 2，整理得：j - i < 3
  • 初始化：dp[i][i] = true，对角线上元素，即长度为1的子串一定是满足条件的
  • 输出：在得到一个状态的值为 true 的时候，记录起始位置和长度，填表完成以后再截取

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";

        int len = s.length();

        int maxLen = 1;
        int begin = 0;

        // dp[i][j]表示 s[i..j]是否为回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }


        char[] charArray = s.toCharArray();
        // 注意左下角先填
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

解法4：

Manacher算法

专门用于查找最长回文子串的算法，复杂度为O(n)

• 相对复杂，绝大多数面试和笔试不做要求
• 将原始字符串进行预处理，在预处理之后的字符串上执行 动态规划 和 中心扩散 方法
• 为了将奇偶数回文串统一表示，将原始字符串进行预处理，用不在输入字符串中的字符隔开

力扣刷题

原文：https://www.cnblogs.com/zhaochuming/p/14355998.html