快捷導(dǎo)航

劍指Offer之Java算法習(xí)題精講鏈表與數(shù)組專(zhuān)項(xiàng)訓(xùn)練

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

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

題目一

數(shù)組題——查找目標(biāo)值

在給定的數(shù)組中查找指定的目標(biāo)值，這里提供兩種解法

具體題目如下

解法一

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

題目二

數(shù)組題——查找三元組

查找給定的數(shù)組中是否存在指定的三個(gè)元素并使得該三個(gè)元素相加等于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;
    }
}

題目三

數(shù)組題——查找四元組

查找給定的數(shù)組中滿足條件的四元組

具體題目如下

解法

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

模板理解背下來(lái)~

題目四

鏈表題——反轉(zhuǎn)鏈表

根據(jù)單鏈表的頭節(jié)點(diǎn)head來(lái)返回反轉(zhuǎn)后的鏈表

具體題目如下

解法

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

題目五

鏈表題——反轉(zhuǎn)鏈表

根據(jù)單鏈表的頭節(jié)點(diǎn)head和指定條件來(lái)返回反轉(zhuǎn)后的鏈表

具體題目如下

解法

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

到此這篇關(guān)于劍指Offer之Java算法習(xí)題精講鏈表與數(shù)組專(zhuān)項(xiàng)訓(xùn)練的文章就介紹到這了,更多相關(guān)Java 鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: