java代码（LC链表和其他一些题）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

java代码（LC链表和其他一些题）

作者：

初静 , 2021-10-05 16:38:49 , 所有人可见 , 阅读 252

快排

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] a = new int[n];1
        for (int i = 0; i < n; i ++) a[i] = sc.nextInt();

        quickSort(a, 0, n - 1);

        for (int i = 0; i < n; i ++) System.out.print(a[i] + " ");
    }

    public static void quickSort(int[] a, int l, int r) {
        if (l >= r) return ;
        int i = l - 1, j = r + 1;
        int x = a[l + r >> 1];

        while (i < j) {
            do i ++; while (a[i] < x);
            do j --; while (a[j] > x);

            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        quickSort(a, l, j);
        quickSort(a, j + 1, r);
    }
}

归并

import java.util.Scanner;

public class Main {
    static int[] tmp = new int[100010];
    public static void merge_sort(int[] q, int l, int r) {
        if (l >= r) return ;
        int mid = l + r >> 1;
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);

        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) tmp[k ++] = q[i ++];
            else tmp[k ++] = q[j ++];
        }

        while (i <= mid) tmp[k ++] = q[i ++];
        while (j <= r) tmp[k ++] = q[j ++];
        for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
    }


    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] q = new int[n];

        for (int i = 0; i < n; i ++) q[i] = scan.nextInt();
        merge_sort(q, 0, n - 1);
        for (int i = 0; i < n; i ++) System.out.print(q[i] + " ");
    }
}

LC1. 两数之和

import java.util.*;
/*
4
2 7 11 15
9
[0,1]
*/

public class Main {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap();

        for(int i = 0;i < nums.length;i ++)
        {
            int other = target - nums[i];
            if(map.containsKey(other)) return new int[]{map.get(other), i};

            map.put(nums[i],i);
        }

        return new int[]{-1,-1};
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i ++) {
            arr[i] = scan.nextInt();
        }

        int target = scan.nextInt();

        int[] res = twoSum(arr, target);

        System.out.print("[");

        for (int i = 0; i < res.length - 1; i ++)
            System.out.print(res[i] + ",");

        System.out.print(res[res.length - 1]);
        System.out.print("]");
    }

}

LC78. 子集

import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static List<Integer> t = new ArrayList<Integer>();
    static List<List<Integer>> ans = new ArrayList<>();

    public static void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<>(t));
            return ;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);

        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }

    public static void main(String[] args) {
        int nums[] = {1, 2, 3};
        dfs(0, nums);

        for (List<Integer>re : ans) {
            System.out.println(re);
        }
    }
}

AcWing 789. 数的范围

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] q = new int[n];

        for (int i = 0; i < n; i ++) q[i] = scan.nextInt();
        while (m -- > 0) {
            int x = scan.nextInt();

            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (q[mid] >= x) r = mid;
                else l = mid + 1;
            }

            if (q[r] != x) System.out.println("-1 -1");
            else {
                System.out.print(l + " ");

                l = 0; r = n - 1; //在java两条赋值写在一行必须中间用; 隔开
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    if (q[mid] <= x) l = mid;
                    else r = mid - 1;
                }

                System.out.println(r);
            }
        }
    }
}

AcWing 795. 前缀和

import java.util.Scanner;

public class Main {
    static int[] sum = new int[100010];

    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        int n =scan.nextInt();
        int m = scan.nextInt();


        for (int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + scan.nextInt();

        while (m -- > 0) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            System.out.println(sum[r] - sum[l - 1]);
        }
        scan.close();
    }

}

AcWing 799. 最长连续不重复子序列

import java.util.Scanner;

public class Main {
    static int[] s = new int[100010];
    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] num = new int[n];

        for (int i = 0; i < n; i ++) num[i] = scan.nextInt();
        int res = 0;
        for (int i = 0, j = 0; i < n; i ++) {
            s[num[i]] ++;
            while (j < i && s[num[i]] > 1) s[num[j ++]] --;

            res = Math.max(res, i - j + 1);
        }
        System.out.println(res);
    }
}

AcWing 800. 数组元素的目标和

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int m = scan.nextInt();
        int x = scan.nextInt();

        int[] A = new int[n];
        int[] B = new int[m];

        for (int i = 0; i < n; i ++) A[i] = scan.nextInt();
        for (int j = 0; j < m; j ++) B[j] = scan.nextInt();

        for (int i = 0, j = m - 1; i < n; i ++) {
            while (j > 0 && A[i] + B[j] > x) j --;
            if (A[i] + B[j] == x) System.out.println(i + " " + j);
        }
    }
}

AcWing 801. 二进制中1的个数

import java.util.*;

public class Main {
    public static int lowbit(int n) {
        return n & -n;
    }


    public static int findOne (int n) {
        int count = 0;
        while (n > 0) {
            n -= lowbit(n);
            count ++;
        }
        return count;
    }


    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for (int i = 0; i < n; i ++) System.out.print(findOne(scan.nextInt()) + " ");
    }
}

AC88. 树中两个结点的最低公共祖先

C++ 完整代码

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return NULL;
    if (root == p || root == q) return root;
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    if (left) return left;
    return right;
}

int main () {
    TreeNode* A = new TreeNode('A');
    TreeNode* B = new TreeNode('B');
    TreeNode* C = new TreeNode('C');
    TreeNode* D = new TreeNode('D');
    TreeNode* E = new TreeNode('E');
    TreeNode* F = new TreeNode('F');
    TreeNode* K = new TreeNode('K');

    A->left = B;
    A->right = C;
    B->left = E, B->right = D;
    C->left = F;
    F->right = K;

    TreeNode* p = E;
    TreeNode* q = D;

    TreeNode* res = lowestCommonAncestor(A, p, q);
    cout << res->val << endl; // B

    return 0;
}

