本文收集了一些LeetCode的一些简单的题目

基础数据类型定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ListNode1 {
    int val;
    ListNode1 next;
    ListNode1() {}
    ListNode1(int val) {
        this.val = val;
    }
    ListNode1(int val, ListNode1 next) {
        this.val = val;
        this.next = next;
    }
}

public class TreeNode1 {
    int val;
    TreeNode1 left;
     TreeNode1 right;
    
     TreeNode1(int x) {
         val = x;
     }
}

和为目标值的两数在数组中的下标

给定一个整数数组 nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例: nums = [2, 7, 11, 15], target = 9。因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int[] problem(int[] nums, int target) {
    int result[] = new int[2];
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                break;
            }
        }
    }
    return result;
}

32位整数反转

给出一个 32位的有符号整数，你需要将这个整数中每位上的数字进行反转。注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为[−231, 231− 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
示例 1: 输入: 123 输出: 321
示例 2: 输入: -123 输出: -321
示例 3: 输入: 120 输出: 21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static int problem(int x) {     
    int len = 0;        // int  溢出问题
    if (x > 0) {        // 1534236469
        len = (x + "").length();
    } else {
        len = (x + "").length() - 1;
    }
    while (x != 0) {
        int temp = x % 10;
        x /= 10;
        target += tempMath.pow(10, len - 1);
        len = len - 1;
    }
    System.out.println((int)Math.pow(2, 31) + " --- " + Math.pow(2, 31));
    return (int) target == target ? int(target) : 0;
}

// 法二
public static int problem(int x) {
    long target = 0;
    while (x != 0) {
        int temp = x % 10;
        x /= 10;
        target = target10 + temp;
    }
    if ((target > Math.pow(2, 31) - 1) || (target < Math.pow(-2, 31))) {
        return 0;
    }
    return ((target > Math.pow(2, 31) - 1) || (target < Math.pow(-2, 31))) ? 0 : (int) target;
}

回文数判断

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1: 输入: 121 输出: true
示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶: 能不将整数转为字符串来解决这个问题吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 利用字符串
public static boolean isPalindrome(int x) {
    boolean flag = true;
    if (x < 0 || (x != 0 && x % 10 == 0)) { // 负数都不是回文数  除0以外的整十数都不是回文数
        return false;
    }
    String src = x + ""; 
    System.out.println(src.length());
    for (int i = 0, j = src.length() - 1; i <= src.length() / 2 && j >= src.length() / 2; i++, j--) {
        System.out.println(src.charAt(i) + "<---->" + src.charAt(j));
        if (src.charAt(i) != src.charAt(j)) {
            return false;
        }
    }
    return flag;
}
// 不使用字符串
public static boolean isPalindrome(int x) {
    boolean flag = true;
    if (x < 0 || (x != 0 && x % 10 == 0)) { // 负数都不是回文数  除0以外的整十数都不是回文数
        return false;
    }
    int count = (x + "").length() / 2, target = 0, isEven = (x + "").length() % 2;
    while (count != 0) {
        int temp = x % 10;
        x /= 10;
        target += (int) tempMath.pow(10, count - 1);
        count = count - 1;
    }
    System.out.println("-->" + target);
    if (isEven == 0 && target != x) {
        return false;
    }
    if (isEven == 1 && target != (x / 10)) {
        return false;
    }
    return flag;
}

罗马数字转整数

罗马数字包含以下七种字符:I，V，X，L，C，D和M。
字符（数值）对应关系：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 的范围内
示例 1: 输入:“III” 输出: 3
示例 2: 输入:“IV” 输出: 4
示例 3: 输入:“IX” 输出: 9
示例 4: 输入:“LVIII” 输出: 58 解释: L = 50, V= 5, III = 3。
示例 5: 输入:“MCMXCIV” 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int problem(String s) {
    int target = 0;
//        char constant[] = {'I','V','X','L','C','D','M'};
    int cons[] = {1, 5, 10, 50, 100, 500, 1000};
    String SRC = "IVXLCDM";
    int i = 0;
    for (; i < s.length() - 1; i++) {
        if ((s.charAt(i) == 'I' && (s.charAt(i + 1) == 'V' || s.charAt(i + 1) == 'X')) ||
                (s.charAt(i) == 'X' && (s.charAt(i + 1) == 'L' || s.charAt(i + 1) == 'C')) ||
                (s.charAt(i) == 'C' && (s.charAt(i + 1) == 'D' || s.charAt(i + 1) == 'M'))) {
            target += cons[SRC.indexOf(s.charAt(i + 1))] - cons[SRC.indexOf(s.charAt(i))];
            i++;
        } else {
            target += cons[SRC.indexOf(s.charAt(i))];
        }
    }
    System.out.println(i);
    if (i == s.length() - 1) {
        target += cons[SRC.indexOf(s.charAt(i))];
    }
    return target;
}

字符串数组的最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 说明: 所有输入只包含小写字母a-z。
如果不存在公共前缀，返回空字符串""。
示例 1: 输入: [“flower”,“flow”,“flight”] 输出: “fl”
示例 2: 输入: [“dog”,“racecar”,“car”] 输出: “” 解释: 输入不存在公共前缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static String problem(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        int len = Math.min(strs[i].length(), prefix.length()); // 比较直到较小长度
        int index = 0;  // 字符比较 下标
        while (index < len && prefix.charAt(index) == strs[i].charAt(index)) {
            index++;
        }
        prefix = prefix.substring(0, index); // 取公共前缀
        if (prefix.length() == 0) { // 前缀已经为空 则退出比较
            break;
        }
    }
    return prefix;
}

