劍指Offer之Java算法習題精講鏈表與數組專項訓練

更新時間：2022年03月22日 09:00:25 作者：明天一定.

跟著思路走，之后從簡單題入手，反復去看，做過之后可能會忘記，之后再做一次，記不住就反復做，反復尋求思路和規(guī)律，慢慢積累就會發(fā)現質的變化

題目一

數組題——查找目標值

在給定的數組中查找指定的目標值，這里提供兩種解法

具體題目如下

解法一

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;
    }    
}

模板理解背下來~

題目四

鏈表題——反轉鏈表

根據單鏈表的頭節(jié)點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;
    }
}

題目五

鏈表題——反轉鏈表

根據單鏈表的頭節(jié)點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 鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: