剑指offer:50-53记录

举报
兔老大 发表于 2021/04/24 00:20:59 2021/04/24
【摘要】 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 示例: s = "abaccdeff" 返回 "b" s = ""  返回 " "   限制: 0 <= s 的长度 <= 50000 思路:map记录次数,再次遍历找出次数1的。 class Solution { public char firstUniqC...

在字符串 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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。