求职Leetcode题目（16）

1.同构字符串

解题思路1：

egg 和 add 同构，就意味着下边的映射成立
e -> a
g -> d

也就是将 egg 的 e 换成 a, g 换成 d, 就变成了 add

同时倒过来也成立
a -> e
d -> g

也就是将 add 的 a 换成 e, d 换成 g, 就变成了 egg

foo 和 bar 不同构，原因就是映射不唯一
o -> a
o -> r
其中 o 映射到了两个字母

 代码：

class Solution {public boolean isIsomorphic(String s, String t) {int n =s.length();HashMap<Character,Character> map =new HashMap<>();for(int i =0;i<n;i++){char c1 =s.charAt(i);char c2 =s.charAt(i);if(map.containsKey(c1)){if(map.get(c1)!=c2){return false;}}else{map.put(c1,c2);}}return true;}
}

 思路2：

将第一个出现的字母映射成 1，第二个出现的字母映射成 2

对于 egg
e -> 1
g -> 2
也就是将 egg 的 e 换成 1, g 换成 2, 就变成了 122

对于 add
a -> 1
d -> 2
也就是将 add 的 a 换成 1, d 换成 2, 就变成了 122

egg -> 122, add -> 122
都变成了 122，所以两个字符串异构。

代码：

public boolean isIsomorphic(String s, String t) {return isIsomorphicHelper(s).equals(isIsomorphicHelper(t));
}private String isIsomorphicHelper(String s) {int[] map = new int[128];int n = s.length();StringBuilder sb = new StringBuilder();int count = 1;for (int i = 0; i < n; i++) {char c = s.charAt(i);//当前字母第一次出现,赋值if (map[c] == 0) {map[c] = count;count++;}sb.append(map[c]);}return sb.toString();
}

2.移除链表元素

解题思路：

1. 删除头结点时另做考虑（由于头结点没有前一个结点）
2. 添加一个虚拟头结点，删除头结点就不用另做考虑
3. 递归

 代码：

/*** 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) {//删除值相同的头节点后，可能新的头结点也值相等，用循环解决while(head!=null&&head.val==val){head=head.next;}if(head==null){return head;}ListNode prev =head;//确保当前节点后还有结点while(prev.next!=null){if(prev.next.val==val){prev.next=prev.next.next;}else{prev=prev.next;}}return 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 removeElements(ListNode head, int val) {if(head==null)return null;head.next =removeElements(head.next,val);if(head.val==val){return head.next;}else{return head;}}}

3.长度最小的子数组

（暴力）代码： 

class Solution {public int minSubArrayLen(int s, int[] nums) {int min = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {int sum = nums[i];if (sum >= s)return 1;for (int j = i + 1; j < nums.length; j++) {sum += nums[j];if (sum >= s) {min = Math.min(min, j - i + 1);break;}}}return min == Integer.MAX_VALUE ? 0 : min;}
}

解题思路2： 

 代码：

class Solution {public int minSubArrayLen(int s, int[] nums) {int lo =0,hi=0,sum=0,min =Integer.MAX_VALUE;while(hi<nums.length){sum+=nums[hi++];while(sum>=s){min=Math.min(min,hi-lo);sum-=nums[lo++];}}return min ==Integer.MAX_VALUE?0:min;}
}