java 完整代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode('6');
        TreeNode node1 = new TreeNode('2');
        TreeNode node2 = new TreeNode('8');
        TreeNode node3 = new TreeNode('0');
        TreeNode node4 = new TreeNode('4');
        TreeNode node5 = new TreeNode('7');
        TreeNode node6 = new TreeNode('9');
        TreeNode node7 = new TreeNode('3');
        TreeNode node8 = new TreeNode('5');

        root.left = node1; root.right = node2;
        node1.left = node3; node1.right = node4;
        node2.left = node5; node2.right = node6;
        node4.left = node7; node4.right = node8;

        TreeNode res=lowestCommonAncestor(root, node3, node8);
        char resval=(char) res.val;
        System.out.println(resval); // 2
    }   

    public static  TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }

    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(char val) {
            this.val = val;
        }

        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC1. 两数之和

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum(nums, target))); //输出 [0, 1]
    }

    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i ++) {
            int other = target - nums[i];
            if (map.containsKey(other)) return new int[]{map.get(other), i};

            map.put(nums[i], i);
        }

        return new int[]{-1, -1};
    }

}

LC9. 整数反转

算法1：使用long 记录

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int x = -123;

        System.out.println(reverse(x));
    }

    public static int reverse(int x) {  
        long res = 0;
        while (x != 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }

        if (res > Integer.MAX_VALUE) return 0;
        if (res < Integer.MIN_VALUE) return 0;

        return (int) res;
    }

}

算法2：使用int 记录

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int x = -123;

        System.out.println(reverse(x));
    }

    public static int reverse(int x) {  
        int res = 0;
        while (x != 0) {
            if (res > 0 && res > (Integer.MAX_VALUE - x % 10) / 10) return 0;
            if (res < 0 && res < (Integer.MIN_VALUE - x % 10) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }

        return res;
    }

}

LC9. 回文数

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int x = 121;

        System.out.println(isPalindrome(x)); //true
    }

    public static boolean isPalindrome(int x) {  
       if (x < 0) return false;
       long res = 0, y = x;
       while (x != 0) {
           res = res * 10 + x % 10;
           x /= 10;
       }

       return res == y;
    }

}

LC13. 罗马数字转整数

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String x = "MCMXCIV";
        System.out.println(romanToInt(x));
    }

    static String[] temp = new String[]{"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
    static int[] a = new int[]{1,4,5,9,10,40,50,90,100,400,500,900,1000};

    public static int romanToInt(String s) {  
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= 12; i ++) {
            map.put(temp[i], a[i]);
        }

        int ans = 0;
        for (int i = 0; i < s.length(); ) {
            if (i + 1 < s.length() && map.containsKey(s.substring(i, i + 2))) {
                ans += map.get(s.substring(i, i + 2));
                i += 2;
            } else {
                ans += map.get(s.substring(i, i + 1));
                i += 1;
            }
        }

        return ans;
    }

}

LC14. 最长公共前缀

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String[] strs = {"flower", "flxx", "flight"};
        // String[] strs = {"dog","racecar","car"};
        System.out.println(longestCommonPrefix(strs)); // 输出fl
    }

    public static String longestCommonPrefix(String[] strs) {  
        if (strs.length == 0) return "";

        String s = strs[0];
        int size = s.length();

        int j = 0;
        for (int i = 0; i < strs.length; i ++) {
            for (j = 0; j < size; j ++) 
                if (s.charAt(j) != strs[i].charAt(j)) {
                    size = j;
                    break;
                }
        }

        return s.substring(0, j);
    }

}

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

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->4->8
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3,
                new ListNode(4, new ListNode(5)))));
        int k = 2;

        printNode(head);
        System.out.println(); //1 2 3 4 5 

        ListNode node = removeNthFromEnd(head, k);

        printNode(node);
        System.out.println(); //1 2 3 5 
    }

   public static ListNode removeNthFromEnd(ListNode head, int k) {
        int n = 0;
        for (ListNode p = head; p != null; p = p.next) n ++;

        if (k == n) return  head.next;

        ListNode a = head;
        for (int i = 0; i < n - k - 1; i ++) a = a.next;

        a.next=  a.next.next;
        return head;

    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC20. 有效的括号

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String s = "{[]}";
        System.out.println(isValid(s)); // 输出true
    }


   /*// 第一种写法(常规写法)
    public static boolean isValid(String s) {  
        Stack<Character> stk = new Stack<Character>();
        for (int i = 0; i < s.length(); i ++) {
            char t = s.charAt(i);
            if (t == '(' || t == '[' || t == '{') stk.push(t);
            else {
                if (stk.isEmpty()) return false;
                else if (t == ')' && stk.peek() == '(') stk.pop();
                else if (t == ']' && stk.peek() == '[') stk.pop();
                else if (t == '}' && stk.peek() == '{') stk.pop();
                else return false;
            }
        }

        return stk.isEmpty();
    }*/

    // 第二种写法（任意一对匹配的括号，他们的ASCII值相差<=2，所以可用此条件判断是否是一对括号）
     public static boolean isValid(String s) {  
        Stack<Character> stk = new Stack<Character>();
        for (int i = 0; i < s.length(); i ++) {
            char t = s.charAt(i);
            if (t == '(' || t == '[' || t == '{') stk.push(t);
            else {
                if (!stk.isEmpty() && Math.abs(stk.peek() - t) <= 2) stk.pop();
                else return false;
            }
        }
        return stk.isEmpty();
     }

}

LC21. 合并两个有序链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
//        输入：l1 = [1,2,4], l2 = [1,3,4]
//        输出：[1,1,2,3,4,4]
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode listNode = mergeTwoLists(l1, l2);

        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }


    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail = tail.next = l1;
                l1 = l1.next;
            }
            else {
                tail = tail.next = l2;
                l2 = l2.next;
            }
        }

        if (l1 != null) tail.next = l1;
        if (l2 != null) tail.next = l2;

        return dummy.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

LC26. 删除有序数组中的重复项

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}; //输出5
        //  int[] nums =  {0,0,1,1,1,2,2,3,3,4}; // 5
        //  int[] nums =  {0, 1, 1, 1, 2, 3, 4, 5, 6, 9, 10}; // 9
        System.out.println(removeDuplicates(nums));
    }

    public static int removeDuplicates(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i ++) 
            if (i == 0 || nums[i] != nums[i - 1]) 
                nums[k ++] = nums[i];

        return k;
    }

}

LC27. 移除元素

import java.util.*;

public class Main {
    public static void main (String[] args) {
// 输入：nums = [0,1,2,2,3,0,4,2], val = 2
// 输出：5, nums = [0,1,4,0,3]
        int[] nums = {0,1,2,2,3,0,4,2};  // 5
        int val = 2;

        // int[] nums = {0, 1, 2, 2, 3, 0, 4, 2};   //7
        // int val = 3;
        System.out.println(removeElement(nums, val));
    }

    public static int removeElement(int[] nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.length; i ++) 
            if (nums[i] != val) nums[k ++] =  nums[i];
        return k;
    }

}

LC23. 合并K个排序链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->4->5
        ListNode head1 = new ListNode(1, new ListNode(4, new ListNode(5)));

        // 链表输入 1->3->4
        ListNode head2 = new ListNode(1, new ListNode(3, new ListNode(4)));

        // 链表输入 2->6
        ListNode head3 = new ListNode(2, new ListNode(6));

        /*      
        List<ListNode> lists = new ArrayList<>();
        lists.add(head1);
        lists.add(head2);
        lists.add(head3);
        */

        ListNode[] lists = new ListNode[]{head1, head2, head3};
        // ListNode[] lists = {head1, head2, head3}; 上面的简化写法
        // int[] nums = new int[] {1, 2, 3};

/*        ListNode[] lists = new ListNode[3];
        lists[0] = head1;
        lists[1] = head2;
        lists[2] = head3;*/

        ListNode node = mergeKLists(lists);

        printNode(node);
        System.out.println(); 
    }

    // 这里只能给出Java的一种方法（使用小根堆）
    public static ListNode mergeKLists(ListNode[] lists) {
        // PriorityQueue<ListNode> q = new PriorityQueue<ListNode>((x, y) -> (x.val - y.val));
        PriorityQueue<ListNode> q=new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            public int compare(ListNode o1,ListNode o2) {
                return o1.val-o2.val;
            }
        });

        for(int i = 0; i < lists.length; i ++)
            if(lists[i] != null) 
                q.add(lists[i]);

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while(!q.isEmpty())
        {
            ListNode t = q.poll();
            cur.next = new ListNode(t.val);
            //更新cur
            cur = cur.next;
            //将下一个位置放进堆中
            if(t.next != null) q.add(t.next);
        }
        return dummy.next;

    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC24. 两两交换链表中的节点

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->4
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
        printNode(head);
        System.out.println(); 

        ListNode node = swapPairs(head);

        printNode(node);
        System.out.println();  //2 1 4 3
    }

    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        for (ListNode p = dummy; p.next != null && p.next.next != null; ) {
            ListNode a = p.next;
            ListNode b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }

        return dummy.next;

    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC25. K 个一组翻转链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->4->5
        ListNode head = new ListNode(1, new ListNode(2,
                new ListNode(3, new ListNode(4, new ListNode(5)))));
        int k = 2;

        printNode(head);
        System.out.println(); 

        ListNode node = reverseKGroup(head, k);

        printNode(node);
        System.out.println();  //2 1 4 3 5 
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        for (ListNode p = dummy; ; ) {
            ListNode q = p;
            for (int i = 0; i < k && q != null; i ++) q = q.next;
            if (q == null) break;

            ListNode a = p.next, b = a.next;
            for (int i = 0; i < k - 1; i ++) {
                ListNode c = b.next;
                b.next = a;
                a = b; b = c;
            }

            ListNode c = p.next;
            p.next = a; c.next = b;
            p = c;
        }

        return dummy.next;

    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC61. 旋转链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->4->5
        ListNode head = new ListNode(1, new ListNode(2, 
                new ListNode(3, new ListNode(4, new ListNode(5)))));
        int k = 2;

        printNode(head);
        System.out.println(); 

        ListNode node = rotateRight(head, k);

        printNode(node);
        System.out.println();  //4 5 1 2 3 
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null) return head;
        int n = 0;
        ListNode tail = null;
        for (ListNode p = head; p != null; p = p.next) {
            tail = p;
            n ++;
        }

        k %= n;
        if (k == 0) return head;
        ListNode p = head;
        for (int i = 0; i < n - k - 1; i ++) p = p.next;
        tail.next = head;
        head = p.next;
        p.next = null;
        return head;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC82. 删除排序链表中的重复元素 II

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->3->4->4->5
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, 
                    new ListNode(3, new ListNode(4, new ListNode(4, new ListNode(5)))))));

        printNode(head);
        System.out.println(); 

        ListNode node = deleteDuplication(head);

        printNode(node);
        System.out.println();  //1 2 5 
    }

    public static ListNode deleteDuplication(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;

        while (p.next != null) {
            ListNode q = p.next;
            while (q != null && p.next.val == q.val) q = q.next;
            if (p.next.next == q) p = p.next;
            else p.next = q;
        }

        return dummy.next;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC83. 删除排序链表中的重复元素

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->1->2->3->3
        ListNode head = new ListNode(1, new ListNode(1, new ListNode(2, 
                    new ListNode(3, new ListNode(3)))));

        printNode(head);
        System.out.println(); 

        ListNode node = deleteDuplicates(head);

        printNode(node);
        System.out.println();  //1 2 3
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode cur = head;
        for (ListNode p = head.next; p != null; p = p.next) 
            if (p.val != cur.val)
                cur = cur.next = p;
        cur.next = null;
        return head;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC86. 分隔链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->4->3->2->5->2
        ListNode head = new ListNode(1, new ListNode(4, 
                new ListNode(3, new ListNode(2, new ListNode(5, new ListNode(2))))));

        printNode(head);
        System.out.println(); 

        int x = 3;
        ListNode node = partition(head, x);

        printNode(node);
        System.out.println();  //1 2 2 4 3 5 
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode before = new ListNode(0);
        ListNode after = new ListNode(0);
        ListNode pb = before, pa = after;
        for (ListNode p = head; p != null; p = p.next) 
            if (p.val < x) {
                pb.next = p;
                pb = p;
            }
            else {
                pa.next = p;
                pa = p;
            }
        pb.next = after.next;
        pa.next = null;

        return before.next;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC92. 反转链表 II

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->4->5
        ListNode head = new ListNode(1, new ListNode(2, 
                new ListNode(3, new ListNode(4, new ListNode(5)))));

        printNode(head);
        System.out.println(); 

        int left = 2, right = 4;
        ListNode node = reverseBetween(head, left, right);

        printNode(node);
        System.out.println();  //1 4 3 2 5 
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode a = dummy;
        for (int i = 0; i < left - 1; i ++) a = a.next;
        ListNode b = a.next, c = b.next;
        for (int i = 0; i < right - left; i ++) {
            ListNode d = c.next;
            c.next = b;
            b = c;
            c = d;
        }

        a.next.next = c;
        a.next = b;
        return dummy.next;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC28. 实现strStr()

调函数

直接枚举所有位置，调用substring函数

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // String s = "hello";
        // String p = "ll";
        // System.out.println(strStr(s, p)); //2

        String s = "aaaaa";
        String p = "bba";
        System.out.println(strStr(s, p)); //-1
    }

    public static int strStr(String s, String p) {
        if (p.length() < 1) return 0;
        int n = s.length();
        int m = p.length();
        for (int i = 0; i < n - m + 1; i ++) {
            if (s.substring(i, i + m).equals(p))
                return i;
        }

        return -1;
    }

}

