剑指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 Solution {
   public ListNode removeElements(ListNode head, int val) {
       ListNode q = new ListNode(-1);
       ListNode a = q;
       q.next = head;
       while(q.next!=null){
           if(q.next.val==val){
               q.next = q.next.next;
           }else{
               q = q.next;
           }
       }
       return a.next;
   }
}

题目二

字符串题——判断同构字符串

根据给定的字符串判断他们是否为同构字符串

具体题目如下

解法

class Solution {
   public boolean isIsomorphic(String s, String t) {
       if(s.length()!=t.length()){
           return false;
       }
       for(int i =0;i<s.length();i++){
           if(s.indexOf(s.charAt(i))!=t.indexOf(t.charAt(i))){
               return false;
           }
       }
       return true;
   }
}

题目三

链表题&mdash;&mdash;操作链表

编写函数来删除某个单链表中指定的节点

具体题目如下

解法

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public void deleteNode(ListNode node) {
       node.val = node.next.val;
       node.next = node.next.next;
   }
}

题目四

字符串题&mdash;&mdash;判断异位词

编写函数来判断给定的两个字符串是否为字母异位词

具体题目如下

解法

class Solution {
   public boolean isAnagram(String s, String t) {
       if(s.length()!=t.length()) return false;
       ArrayList<Character> list1 = new ArrayList<>();
       ArrayList<Character> list2 = new ArrayList<>();
       for (int i = 0; i < s.length(); i++) {
           list1.add(s.charAt(i));
       }

for (int i = 0; i < t.length(); i++) {
           list2.add(t.charAt(i));
       }
       Collections.sort(list1);
       Collections.sort(list2);
       for (int i = 0; i < list1.size(); i++) {
           if (list1.get(i)!=list2.get(i)) return false;
       }
       return true;
   }
}

//要熟悉API
class Solution {
   public boolean isAnagram(String s, String t) {
       if (s.length() != t.length()) {
           return false;
       }
       char[] str1 = s.toCharArray();
       char[] str2 = t.toCharArray();
       Arrays.sort(str1);
       Arrays.sort(str2);
       return Arrays.equals(str1, str2);
   }
}

题目五

数组题&mdash;&mdash;查找数组

根据给定的数组按照指定条件查找数组中是否包含指定值

具体题目如下

解法

class Solution {
   public int missingNumber(int[] nums) {
       Arrays.sort(nums);
       for (int i = 0; i < nums.length; i++) {
           if(i!=nums[i]){
               return i;
           }
       }
       return nums.length;
   }
}

题目六

字符串题&mdash;&mdash;验证字符串

验证给定的字符串是否遵循相同的规律

具体题目如下

解法

class Solution {
   public boolean wordPattern(String pattern, String s) {
       String[] split = s.split(" ");
       if(split.length!=pattern.length()) return false;
       int q = 0;
       for(int i =0;i<split.length;i++){
          l: for(int w = 0;w<split.length;w++){
               if(split[w].equals(split[i])){
                  q = w;
                  break l;
               }
           }
           if(pattern.indexOf(pattern.charAt(i))!=q){
               return false;
           }
       }
       return true;
   }
}

来源：https://blog.csdn.net/wai_58934/article/details/123153850