剑指Offer之Java算法习题精讲链表与数组专项训练
时间：2022-11-01 09:19:41 | 栏目：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;
}
}