LC35. 搜索插入位置

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 5;
        System.out.println(searchInsert(nums, target)); //2
    }

    public static int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return l;
    }

}

LC53. 最大子序和


import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        int last = 0;
        for (int i = 0; i < nums.length; i ++) {
            last = nums[i] + Math.max(last, 0);
            res = Math.max(res, last);
        }
        return res;
    }
}

LC66. 加一

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // int[] nums = {9, 9, 9, 9};
         int[] nums = {4, 3, 2, 1};

        String res = Arrays.toString(plusOne(nums));
        //输出前把int[]转成字符串Arrays.toString(int[])，然后直接输出

        System.out.println(res); //[4, 3, 2, 2]
    }

    public static int[] plusOne(int[] digits) {
        int n = digits.length;
        List<Integer> A = new ArrayList<Integer>();
        for (int i = n - 1; i >= 0; i --) A.add(digits[i]);

        int t = 1; 
        for (int i = 0; i < A.size(); i ++) {
            t += A.get(i);
            A.set(i, t % 10); //这里用的是ArrayList的set()的API
            t /= 10;
        }

        if (t != 0) A.add(t);

        //这里是反转并把ArrayList<Integer>转换成int[]
        int[] ans = new int[A.size()]; 
        for (int i = 0; i < A.size(); i ++) {
            ans[i] = A.get(A.size() - i - 1);
        }

        return ans;
    }


}

67. 二进制求和

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String a = "1010";
        String b = "1011";

        String res = addBinary(a, b);
        System.out.println(res);  // 10101
    }

    public static String addBinary(String a, String b) {
        StringBuffer sa = new StringBuffer(a);
        StringBuffer sb = new StringBuffer(b);

        sa = sa.reverse();
        sb = sb.reverse();

        StringBuffer sc = new StringBuffer("");
        int t = 0;
        for (int i = 0; i < sa.length() || i < sb.length(); i ++) {
            if (i < sa.length()) t += sa.charAt(i) - '0';
            if (i < sb.length()) t += sb.charAt(i) - '0';
            sc.append(t % 2);
            t /= 2;
        } 

        if(t != 0) sc.append(t);

        return sc.reverse().toString();
    }


}

69. x的平方根

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int x = 8;
        System.out.println(mySqrt(x));
    }

    public static int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = (int)(l + r + 1L >> 1);
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }

}

LC70. 爬楼梯

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int x = 3;
        System.out.println(climbStairs(x)); // 3
    }

    public static int climbStairs(int n) {
        int[] f = new int[n + 10];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= n; i ++) 
            f[i] = f[i - 1] + f[ i - 2];

        return f[n];

    }

}

LC83. 删除排序链表中的重复元素

import java.util.*;

public class Main {
    public static void main (String[] args) {
        /*
            这里建单链表用的是头插法，可以先写node5也可以先写node1
        */
        ListNode node5 = new ListNode(3); 
        ListNode node4 = new ListNode(3, node5);
        ListNode node3 = new ListNode(2, node4);
        ListNode node2 = new ListNode(1, node3);
        ListNode node1 = new ListNode(1, node2);

        printNode(node1);
        System.out.println(); // 1 1 2 3 3 

        ListNode node = deleteDuplicates(node1);

        printNode(node);
        System.out.println();  //1 2 3 
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head; // Java不可写成 if(!head)
        ListNode cur = head; 
        for (ListNode p = head.next; p != null; p = p.next) { //Java不可以把 p!=null 写成p
            if (p.val != cur.val)
                cur = cur.next = p;
        }

        cur.next = null;
        return head;

    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC138. 复制带随机指针的链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        ListNode head = new ListNode(7);
        ListNode node2 = new ListNode(13, 0);
        ListNode node3 = new ListNode(11, 4);
        ListNode node4 = new ListNode(10, 2);
        ListNode node5 = new ListNode(1, 0);

        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        head.random = null;
        node2.random = head;
        node3.random = node5;
        node4.random = node3;
        node4.random = head;

        printNode(head);
        System.out.println(); 

        ListNode node = copyRandomList(head);

        printNode(node);
        System.out.println();  //1 4 3 2 5 
    }

/*
    // 第一种做法：简单直观    
    static HashMap<ListNode, ListNode> map = new HashMap();

    public static ListNode copyRandomList (ListNode head) {
        //将点存入到哈希表中
        ListNode p = head;
        while(p != null)
        {
            map.put(p, new ListNode(p.val));
            p = p.next;
        }
        //存边
        for(Map.Entry<ListNode, ListNode> entry : map.entrySet())
        {
            ListNode a = entry.getKey();
            ListNode b = entry.getValue();

            b.next = map.get(a.next);
            b.random = map.get(a.random);
        }

        return map.get(head);
    }*/

