剑指Offer之Java算法习题精讲链表与数组专项训练

题目一

数组题——查找目标值

在给定的数组中查找指定的目标值,这里提供两种解法

具体题目如下

解法一

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

解法二

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

题目二

数组题——查找三元组

查找给定的数组中是否存在指定的三个元素并使得该三个元素相加等于0

具体题目如下

解法

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        return nSumTarget(nums, 3, 0, 0);
    }
    public List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target){
        int size = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(n < 2 || size < n) return res;
        if(n == 2){
            int lo = start, hi = size - 1;
            while(lo < hi){
                int left = nums[lo], right = nums[hi];
                int sum = left + right;
                if(sum < target){
                    while(lo < hi && nums[lo] == left) lo++;
                }else if(sum > target){
                    while(lo < hi && nums[hi] == right) hi--;
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[lo]);
                    list.add(nums[hi]);
                    res.add(list);
                    while(lo < hi && nums[lo] == left) lo++;
                    while(lo < hi && nums[hi] == right) hi--;
                }
            }
        }else{
            for(int i = start; i < size; i++){
                List<List<Integer>> temp = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for(List<Integer> list : temp){
                    list.add(nums[i]);
                    res.add(list);
                }
                while(i < size - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }
}

题目三

数组题——查找四元组

查找给定的数组中满足条件的四元组

具体题目如下

解法

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSumTarget(nums,4,0,target);
    }
    public List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target){
        int size = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(n < 2 || size < n) return res;
        if(n == 2){
            int lo = start, hi = size - 1;
            while(lo < hi){
                int left = nums[lo], right = nums[hi];
                int sum = left + right;
                if(sum < target){
                    while(lo < hi && nums[lo] == left) lo++;
                }else if(sum > target){
                    while(lo < hi && nums[hi] == right) hi--;
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[lo]);
                    list.add(nums[hi]);
                    res.add(list);
                    while(lo < hi && nums[lo] == left) lo++;
                    while(lo < hi && nums[hi] == right) hi--;
                }
            }
        }else{
            for(int i = start; i < size; i++){
                List<List<Integer>> temp = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for(List<Integer> list : temp){
                    list.add(nums[i]);
                    res.add(list);
                }
                while(i < size - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }
}

模板理解背下来~

题目四

链表题——反转链表

根据单链表的头节点head来返回反转后的链表

具体题目如下

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

题目五

链表题——反转链表

根据单链表的头节点head和指定条件来返回反转后的链表

具体题目如下

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode cure = null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==1){
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next,left-1,right-1);
        return head;
    }
    public ListNode reverseN(ListNode head,int n){
        if(n==1){
            cure = head.next;
            return head;
        }
        ListNode last = reverseN(head.next,n-1);
        head.next.next = head;
        head.next = cure;
        return last;
    }
}

到此这篇关于剑指Offer之Java算法习题精讲链表与数组专项训练的文章就介绍到这了,更多相关Java 链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 剑指Offer之Java算法习题精讲字符串与二叉搜索树

    题目一 解法 class Solution { public boolean repeatedSubstringPattern(String a) { for (int i = 1; i <=a.length()/2 ; i++) { String s = a.substring(0, i); StringBuffer sb = new StringBuffer(); while (sb.length()<a.length()){ sb.append(s); } if(sb.toString(

  • 剑指Offer之Java算法习题精讲二叉树的构造和遍历

    题目一  解法 /** * Definition for a binary tree node. * public 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; *

  • 剑指Offer之Java算法习题精讲数组与字符串题

    题目一 解法 class Solution { public int thirdMax(int[] nums) { Arrays.sort(nums); if(nums.length<3){ return nums[nums.length-1]; } int p = 1; for(int i =nums.length-2;i>=0;i--){ if(nums[i]==nums[i+1]){ }else{ ++p; if(p==3){ return nums[i]; } } } return n

  • 剑指Offer之Java算法习题精讲数组与二叉树

    题目一  解法 /** * Definition for a binary tree node. * public 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; *

  • 剑指Offer之Java算法习题精讲链表与字符串及数组

    题目一 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Soluti

  • 剑指Offer之Java算法习题精讲N叉树的遍历及数组与字符串

    题目一 解法 /* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class S

  • 剑指Offer之Java算法习题精讲二叉树专项训练

    题目一  解法 /** * Definition for a binary tree node. * public 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; *

  • 剑指Offer之Java算法习题精讲数组与字符串

    题目一  解法 class Solution { public int findLengthOfLCIS(int[] nums) { if(nums.length==1) return 1; int fast = 1; int tmp = 1; int max = Integer.MIN_VALUE; while(fast<nums.length){ if(nums[fast]>nums[fast-1]){ tmp++; max = Math.max(max,tmp); }else{ max

  • 剑指Offer之Java算法习题精讲链表与数组专项训练

    题目一 数组题——查找目标值 在给定的数组中查找指定的目标值,这里提供两种解法 具体题目如下 解法一 class Solution { public int[] twoSum(int[] nums, int target) { int[] a = {-1,-1}; for(int i = 0;i<nums.length-1;i++){ for(int j = i+1;j<nums.length;j++){ if(nums[i]+nums[j]==target){ a[0] = i; a[1]

  • 剑指Offer之Java算法习题精讲链表与二叉树专项训练

    题目一 链表题——反转链表 根据单链表的头节点head来返回反转后的链表 具体题目如下 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val;

  • 剑指Offer之Java算法习题精讲链表专题篇

    题目一  解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solut

  • 剑指Offer之Java算法习题精讲链表专项训练

    题目一 链表题--链表合并 根据给定的两个升序链表合并为一个新的升序链表 具体题目如下 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val;

  • 剑指Offer之Java算法习题精讲二叉树与斐波那契函数

    题目一 解法 class Solution { public int fib(int n) { int[] arr = new int[31]; arr[0] = 0; arr[1] = 1; for(int i = 2;i<=n;i++){ arr[i] = arr[i-2]+arr[i-1]; } return arr[n]; } } 题目二  解法 /** * Definition for a binary tree node. * public class TreeNode { * in

  • 剑指Offer之Java算法习题精讲二叉树与N叉树

    题目一  解法 /** * Definition for a binary tree node. * public 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; *

  • 剑指Offer之Java算法习题精讲二叉树专题篇下

    题目一  解法 /** * Definition for a binary tree node. * public 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; *

  • 剑指Offer之Java算法习题精讲二叉树专题篇上

    来和二叉树玩耍吧~ 题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val

  • 剑指Offer之Java算法习题精讲数组与字符和等差数列

    题目一  解法 class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { int[] arr = new int[1001]; int[] ans = new int[arr1.length]; int index = 0; for(int i =0;i<arr1.length;i++){ arr[arr1[i]]+=1; } for(int i = 0;i<arr2.length;i++){ while

随机推荐