有效字符串判定

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，']'的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1: 输入: “()” 输出: true
示例 2: 输入: “()[]{}” 输出: true
示例 3: 输入: “(]” 输出: false
示例 4: 输入: “([)]” 输出: false
示例 5: 输入: “{[]}” 输出: true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static boolean problem(String s) {
    // 空串合法
    if (s == null || s.length() == 0) {
        return true;
    }
    // 第一个字符为右括号 或者 串长为奇数 非法
    if (s.charAt(0) == ')' || s.charAt(0) == ']' || s.charAt(0) == '}' || s.length() % 2 == 1) {
        return false;
    }
    boolean flag = true;
    //左括号进栈  右括号出栈 判断是否合法
    char stack[] = new char[s.length()];
    int top = 0, i = 0;
    while (i < s.length()) {
        if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
            stack[top++] = s.charAt(i);
            i++;
        } else {
            char temp = stack[--top];
            if ((temp == '(' && s.charAt(i) == ')') || (temp == '[' && s.charAt(i) == ']') ||
                        (temp == '{' && s.charAt(i) == '}')) {
                
                i++;
            } else {
                return false;
            }
        }
    }
    if (top != 0) {  // 栈不空 非法
        return false;
    }
    return flag;
}

合并两个升序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过 拼接给定的两个链表的所有节点 组成的。
示例：输入：1->2->4, 1->3->4; 输出：1->1->2->3->4->4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static ListNode1 problem(ListNode1 l1, ListNode1 l2) {
    if (l1 == null && l2 == null) {
        return l1;
    } else if (l1 != null && l2 == null) {
        return l1;
    } else if (l1 == null && l2 != null) {
        return l2;
    }
    ListNode1 p1 = l1, p2 = l2, h;
    if (p1.val < p2.val) {
        h = p1;
        p1 = p1.next;
    } else {
        h = p2;
        p2 = p2.next;
    }
    ListNode1 head = h;
    while (p1 != null && p2 != null) {
        if (p1.val < p2.val) {
            h.next = p1;
            p1 = p1.next;
        } else {
            h.next = p2;
            p2 = p2.next;
        }
        h = h.next;
    }
    while (p1 != null) { // l1剩下的
        h.next = p1;
        p1 = p1.next;
        h = h.next;
    }
    while (p2 != null) { // l2 剩下的
        h.next = p2;
        p2 = p2.next;
        h = h.next;
    }
    return head;
}

排序数组原地去重

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 【原地】修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) { print(nums[i]); }

1
2
3
4
5
6
7
8
9
10
public static int problem(int[] nums) {
    int index = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[index] != nums[i]) {
            index++;
            nums[index] = nums[i];
        }
    }
    return index + 1;
}