    // 第二种做法：巧妙
    public static ListNode copyRandomList (ListNode head) {
        for (ListNode p = head; p != null; ) { //在每个点后面添加一个他的复制
            ListNode np = new ListNode(p.val);
            ListNode next = p.next;
            p.next = np;
            np.next = next;
            p = next;
        }
        //复制random指针
        for (ListNode p = head; p != null; p = p.next.next) {
            if (p.random != null) p.next.random = p.random.next;
        }
        // 分离两个链表
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for (ListNode p = head; p != null; p = p.next) {
            cur.next = p.next;
            cur = cur.next;
            p.next = p.next.next;
        }

        return dummy.next;

    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/


    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;
        ListNode random;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        ListNode(int val, int x) {
            this.val = val;
            if (this.random != null) this.random.val = x;
        }

        ListNode(int val, ListNode next, ListNode random) {
            this.val = val;
            this.next = next;
            this.random = random;
        }
    }

}

LC142. 环形链表 II

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->4
        ListNode head = new ListNode(3);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(0);
        ListNode head4 = new ListNode(-4);

        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head2;

        ListNode node = detectCycle(head);

        System.out.println(node.val); // 2

    }

    public static ListNode detectCycle (ListNode head) {
       if (head == null || head.next == null) return null;
       ListNode i = head, j = head;
       while (i != null && j != null) {
           i = i.next;
           j = j.next;
           if (j != null) j = j.next;
           if (i == j) {
               i = head;
               while (i != j) {
                   i = i.next;
                   j = j.next;
               }
               return i;
           }
       }

       return null;
    }


    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;
        ListNode random;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        ListNode(int val, int x) {
            this.val = val;
            if (this.random != null) this.random.val = x;
        }

        ListNode(int val, ListNode next, ListNode random) {
            this.val = val;
            this.next = next;
            this.random = random;
        }
    }

}

LC143. 重排链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->4->5
        ListNode head = new ListNode(1, new ListNode(2, 
                new ListNode(3, new ListNode(4, new ListNode(5)))));

        printNode(head);
        System.out.println(); // 1 2 3 4 5 

        reorderList(head);

        printNode(head);
        System.out.println();  // 1 5 2 4 3 
    }

    public static void reorderList(ListNode head) {
       if (head == null) return ;
       int n = 0;
       for (ListNode p = head; p != null; p = p.next) n ++;
       ListNode mid = head;
       for (int i = 0; i < (n + 1) / 2 - 1; i ++) mid = mid.next;
       ListNode tail = mid;
       for (ListNode p = mid, q = mid.next; q != null; ) {
           ListNode next = q.next;
           q.next = p; p = q; q = next;
           tail = p;
       }

       for (ListNode p = head, q = tail; q != mid; ) {
           ListNode next = q.next;
           q.next = p.next;
           p.next = q;
           p = p.next.next; q = next;
       }

       if (n % 2 != 0) mid.next = null;
       else mid.next.next = null;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/

    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC147. 对链表进行插入排序

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 -1->5->3->4->0
        ListNode head = new ListNode(-1, new ListNode(5, 
                new ListNode(3, new ListNode(4, new ListNode(0)))));

        printNode(head);
        System.out.println(); // -1 5 3 4 0 

        ListNode node = insertionSortList(head);

        printNode(node);
        System.out.println();  // -1 0 3 4 5 
    }

    public static ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        for (ListNode p = head; p != null; ) {
            ListNode cur = dummy, next = p.next;
            while (cur.next != null && cur.next.val <= p.val) cur = cur.next;
            p.next = cur.next;
            cur.next = p;
            p = next;
        }

        return dummy.next;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/

    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC203. 移除链表元素

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->6->3->4->5->6
        ListNode head = new ListNode(1, new ListNode(2, 
                new ListNode(6, new ListNode(3, new ListNode(4, new ListNode(5,
                new ListNode(6)))))));

        printNode(head);
        System.out.println(); // 1 2 6 3 4 5 6  

        int val = 6;
        ListNode node = removeElements(head, val);

        printNode(node);
        System.out.println();  // 1 2 3 4 5 
    }

    public static ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        for (ListNode p = dummy; p != null; p = p.next) {
            ListNode q = p.next;
            while (q != null && q.val == val) q = q.next;
            p.next = q;
        }

        return dummy.next;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/

    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC206. 反转链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->3->4->5
        ListNode head = new ListNode(1, new ListNode(2,new ListNode(3, 
                    new ListNode(4, new ListNode(5)))));

        printNode(head);
        System.out.println(); // 1 2 3 4 5   

        ListNode node = reverseList(head);

        printNode(node);
        System.out.println();  // 5 4 3 2 1 
    }

    // 方法一：非递归，迭代方式
    public static ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode a = head, b = a.next;
        while (b != null) {
            ListNode c = b.next;
            b.next = a;
            a = b; b = c;
        }

        head.next = null;
        return a;
    }

/*
    // 方法二：递归方式
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return tail;
    }*/

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/

    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC234. 回文链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 1->2->2->1
        ListNode head = new ListNode(1, new ListNode(2,
                new ListNode(2, new ListNode(1))));

        printNode(head);
        System.out.println(); // 1 2 2 1  

        boolean ans = isPalindrome(head);

        System.out.println(ans);  // true
    }

    /*
        1.先将后一半链表反转
        2.判断前一半与后一半链表是否对称
        3. 将后一半链表反转回来
    */

    public static boolean isPalindrome(ListNode head) {
       int n = 0;
       for (ListNode p = head; p != null; p = p.next) n ++;

       if (n <= 1) return true; // 只有一个节点的链表
       int half = n / 2; // 前一半和后一半要判断的长度

       ListNode a = head; //为反转后半段链表做准备
       for (int i = 0; i < n - half; i ++) a = a.next; // 后半段链表共half个节点，需要反转half-1次
       ListNode b = a.next;
       //1. 反转
       for (int i = 0; i < half - 1; i ++) {
           ListNode c = b.next;
           b.next = a;
           a = b; b = c; //反转之后，a指向最后一个点，b指向空
       }

       ListNode p = head, q = a; //两个指针p和q，分别从前往后走，和从后往前走
       // 2. 判断是否对称
       boolean success = true;
       for (int i = 0; i < half; i ++) { //共需循环half次，左右各half个点，所以对half个点判断
           if (p.val != q.val) {
               success = false;
               break;
           }
           p = p.next;
           q = q.next;
       }

       ListNode tail = a; // tail保留最后一个节点，最后一个节点指向null
       b = a.next;

       for (int i = 0; i < half - 1; i ++) { // 3. 将链表回复原状
           ListNode c = b.next;
           b.next = a;
           a = b; b = c;
       }

       tail.next = null;
       return success;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/

    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC237. 删除链表中的节点

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 链表输入 4->5->1->9
        ListNode head = new ListNode(4);
        ListNode node = new ListNode(5);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(9);

        head.next = node;
        node.next = node1;
        node1.next = node2;

        printNode(head);
        System.out.println(); // 4 5 1 9  

        deleteNode(head, node);

        printNode(head);
        System.out.println();  // 4 1 9 
    }

    public static void deleteNode(ListNode head, ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    public static void printNode(ListNode head) { //注意：方法都是静态的
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            System.out.print(" ");
        }
        /*       
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
            System.out.print(" ");
        }*/

    }

    public static class ListNode { //定义的时候注意是静态内部类
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

LC88. 合并两个有序数组

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int m = 3;
        int[] nums2 = {2, 5, 6};
        int n = 3;

        merge(nums1, m, nums2, n);

        System.out.println(Arrays.toString(nums1)); //输出: [1,2,2,3,5,6]
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1;
        int i = m - 1, j = n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) nums1[k --] = nums1[i --];
            else nums1[k --] = nums2[j --];
        }

        while (j >= 0) nums1[k --] = nums2[j --];
    }


}

