剑指offer：50-53记录
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。
示例:
s = "abaccdeff"
返回 "b"
s = ""
返回 " "
限制：
0 <= s 的长度 <= 50000
思路：map记录次数，再次遍历找出次数1的。
-
class Solution {
-
public char firstUniqChar(String s) {
-
// 哈希表存储，<字符，出现次数>
-
Map<Character,Integer> map=new HashMap<>();
-
for(int i=0;i<s.length();i++){
-
if(map.containsKey(s.charAt(i))){
-
map.put(s.charAt(i),map.get(s.charAt(i))+1);
-
}else{
-
map.put(s.charAt(i),1);
-
}
-
}
-
//顺序判断，只要找到第一个出现次数为1的就返回
-
for(int i=0;i<s.length();i++){
-
if(map.get(s.charAt(i))==1)
-
return s.charAt(i);
-
}
-
return ' ';
-
}
-
}
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
归并加一句统计。
-
class Solution {
-
-
private int res;
-
-
public int reversePairs(int[] nums) {
-
if (nums == null || nums.length < 1) {
-
return 0;
-
}
-
mergeSort(nums, 0, nums.length - 1);
-
return res;
-
}
-
-
private void mergeSort(int[] arr, int left, int right) {
-
if (left == right) {
-
return;
-
}
-
int mid = (left + right) >>> 1;
-
mergeSort(arr, left, mid);
-
mergeSort(arr, mid + 1, right);
-
merge(arr, left, mid, right);
-
}
-
-
private void merge(int[] arr, int left, int mid, int right) {
-
int[] temp = new int[right - left + 1];
-
int i = left, j = mid + 1, index = 0;
-
while (i <= mid && j <= right) {
-
if (arr[i] <= arr[j]) {
-
temp[index++] = arr[i++];
-
} else {
-
temp[index++] = arr[j++];
-
//加一句
-
res += mid - i + 1;
-
}
-
}
-
while (i <= mid) {
-
temp[index++] = arr[i++];
-
}
-
while (j <= right) {
-
temp[index++] = arr[j++];
-
}
-
System.arraycopy(temp, 0, arr, left, temp.length);
-
}
-
}
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
思路：先都走到最后，顺便统计长度。
结尾不一样就肯定没有相交，返回。
然后让长的先几步，走到一样长了再一起往前走，相遇就找到了。
-
/**
-
* Definition for singly-linked list.
-
* public class ListNode {
-
* int val;
-
* ListNode next;
-
* ListNode(int x) {
-
* val = x;
-
* next = null;
-
* }
-
* }
-
*/
-
public class Solution {
-
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
-
if(headB==null || headA==null){
-
return null;
-
}
-
ListNode tempA=headA;
-
ListNode tempB=headB;
-
int a=0;
-
int b=0;
-
while(tempA.next!=null){
-
tempA=tempA.next;
-
a++;
-
}
-
while(tempB.next!=null){
-
tempB=tempB.next;
-
b++;
-
}
-
if(tempB!=tempA){
-
return null;
-
}
-
tempA=headA;
-
tempB=headB;
-
if(a>b){
-
for(int i=0;i<a-b;i++){
-
tempA=tempA.next;
-
}
-
}else{
-
for(int i=0;i<b-a;i++){
-
tempB=tempB.next;
-
}
-
}
-
while(tempB!=tempA){
-
tempA=tempA.next;
-
tempB=tempB.next;
-
}
-
return tempA;
-
-
}
-
}
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
限制：
0 <= 数组长度 <= 50000
思路：两次二分，稍微修改一下查最左或最右。最后相减即可。
-
class Solution {
-
public int search(int[] nums, int target) {
-
int left=searchRangeLeft(nums,target);
-
int right=searchRangeRight(nums,target);
-
if(left==-1)return 0;
-
return right-left+1;
-
}
-
public int searchRangeLeft(int[] nums, int target) {
-
int left=0;
-
int right=nums.length-1;
-
while(left<=right){
-
int mid=(left+right)/2;
-
if(nums[mid]>target){
-
right=mid-1;
-
}else if(nums[mid]<target){
-
left=mid+1;
-
}else if(mid==0 || nums[mid-1]!=target){
-
return mid;
-
}else{
-
right=mid-1;
-
}
-
}
-
return -1;
-
}
-
public int searchRangeRight(int[] nums, int target) {
-
int left=0;
-
int right=nums.length-1;
-
while(left<=right){
-
int mid=(left+right)/2;
-
if(nums[mid]>target){
-
right=mid-1;
-
}else if(nums[mid]<target){
-
left=mid+1;
-
}else if(mid==nums.length-1 || nums[mid+1]!=target){
-
return mid;
-
}else{
-
left=mid+1;
-
}
-
}
-
return -1;
-
}
-
}
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：
1 <= 数组长度 <= 10000
思路1：异或，就一个没出现的剩下了，别的两两抵消了。
-
class Solution {
-
public int missingNumber(int[] nums) {
-
int res=nums.length;
-
for(int i=0;i<nums.length;i++){
-
res^=nums[i];
-
res^=i;
-
}
-
return res;
-
}
-
}
思路2：二分，条件就是值是否等于下标。
-
class Solution {
-
public int missingNumber(int[] nums) {
-
int left = 0;
-
int right = nums.length-1;
-
while(left<=right){
-
int mid = (left+right) / 2;
-
if(nums[mid]!=mid) right = mid -1;
-
else left = mid + 1;
-
}
-
return left;
-
}
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/104777859
- 点赞
- 收藏
- 关注作者
评论（0）