原地删除数组中特定值

给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。 你不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) { print(nums[i]); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int problem(int[] nums, int val) {
    int index = nums.length;
    for (int i = 0; i < index; ) {
        if (nums[i] == val) {
            for (int j = i; j < nums.length - 1; j++) {
                nums[j] = nums[j + 1];
            }
            index--;
            i--;
        }
        i++;
    }
    return index;
}

实现strStr()函数

给定一个haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1
说明: 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当needle是空字符串时我们应当返回 0 。这与C语言的strstr()以及 Java的indexOf()定义相符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int problem10(String haystack, String needle) {
    if (needle.length() == 0 || needle.equals("")) {
        return 0;
    }
    if (haystack.length() < needle.length()) {
        return -1;
    }
    int i = 0;
    int diff = haystack.length() - needle.length() + 1;
    for (; i < diff; i++) {
        int j = 0;
        for (; j < needle.length(); j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) { // 不匹配 退出比较
                break;
            }
        }
        if (j == needle.length()) { // 比完 第一次找到匹配的needle  退出
            break;
        }
    }
    if (i == diff) { // 比完 没找到
        return -1;
    }
    return i;
}

在排序数组中找目标值

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
示例 4: 输入: [1,3,5,6], 0 输出: 0

1
2
3
4
5
6
7
8
9
10
11
12
public static int problem(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target || (i == 0 && nums[i] > target)) { // 原数组中找到了  target 或者比第一个还小
            return i;
        }
        if (i < nums.length - 1 && nums[i] < target && nums[i + 1] > target) {  
            // 插在数组的第 2 到第 nums.length-1个位置
            return i + 1;
        }
    }
    return nums.length; // 插到第 nums.length 个位置
}

外观数列

外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1（1）、2（11）、3（21）、4（1211）、5（111221）
1读作"one 1"(“一个一”),即11。11读作"two 1"(“两个一”）,即21。21读作"one 2",“one 1”（“一个二”,“一个一”), 即1211。
给定一个正整数 n（1 ≤n≤ 30），输出外观数列的第 n 项。**注意：**整数序列中的每一项将表示为一个字符串。
示例 1: 输入: 1 输出: “1” 解释：这是一个基本样例。
示例 2: 输入: 4 输出: “1211”
解释：当 n = 3 时，序列是 “21”，其中我们有 “2” 和 “1” 两组，“2” 可以读作 “12”，也就是出现频次 = 1 而 值 = 2；类似 “1” 可以读作 “11”。所以答案是 “12” 和 “11” 组合在一起，也就是 “1211”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static String problem(int n) {
    if (n == 1) {  // 首项
        return "1";
    } else if (n == 2) { // 第二项
        return "11";
    } else { // 推导
        String str = "11";
        for (int i = 3; i <= n; i++) {
            String nextStr = "";
            int count = 1, index = 0, j = 1;
            for (; j < str.length(); j++) {
                if (str.charAt(index) == str.charAt(j)) {
                    count++;
                } else {
                    nextStr = nextStr + count + str.charAt(index);
                    index = j;
                    count = 1;
                }
            }
            if (j == str.length()) { // 比到了最后
                nextStr = nextStr + count + str.charAt(index);
            }
            str = nextStr;
            System.out.println(i + " --->> " + str);
        }
        return str;
    }
}

最大连续数组

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6。解释:连续子数组[4,-1,2,1] 的和最大，为6。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int problem(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int target = nums[0], max = target, index = 1;
    for (int i = 1; i < nums.length; i++) {
        target += nums[i];
        max = max > target ? max : target;
        if (i == nums.length - 1 && index < nums.length) { // 已经最后 回退
            System.out.println(index + " --> " + max);
            i = index++ - 1; // 执行完后 i会加1;
            target = 0;
        }
    }
    return max;
    /*考虑分治的方法*/
}

计算字符串中最后一个单词的长度

给定一个仅包含大小写字母和空格’ '的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。如果不存在最后一个单词，请返回 0。说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。
示例: 输入: “Hello World” 输出: 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int problem14(String s) {
    if (s.length() == 0 || s.equals("")) {
        return 0;
    }
    int len = 0;
    for (int i = s.length() - 1; i >= 0; i--) {// 从后往前看第一个单词的长度
        if (s.charAt(i) != ' ') {
            len++;
        }
        if (len != 0 && s.charAt(i) == ' ') {
            break;
        }
    }
    return len;
}