LC94. 二叉树的中序遍历

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 这种建树方式，和建业的一个个建立节点，然后lefth和right连接都要会
        TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)); 

        /*      
        这是另一种建树方式
        TreeNode root = new TreeNode(1);
        TreeNode a = new TreeNode(2);
        TreeNode b = new TreeNode(3);

        root.right = a;
        a.left = b;
        */

        List<Integer> ans = inorderTraversal(root);

        System.out.println(ans); // [1, 3, 2]
    }

    // 中序递归遍历二叉树
    /*  
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    public static void dfs(TreeNode root, List<Integer> res) {
        if (root == null) return ;
        dfs(root.left, res);
        res.add(root.val);
        dfs(root.right, res);
    }
    */

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();

        while (root != null || !stk.empty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }

            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC100. 相同的树

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 这种建树方式，和建业的一个个建立节点，然后lefth和right连接都要会
        TreeNode root1 = new TreeNode(1, null, new TreeNode(2)); 
        // TreeNode root2 = new TreeNode(1, new TreeNode(2), null); 
        TreeNode root2 = new TreeNode(1, new TreeNode(2), null); //这个样例就是true了。

        System.out.println(isSameTree(root1, root2));  // false
    }


    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null || p.val != q.val) return false;

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC101. 对称二叉树


import java.util.*;

public class Main {
    public static void main (String[] args) {

/*
        //这个例子是true
        TreeNode root = new TreeNode(1, 
                new TreeNode(2, new TreeNode(3), new TreeNode(4)),
                new TreeNode(2, new TreeNode(4), new TreeNode(3)) 
        );
*/

        TreeNode root = new TreeNode(1, 
                new TreeNode(2, null, new TreeNode(3)),
                new TreeNode(2, null, new TreeNode(3))
        );


        System.out.println(isSymmetric(root));  //false
    }


    // 下面是递归解法    
/*    
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return dfs(root.left, root.right);
    }


    public static boolean dfs(TreeNode p, TreeNode q) {
        if (p == null &&  q == null) return true;
        if (p == null || q == null || p.val != q.val) return false;
        return dfs(p.left, q.right) && dfs(p.right, q.left);
    }*/


    // 下面是非递归写法（迭代版本）
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> left = new Stack<>();
        Stack<TreeNode> right = new Stack<>();
        TreeNode lc = root.left;
        TreeNode rc = root.right;
        while (lc != null || rc != null || !left.empty()) {
            while (lc != null && rc != null) {
                left.push(lc);
                right.push(rc);
                lc = lc.left;
                rc = rc.right;
            }
            if (lc != null || rc != null) return false;
            lc = left.pop();
            rc = right.pop();
            if (lc.val != rc.val) return false;
            lc = lc.right;
            rc = rc.left;
        }

        return true;

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC104. 二叉树的最大深度 (非递归写法没补呢！！)

import java.util.*;

public class Main {
    public static void main (String[] args) {
/*        TreeNode root = new TreeNode(10, 
                new TreeNode(5, 
                    new TreeNode(3,
                        new TreeNode(1),
                        new TreeNode(4)),
                    new TreeNode(8)),
                new TreeNode(11)

        );
        这棵二叉树的深度是4
        */

        TreeNode root = new TreeNode(3, 
            new TreeNode(9), 
            new TreeNode(20, 
                new TreeNode(15),
                new TreeNode(7))
            );


        System.out.println(maxDepth(root));  //3
    }


/*  第一种递归写法 
    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }*/

    // 另一种递归写法
    public static int dfs(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(dfs(root.left), dfs(root.right));
    }

    public static int maxDepth(TreeNode root) {
        return dfs(root);
    } 


    // 非递归写法
    // public static int dfs(TreeNode root) {

    // }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC108. 将有序数组转换为二叉搜索树

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sortedArrayToBST(nums);

