【剑指Offer】Java题解汇总(下)

【剑指Offer】Java题解汇总(下)

51. 数组中的逆序对

//实际上就是 归并排序
/*有问题
class Solution {
    int sum = 0;
    public int reversePairs(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(nums,0,nums.length-1,temp);
        return sum;
    }
    //分+合方法
    public void mergeSort(int[] arr, int left, int right, int[] temp){
        if(left < right){
            int mid = (left+right)/2; //中间索引
            //向左递归进行分解
            mergeSort(arr,left,mid,temp);
            //向右递归进行分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }
    //合并的方法, 从后往前比
    public void merge(int[] arr, int left, int mid, int right, int[] temp){
        int i = mid; //初始化i,左边有序序列的初始索引
        int j = right; //初始化j,右边有序序列的初始索引
        int t = temp.length-1; //指向temp数组的当前索引

        //(一)
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列,有一边处理完毕为止
        while(i>=0 && j>mid){
            if(arr[i] >= arr[j]){
                temp[t] = arr[i];
                t --;
                i --;
                sum += j-mid;
            }else{
                temp[t] = arr[j];
                t --;
                j --;
               
            }
        }

        //(二)
        //把有剩余的一边的数据依次全部填充到temp
        while(i >=0){
            temp[t] = arr[i];
            t --;
            i --;
        }
        while(j > mid){
            temp[t] = arr[j];
            t --;
            j --;
        }

        //(三)
        //将temp数组的元素拷贝到arr
        t = 0;
        int tempLeft = left;
        while(tempLeft <= right){
            arr[tempLeft] = temp[t];
            t ++;
            tempLeft ++;
        }

    }
}
*/
//实际上就是 归并排序的思想
//照抄剑指offer代码
class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length < 2){
            return 0;
        }
        int[] temp = new int[nums.length];
        for(int i=0; i<nums.length; i++){
            temp[i] = nums[i];
        }
        int sum = inversePairsCore(nums,temp,0,nums.length-1);
        return sum;
    }
    public int inversePairsCore(int[] nums, int[] temp, int start,int end){
        if(start == end){
            temp[start] = nums[start];
            return 0;
        }
        int length = (end - start)/2;
        int left = inversePairsCore(temp,nums,start,start+length);
        int right = inversePairsCore(temp,nums,start+length+1,end);

        int i = start+length;
        int j = end;
        int indexCopy = end;
        int count = 0;
        while(i >= start && j >= start+length+1){
            if(nums[i] > nums[j]){
                temp[indexCopy--] = nums[i--];
                count += j-start-length;
            }else{
                temp[indexCopy--] = nums[j--];
            }
        }
        for(;i>=start;--i){
            temp[indexCopy--]=nums[i];
        }
        for(;j>=start+length+1;--j){
            temp[indexCopy--]=nums[j];
        }
        return left+right+count;
    }
}

52. 两个链表的第一个公共节点

方法很多:双指针法、先求出两个链表的长度法、栈的方法、集合的方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /*先计算长度,再比较
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        int cntA = 0;
        int cntB = 0;
        ListNode tempA = headA;
        ListNode tempB = headB;
        while(tempA != null){
            cntA++;
            tempA = tempA.next;
        }
        while(tempB != null){
            cntB++;
            tempB = tempB.next;
        }
        tempA = headA;
        tempB = headB;
        if(cntA > cntB){
            for(int i=0; i<cntA-cntB; i++){
                tempA = tempA.next;
            }
        }
        if(cntA < cntB){
            for(int i=0; i<cntB-cntA; i++){
                tempB = tempB.next;
            }
        }
        while(tempA != null && tempB != null && tempA != tempB){
            tempA = tempA.next;
            tempB = tempB.next;
        }
        return tempA;
    }
    */
    //双指针法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //tempA和tempB我们可以认为是A,B两个指针
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            //如果指针tempA不为空,tempA就往后移一步。
            //如果指针tempA为空,就让指针tempA指向headB(注意这里是headB不是tempB)
            tempA = tempA == null ? headB : tempA.next;
            //指针tempB同上
            tempB = tempB == null ? headA : tempB.next;
        }
        //tempA要么是空,要么是两链表的交点
        return tempA;
    }

}

53. 在排序数组中查找数字(1)

先找出右端点,再找出左端点

class Solution {
    public int search(int[] nums, int target) {
        int i = 0;
        int j = nums.length-1;
        int left = 0;
        int right = 0;
        while(i <= j){
            int mid = (i+j)/2;
            if(nums[mid] <= target){
                i = mid+1;
            }else{
                j = mid-1;
            }
        }
        right = i;
        // 若数组中无 target ,则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        i = 0;
        while(i <= j){
            int mid = (i+j)/2;
            if(nums[mid] < target){
                i = mid+1;
            }else{
                j = mid-1;
            }
        }
        left = j;
        return right-left-1;
    }
}

54. 在排序数组中查找数字(2)

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length-1;
        while(i <= j){
            int m = (i+j)/2;
            if(nums[m] == m){
                //注意这里的m==j和下面的m==0的边界条件
                if(m == j || nums[m+1] != (m+1)){
                    return m+1;
                }
                i = m+1;
            }else{
                if(m == 0 || nums[m-1] == (m-1)){
                    return m;
                }
                j = m-1;
            }
        }
        return i;
    }
}

55. 二叉搜索树的第k大节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 /*我的写法
class Solution {
    List<TreeNode> list = new ArrayList<TreeNode>();
    public int kthLargest(TreeNode root, int k) {
        mid(root);
        return list.get(k-1).val;
    }
    public void mid(TreeNode root){
        if(root == null){
            return;
        }
        mid(root.right);
        list.add(root);
        mid(root.left);
    }
}
*/
//大佬的写法,可以提前终止
class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}

