剑指Offer之Java算法习题精讲数组查找与字符串交集
题目一
数组题——二分查找法
写一个函数查找给定的数组中指定的数值
具体题目如下
解法
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left<=right){
int mid = left+(right-left)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid + 1;
}
}
return -1;
}
}
题目二
数组题——查找数组中元素位置
根据给定的数组按照指定条件查找首尾元素位置
具体题目如下
解法：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = {-1,-1};
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = left+(right-left)/2;
if(nums[mid] == target){
res[0] = mid;
right = mid-1;
}else if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid+1;
}
}
left = 0;
right = nums.length-1;
while(left<=right){
int mid = left+(right-left)/2;
if(nums[mid] == target){
res[1] = mid;
left = mid+1;
}else if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid+1;
}
}
return res;
}
}
题目三
字符串题——查找字符串交集
根据给定的字符串按照指定条件查找一个字符串所涵盖的另一个字符串字符的最小子串
具体题目如下
解法
class Solution {
public String minWindow(String s, String t) {
if(s == null || s == "" || t == null || t == "" || s.length() < t.length()){
return "";
}
int[] need = new int[128];
int[] have = new int[128];
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
int left = 0, right = 0;
int min = s.length() + 1, count = 0, start = 0;
while (right < s.length()){
char r = s.charAt(right);
if (need[r] == 0) {
right++;
continue;
}
if (have[r] < need[r]) {
count++;
}
have[r]++;
right++;
while (count == t.length()){
if (right - left < min) {
min = right - left;
start = left;
}
char l = s.charAt(left);
if (need[l] == 0) {
left++;
continue;
}
if (have[l] == need[l]) {
count--;
}
have[l]--;
left++;
}
}
if (min == s.length() + 1) {
return "";
}
return s.substring(start, start + min);
}
}
到此这篇关于剑指Offer之Java算法习题精讲数组查找与字符串交集的文章就介绍到这了,更多相关Java 数组查找内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
剑指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算法习题精讲链表与二叉树专项训练
题目一 链表题——反转链表 根据单链表的头节点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 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算法习题精讲字符串与二叉搜索树
题目一 解法 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算法习题精讲链表与数组专项训练
题目一 数组题——查找目标值 在给定的数组中查找指定的目标值,这里提供两种解法 具体题目如下 解法一 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算法习题精讲二叉树专项训练
题目一 解法 /** * 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 search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left<=right){ int mid = left+(right-left)/2; if(nums[mid]==target){ return mid; }else if(nums[m
-
剑指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
-
剑指Offer之Java算法习题精讲数组与列表的查找及字符串转换
题目一 解法 class Solution { public String toLowerCase(String s) { StringBuilder sb = new StringBuilder(); for(int i = 0;i<s.length();i++){ char ch = s.charAt(i); if('A'<=ch&&ch<='Z'){ ch = (char)(ch+32); } sb.append(ch); } return sb.toString(
-
剑指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算法习题精讲链表专题篇
题目一 解法 /** * 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算法习题精讲二叉树与斐波那契函数
题目一 解法 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; *