        List<Integer> res = postorderTraversal(root);
        System.out.println(res); // 后序遍历结果 [-3, -10, 9, 5, 0]
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    public static TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int mid = l + r >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, l, mid - 1);
        root.right = build(nums, mid + 1, r);
        return root;
    }

    // 后序遍历一下
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    public static void dfs(TreeNode root, List<Integer> res) {
        if (root == null) return ;
        dfs(root.left, res);
        dfs(root.right, res);
        res.add(root.val);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC110. 平衡二叉树

import java.util.*;

public class Main {
    public static boolean ans;

    public static void main (String[] args) {
 /*      
        TreeNode root = new TreeNode(3, 
                new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7))
        );
        这棵树是true
        */

        TreeNode root = new TreeNode(1, 
            new TreeNode(2, 
                    new TreeNode(3, 
                            new TreeNode(4), new TreeNode(4)),
                    new TreeNode(3)
            ),
            new TreeNode(2)
            );

        System.out.println(isBalance(root));  // false
    }

    public static boolean isBalance(TreeNode root) {
        ans = true;
        dfs(root);
        return ans;
    }

    public static int dfs(TreeNode root) {
        if (root == null) return 0;
        int lh = dfs(root.left);
        int rh = dfs(root.right);
        if (Math.abs(lh - rh) > 1) ans = false;
        return Math.max(lh, rh) + 1;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC111. 二叉树的最小深度

import java.util.*;

public class Main {
    public static boolean ans;

    public static void main (String[] args) {
        TreeNode root = new TreeNode(3,
                new TreeNode(9), 
                new TreeNode(20, 
                        new TreeNode(15),
                        new TreeNode(7))
                );

        System.out.println(minDepth(root));  // 2
    }

    public static int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (root.left != null && root.right != null)
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        if (root.left != null) return minDepth(root.left) + 1;
        return minDepth(root.right) + 1;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC112. 路径总和

import java.util.*;

public class Main {
    public static boolean ans;

    public static void main (String[] args) {
        TreeNode root = new TreeNode(5,
                new TreeNode(4, 
                        new TreeNode(11, 
                                new TreeNode(7), 
                                new TreeNode(2)),
                        null),
                new TreeNode(8,
                        new TreeNode(13),
                        new TreeNode(4, 
                                null,
                                new TreeNode(1)
                        )
                )
        );

        System.out.println(hasPathSum(root, 22));  // true 
    }

    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        targetSum -= root.val;
        if (root.left == null && root.right == null) return targetSum == 0; 
        return (root.left != null && 
            hasPathSum(root.left, targetSum) || 
            root.right != null && hasPathSum(root.right, targetSum)); 
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

LC118. 杨辉三角

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(generate(5)); 
        // [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows == 0) return res;
        res.add(Arrays.asList(1));

        for (int i = 1; i < numRows; i ++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for (int j = 1; j < i; j ++) 
                list.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
            list.add(1);
            res.add(list);

        }
        return res;
    }


}

LC119. 杨辉三角II

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(getRow(3)); //[1, 3, 3, 1]
    }

    // 优化前    
    public static List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        int[][] f = new int[rowIndex + 1][rowIndex + 1];

        for (int i = 0; i <= rowIndex; i ++) {
            for (int j = 0; j <= i; j ++) {
                if (j == 0) f[i][j] = 1;
                if (i == j) f[i][j] = 1;
                if (i > 0 && j > 0) f[i][j] = f[i - 1][j - 1] + f[i - 1][j];

                if (i == rowIndex) res.add(f[i][j]);
            }
        }
        return res;
    }

    /*
        // 使用滚动数组优化后    
    public static List<Integer> getRow(int n) {
        int[][] f = new int[2][n + 1];

        for(int i = 0; i < n + 1; i ++){
            f[i & 1][0] = f[i & 1][i] = 1;
            for(int j = 1; j < i; j ++)
                f[i & 1][j] = f[i - 1 & 1][j - 1] + f[i - 1 & 1][j];
        }

        List<Integer> res = new ArrayList();
        for(int i = 0; i < n + 1; i ++){
            res.add(f[n & 1][i]);
        }

        return res;
    }
    */

}

LC121. 买卖股票的最佳时机

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] prices = {7,1,5,3,6,4}; // 输出4
        // int[] prices = {7,6,4,3,1};
        System.out.println(maxProfit(prices)); 
    }

    public static int maxProfit(int[] prices) {
        int res = 0;
        // int minp = 0x3f3f3f3f;
        int minp = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i ++) {
            res = Math.max(res, prices[i] - minp);
            minp = Math.min(minp, prices[i]); //注意这里()第一个是minp,不是res
        }
        return res;
    }

}

LC125. 验证回文串


import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama")); //true
        // System.out.println(isPalindrome("race a car")); //false

    }

    public static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i ++, j --) {
            while (i < j && !check(s.charAt(i))) i ++;
            while (i < j && !check(s.charAt(j))) j --;
            if (i < j && Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
                return false;
        }
        return true;
    }

    public static boolean check(char c) {
        return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9';
    }

}

LC136. 只出现一次的数字

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {4,1,2,1,2};
        System.out.println(singleNumber(nums)); // 4
    }

    public static int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i ++) res ^= nums[i];

        return res;
    }


}

LC141. 环形链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        ListNode head = new ListNode(3);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(0);
        ListNode head4 = new ListNode(-4);

        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head2;


        System.out.println(hasCycle(head)); // true
    }

    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode s = head, f = head.next;
        while (f != null) {
            s = s.next;
            f = f.next;
            if (f == null) return false;
            f = f.next;
            if (s == f) return true;
        }
        return false;
    }

    public static class ListNode {
        int val;
        ListNode next;

/*      
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }*/
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}

LC144. 二叉树前序遍历


import java.util.*;

public class Main {
    public static void main (String[] args) {
        // TreeNode root = new TreeNode(1, null, 
            new TreeNode(2, new TreeNode(3), null)); //这是一种 建树方式

        TreeNode root = new TreeNode(1);
        TreeNode a = new TreeNode(2);
        TreeNode b = new TreeNode(3);

        root.right = a;
        a.left = b; //  这个样例的前序遍历结果是 [1, 2, 3]

        /*
        TreeNode root = new TreeNode(5,
                new TreeNode(4, 
                        new TreeNode(11, 
                                new TreeNode(7), 
                                new TreeNode(2)),
                        null),
                new TreeNode(8,
                        new TreeNode(13),
                        new TreeNode(4, 
                                null,
                                new TreeNode(1)
                        )
                )
        ); // 这个样例的前序遍历结果是 [5, 4, 11, 7, 2, 8, 13, 4, 1]*/


        List<Integer> ans = preorderTraversal(root);

        System.out.println(ans);
    }        

   // 中序递归遍历二叉树
    /*  
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    public static void dfs(TreeNode root, List<Integer> res) {
        if (root == null) return ;
        res.add(root.val);
        dfs(root.left, res);
        dfs(root.right, res);
    }
    */

    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();

        while (root != null || !stk.empty()) {
            while (root != null) {
                res.add(root.val);
                stk.push(root);
                root = root.left;
            }

            root = stk.pop();
            root = root.right;
        }

        return res;
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

    }
}

LC145. 二叉树的后序遍历

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // TreeNode root = new TreeNode(1, null,
                new TreeNode(2, new TreeNode(3), null)); //这是一种 建树方式