数组代表一个数字，做加一计算

给定一个由整数组成的 【非空数组】 所表示的 【非负整数】 ，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
示例1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。
示例2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int[] problem(int[] digits) {
    int temp = 0; // 表示进位
    for (int i = digits.length - 1; i >= 0; i--) {
        if (i == digits.length - 1 && (digits[i] + 1 < 10)) { // 最后一位没有进位
            digits[i] += 1;
            return digits;
        } else {
            int pre = digits[i];
            if (i == digits.length - 1) { // 最后一位有进位
                digits[i] = (digits[i] + 1) % 10;
                temp = 1;
            } else {
                digits[i] = (pre + temp) % 10;
                temp = (pre + temp) / 10;
            }
        }
    }
    if (temp != 0) {  // 最后一位数有进位
        int[] re = new int[digits.length + 1];
        re[0] = temp;
        for (int i = 0; i < digits.length; i++) {
            re[i + 1] = digits[i];
        }
        return re;
    }
    return digits;
}

二进制相加

给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 【非空】 字符串且只包含数字1和0。
示例 1: 输入: a = “11”, b = “1” 输出: “100”
示例 2: 输入: a = “1010”, b = “1011” 输出: “10101”
提示：每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。 1 <= a.length, b.length <= 10^4。字符串如果不是 “0” ，就都不含前导零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static String problem(String a, String b) {
    String re = "";
    int i = a.length() - 1, j = b.length() - 1, temp = 0; // temp 是进位
    // char型的数字 转 int：  char - '0'
    while (i >= 0 && j >= 0) {
        re = ((a.charAt(i) - '0') + (b.charAt(j) - '0') + temp) % 2 + re;
        temp = ((a.charAt(i) - '0') + (b.charAt(j) - '0') + temp) / 2;
        i--;
        j--;
    }
    while (i >= 0) {  // a 剩下的
        re = ((a.charAt(i) - '0') + temp) % 2 + re;
        temp = ((a.charAt(i) - '0') + temp) / 2;
        i--;
    }
    while (j >= 0) { // b 剩下的
        re = ((b.charAt(j) - '0') + temp) % 2 + re;
        temp = ((b.charAt(j) - '0') + temp) / 2;
        j--;
    }
    if (temp != 0) { // 最后还有进位
        re = temp + re;
    }
    return re;
}

实现int sqrt(int x)函数

计算并返回x的平方根，其中x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1: 输入: 4 输出: 2
示例 2: 输入: 8 输出: 2。说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 第一种
public static int problem(int x) {
    if (x == 0) {
        return x;
    }
    int ans = (int)Math.exp(0.5 Math.log(x));
    return (long)(ans + 1) (ans + 1) <= x ? ans + 1 : ans;
}
// 第二种 二分查找
public static int problem(int x) {
    if (x == 0) {
        return x;
    }
    int target = -1;
    int i = 0, e = x;
    while (i <= e) {     // 二分查找
        int mid = i + (e - 1) / 2;
        if ((long)mid mid <= x) { // 右边  (long long)mid  mid
            target = mid;
            i = mid + 1;
        }else { // 左边
            e = mid - 1;
        }
    }
    return target;
}
// 第三种 牛顿迭代
public static int problem(int x) {
    if (x == 0) {
        return x;
    }
    int target = -1;
    double C = x, x0 = x;
    while (true) {  // 牛顿迭代   比二分快
        double xi = 0.5 (x0 + C / x0);
        if (Math.abs(x0 - xi) < 1e-7) {
            break;
        }
        x0 = xi;
    }
    target = (int) x0;

    return target;
}

爬楼梯算法

假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。有多少种不同方法可以爬到楼顶？注意：给定 n 是正整数。
示例 1：输入： 2 输出： 2。解释： 有两种方法可以爬到楼顶。（1 阶 + 1 阶）、（2 阶）
示例 2：输入： 3 输出： 3。解释： 有三种方法可以爬到楼顶。（1 阶 + 1 阶 + 1 阶）、（1 阶 + 2 阶）、（2 阶 + 1 阶）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static int problem(int n) {
    int target = 0;
//        target = test_math(n);       // 排列组合
    target = test_dynamicProgram(n); // 滚动数组
    return target;
}

public static int test_math(int n) {
    // 排列组合中的排列  排列： A(n,m)=n×（n-1）...（n-m+1）=n!/（n-m）!(n为下标,m为上标）
    int count1 = n, count2 = 0, target = 0;
    while (true) {
        if (count1 - 2 < 0) {
            break;
        } else if (count1 - 2 == 0) {// 全2
            target += 1;
            break;
        } else {
            count2++; // 2的个数
            count1 = count1 - 2;
            target += combination(count1 + count2, count2);
        }
    }
    return target + 1; // 加一个全 1
}

// 组合   C(n,m) = A(n,m) / m!
public static int combination(int n, int m) {
    int target = 1;
    for (int i = (n - m + 1); i <= n; i++) { // A(n,m)=n*(n-1)...(n-m+1)=n! / (n-m)!
        target *= i;
    }
    for (int i = m; i >= 1; i--) { // C(n,m) = A(n,m) / m!
        target /= i;
    }
    return target;
}

**动态规划的转移方程：**用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，故可列出如下式子：f(x) = f(x−1) + f(x−2)。它意味着爬到第 x级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。因为每次只能爬 11 级或 22 级，所以 f(x)只能从 f(x−1) 和 f(x−2) 转移过来，要统计方案总数，就需要对这两项的贡献求和。
**边界条件：**从第 0 级开始爬，从第 0 级爬到第 0 级可以看作只有一种方案，即 f(0)=1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。
不妨写几项来验证一下，根据转移方程得到 f(2)=2，f(3)=3，f(4)=5…把这些情况都枚举出来，发现计算的结果是正确的。
不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现，但由于这里的 f(x) 只和 f(x−1) 与 f(x−2) 有关，所以可以用「滚动数组思想」把空间复杂度优化成 O(1)

1
2
3
4
5
6
7
8
9
10
// 滚动数组
public static int test_dynamicProgram(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}

排序链表去重

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例1: 输入: 1->1->2 输出: 1->2
示例2: 输入: 1->1->2->3->3 输出: 1->2->3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static ListNode1 problem(ListNode1 head) {
    if (head == null) {
        return head;
    }
    ListNode1 p = head.next, pre = head;
    while (p != null) {
        if (p.val == pre.val) {
            pre.next = p.next;
        }else{
            pre = pre.next;
        }
        p = p.next;
    }
    return head;
}

合并两无序数组为一个有序数组

给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。
说明：初始化nums1 和 nums2 元素数量分别为m 和 n 。设nums1有足够的空间（空间大小大于或等于m + n）保存 nums2 中元素。
示例：输入: nums1 = [1,2,3,0,0,0], m = 3；nums2 = [2,5,6], n = 3。输出:[1,2,2,3,5,6]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void problem(int[] num1, int m, int[] num2, int n){
    int i = 0, j = 0;
    while(i < m + j && j < n){
        if(num1[i] > num2[j]){
            for(int k = m + j; k >= i; k--){ // 第i+1个元素到第m+j个元素依次后移
                if(k == i){
                    num1[i] = num2[j]; // 插入元素
                }else {
                    num1[k] = num1[k - 1];
                }
            }
            j++;
        }
        i++;
    }
    while(j < n){  // num2 还有剩
        num1[i++] = num2[j++];
    }
}

判断两个二叉树是否相同

给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

image-20250622221035975

1
2
3
4
5
6
7
8
9
10
11
12
13
public static boolean problem(TreeNode1 p, TreeNode1 q){
    return isSameTree(p, q);
}

public static boolean isSameTree(TreeNode1 p, TreeNode1 q){
    if(p == null && q == null) // 两棵树同时为 null 则相同
        return true;
    if(p == null || q == null) // 其中一棵树为 null 则不同
        return false;
    if(p.val != q.val) // 根节点不同 则不同
        return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 左子树 右子树都相同
}