56. 二叉树的深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 /*
 //深度有限遍历
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
*/
//层序遍历
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}

57. 平衡二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

58. 数组中数字出现的次数(1)

class Solution {
    public int[] singleNumbers(int[] nums) {
        int ret = 0;
        for (int n : nums) {
            ret ^= n;
        }
        int div = 1;
        while ((div & ret) == 0) {
            div <<= 1;
        }
        int a = 0, b = 0;
        for (int n : nums) {
            if ((div & n) != 0) {
                a ^= n;
            } else {
                b ^= n;
            }
        }
        return new int[]{a, b};
    }
}

59. 数组中数字出现的次数(2)

class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums) {
            for(int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }
}

60. 和为s的两个数字

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i < j) {
            int s = nums[i] + nums[j];
            if(s < target) i++;
            else if(s > target) j--;
            else return new int[] { nums[i], nums[j] };
        }
        return new int[0];
    }
}

61. 和为s的连续正数序列

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> vec = new ArrayList<int[]>();
        for (int l = 1, r = 2; l < r;) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] res = new int[r - l + 1];
                for (int i = l; i <= r; ++i) {
                    res[i - l] = i;
                }
                vec.add(res);
                l++;
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        return vec.toArray(new int[vec.size()][]);
    }
}

62. 翻转单词顺序

/*
//双指针法
class Solution {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}
*/
//Java内置函数
class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" "); // 删除首尾空格,分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空单词则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串,删除尾部空格,并返回
    }
}

63. 左旋转字符串

/*
//字符串切片
class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}
*/
//遍历拼接
class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < s.length(); i++)
            res.append(s.charAt(i));
        for(int i = 0; i < n; i++)
            res.append(s.charAt(i));
        return res.toString();
    }
}

64. 滑动窗口的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.removeFirst(); // 删除 deque 中对应的 nums[i-1]
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.removeLast(); // 保持 deque 递减
            deque.addLast(nums[j]);
            if(i >= 0)
                res[i] = deque.peekFirst();  // 记录窗口最大值
        }
        return res;
    }
}

65. 队列的最大值

class MaxQueue {
    Queue<Integer> q;
    Deque<Integer> d;

    public MaxQueue() {
        q = new LinkedList<Integer>();
        d = new LinkedList<Integer>();
    }
    
    public int max_value() {
        if (d.isEmpty()) {
            return -1;
        }
        return d.peekFirst();
    }
    
    public void push_back(int value) {
        while (!d.isEmpty() && d.peekLast() < value) {
            d.pollLast();
        }
        d.offerLast(value);
        q.offer(value);
    }
    
    public int pop_front() {
        if (q.isEmpty()) {
            return -1;
        }
        int ans = q.poll();
        if (ans == d.peekFirst()) {
            d.pollFirst();
        }
        return ans;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

66. 扑克牌中的顺子

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums) {
            if(num == 0) continue; // 跳过大小王
            max = Math.max(max, num); // 最大牌
            min = Math.min(min, num); // 最小牌
            if(repeat.contains(num)) return false; // 若有重复,提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

67. 圆圈中最后剩下的数字

/*
//递归
class Solution {
    public int lastRemaining(int n, int m) {
        return f(n, m);
    }

    public int f(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = f(n - 1, m);
        return (m + x) % n;
    }
}
*/
//迭代
class Solution {
    public int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i) {
            f = (m + f) % i;
        }
        return f;
    }
}

68. 股票的最大利润

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

69. 求1+2+。。。+n

class Solution {
    public int sumNums(int n) {
        boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

70. 不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

71. 构建乘积数组

class Solution {
    public int[] constructArr(int[] a) {
        if(a.length == 0) return new int[0];
        int[] b = new int[a.length];
        b[0] = 1;
        int tmp = 1;
        for(int i = 1; i < a.length; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }
        for(int i = a.length - 2; i >= 0; i--) {
            tmp *= a[i + 1];
            b[i] *= tmp;
        }
        return b;
    }
}

72. 把字符串转换为整数

class Solution {
    public int strToInt(String str) {
        char[] c = str.trim().toCharArray();
        if(c.length == 0) return 0;
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 1, sign = 1;
        if(c[0] == '-') sign = -1;
        else if(c[0] != '+') i = 0;
        for(int j = i; j < c.length; j++) {
            if(c[j] < '0' || c[j] > '9') break;
            if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (c[j] - '0');
        }
        return sign * res;
    }
}

73. 二叉搜索树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
            if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}

74. 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null; // 如果树为空,直接返回null
        if(root == p || root == q) return root; // 如果 p和q中有等于 root的,那么它们的最近公共祖先即为root(一个节点也可以是它自己的祖先)
        TreeNode left = lowestCommonAncestor(root.left, p, q); // 递归遍历左子树,只要在左子树中找到了p或q,则先找到谁就返回谁
        TreeNode right = lowestCommonAncestor(root.right, p, q); // 递归遍历右子树,只要在右子树中找到了p或q,则先找到谁就返回谁
        if(left == null) return right; // 如果在左子树中 p和 q都找不到,则 p和 q一定都在右子树中,右子树中先遍历到的那个就是最近公共祖先(一个节点也可以是它自己的祖先)
        else if(right == null) return left; // 否则,如果 left不为空,在左子树中有找到节点(p或q),这时候要再判断一下右子树中的情况,如果在右子树中,p和q都找不到,则 p和q一定都在左子树中,左子树中先遍历到的那个就是最近公共祖先(一个节点也可以是它自己的祖先)
        else return root; //否则,当 left和 right均不为空时,说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×