/*        TreeNode root = new TreeNode(1);
        TreeNode a = new TreeNode(2);
        TreeNode b = new TreeNode(3);

        root.right = a;
        a.left = b; //  这个样例的前序遍历结果是 [1, 2, 3]
        */

        TreeNode root = new TreeNode(5,
                new TreeNode(4, 
                        new TreeNode(11, 
                                new TreeNode(7), 
                                new TreeNode(2)),
                        null),
                new TreeNode(8,
                        new TreeNode(13),
                        new TreeNode(4, 
                                null,
                                new TreeNode(1)
                        )
                )
        ); // 这个样例的后序遍历结果是 [7, 2, 11, 4, 13, 1, 4, 8, 5]


        List<Integer> ans = postorderTraversal(root);

        System.out.println(ans);
    }        

   // 后序递归遍历二叉树
    /*  
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    public static void dfs(TreeNode root, List<Integer> res) {
        if (root == null) return ;
        dfs(root.left, res);
        dfs(root.right, res);
        res.add(root.val);
    }
    */

    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();

        while (root != null || !stk.empty()) {
            while (root != null) {
                res.add(root.val);
                stk.push(root);
                root = root.right;
            }

            root = stk.pop();
            root = root.left;
        }
        Collections.reverse(res);

        return res;
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

    }
}

LC155. 最小栈

import java.util.*;

public class Main {
    public static void main (String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);

        System.out.println(minStack.getMin()); //  -3
        minStack.pop();

        System.out.println(minStack.top()); // 0
        System.out.println(minStack.getMin()); // -2
        System.out.println(minStack.getMin()); // -2
        System.out.println(minStack.getMin()); // -2
        System.out.println(minStack.getMin()); // -2
    }

    public static class MinStack {
        public static Stack<Integer> stk;
        public static Stack<Integer> min_stk;

        public MinStack() {
            stk = new Stack<Integer>();
            min_stk = new Stack<Integer>();
        }

/*        public static void push(int x) {
            if (stk.empty()) {
                stk.push(x);
                min_stk.push(x);
                return ;
            }
            int min_x = min_stk.peek();
            if (min_x < x) {
                stk.push(x);
                min_stk.push(min_x);
            } else {
                stk.push(x);
                min_stk.push(x);
            }
        }*/

        public static void push(int x) {
            stk.push(x);
            if (min_stk.empty() || min_stk.peek() >= x) min_stk.push(x);
        }

/*        public static void pop() {
            stk.pop();
            min_stk.pop();
        }*/

        public static void pop() {
            if (stk.peek() == min_stk.peek()) min_stk.pop();
            stk.pop();
        }

        public static int top() {
            return stk.peek();
        }

        public static int getMin() {
            return min_stk.peek();
        }
    }

}

Lc160. 相交链表

import java.util.*;

public class Main {
    public static void main (String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);

        node1.next = node3;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        // node1: 1->3->4->5->6
        // node2: 2->3->4->5->6

        System.out.println(getIntersectionNode(node1, node2).val); // 3
    }
/*    
    // 推荐的方式
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;

        while (p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }

        return p;
    }
    */

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
        ListNode p = headA, q = headB;
        int la = 0, lb = 0;
        for (ListNode t = headA; t != null; t = t.next) la ++;
        for (ListNode t = headB; t != null; t = t.next) lb ++;

        int k = la - lb;
        if (la < lb) {
            p = headB;
            q = headA;
            k = lb - la;
        }

        while (k -- != 0) {
            p = p.next;
        }

        while (p != null) {
            if (p == q) return p;
            p = p.next;
            q = q.next;
        }

        return null;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}

LC168. Excel表列名称

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(convertToTitle(28)); // AB

    }

    public static String convertToTitle(int num) {
        StringBuffer sb = new StringBuffer("");
        while (num > 0) {
            num --;
            sb.append((char)(num % 26 + 'A'));
            num /= 26;
        }

        return sb.reverse().toString();
    }

}

LC169. 多数元素

import java.util.*;

public class Main {
    public static void main (String[] args) {
    //   int[] nums = {2, 2, 1, 1, 1, 2, 2}; //输出2

       int[] nums = {3, 2, 3}; //输出3

        System.out.println(majorityElement(nums));
    }

    public static int  majorityElement(int[] nums) {
        int val = nums[0], cnt = 1;
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] == val) cnt ++;
            else cnt --;
            if (cnt == 0) {
                val = nums[i];
                cnt = 1;
            }
        }

        return val;
    }

}

LC171. Excel表列序号

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(titleToNumber("ZY")); // 701
    }

    public static int titleToNumber(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i ++) {
            res = res * 26 + (s.charAt(i) - 'A' + 1);
        }

        return res;
    }

}

LC202. 快乐数

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(isHappy(19)); //true
    }

    public static boolean isHappy(int n) {
        if (n == 1) return true;
        HashSet<Integer> set = new HashSet<Integer>();
        set.add(n);
        while (n != 1) {
            n = get(n);
            if (n == 1) return true;
            if (set.contains(n)) break;
            set.add(n);
        }

        return false;
    }

    public static int get(int n) {
        int res = 0;
        while (n != 0) {
            res += (n % 10) * (n % 10);
            n /= 10;
        }

        return res;
    }

}

环形链表的思路

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(isHappy(19)); //true
    }

    public static boolean isHappy(int n) {
        if (n == 1) return true;
        int fast = get(n), slow = n;
        while (fast != slow) {
            fast = get(get(fast));
            slow = get(slow);
        }

        return fast == 1;
    }

    public static int get(int n) {
        int res = 0;
        while (n != 0) {
            res += (n % 10) * (n % 10);
            n /= 10;
        }

        return res;
    }

}

LC167. 两数之和 II - 输入有序数组

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        String res = Arrays.toString(twoSum(nums, target));
        System.out.println(res); //输出: [1,2]
    }

    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0, j = nums.length - 1; i < nums.length; i ++) {
            while (i < j && nums[i] + nums[j] > target) j --;
            while (i < j && nums[i] + nums[j] == target) return new int[]{i + 1, j + 1};
        }

        return new int[]{};
    }

}

0 评论

App 内打开