[数据结构与算法]每日＞...＜LeetCode练习

LeetCode 160

public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
     ListNode l1=headA;	//用l1，l2两个结点记录headA，headB，便于编写
     ListNode l2=headB;
     while(l1!=l2){			
         l1=(l1==null)?headB:l1.next;	//当两个链表结点不为空时，都向后走
         l2=(l2==null)?headA:l2.next;	//到链表尾部时，就从另一个链表的头部又开始走
     }
      //两个结点这样走，总会有一时刻，使得l1==l2，此时退出循环，此结点为相交结点  
     return l1;
      
    }
}

LeetCode206

该递归过程在此不做详解，我会在另一篇博客中作出一定的分析?JAVA巨精简递归小谈＞__＜_m0_60010936的博客-CSDN博客

LeetCode206

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 Solution1 {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){  //递归结束条件
            return head;		  //结束即（"递"的过程已结束）
        }					
        ListNode next=head.next;
        ListNode newHead=reverseList(next);
        next.next=head;//递的过程结束，跳到此处，开始进行"归"的过程
        head.next=null;
        return newHead;//返回新头结点			
    }
}

LeetCode 844

public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        //skip记录两个字符串中的"#"
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                //遇到字符是#
                if (S.charAt(i) == '#') {
                    skipS++;	//若遇见'#'，skip+1
                    i--;	//从后往前遍历的顺序
                //已经遇到过#,且当前不为#
                } else if (skipS > 0) {
                    skipS--;	//若没有'#'，skip-1
                    i--;	//继续向前遍历
                //没有遇到过#
                } else {	
                    break;	//若没有'#'，即skip==0，退出	
                }
            }
		//与上同理
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }  
            //走到这里是两个字符串中均无'#'，则为false，因为题目要求必有#                       
            if (i >= 0 && j >= 0) {                   
                if (S.charAt(i) != T.charAt(j)) {      
                    return false;                             
                }                            		
            } else {                        		
                if (i >= 0 || j >= 0) {						
                    return false;					
                }						
            }					
            i--;						
            j--;				
        }		
        return true;		
    }							

LeetCode 28：

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;=
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}

?LeetCode 290：

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch2str = new HashMap<Character, String>();
        int m = str.length();
        int i = 0;
        for (int p = 0; p < pattern.length(); ++p) {
            char ch = pattern.charAt(p);
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str.charAt(j) != ' ') { //j走过的时一个完整的词语
                j++
            }					    //遇到' '即跳出
            String tmp = str.substring(i, j);	    //将一个完整的单词赋给tmp	
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;			    //比较字符与串
            }
            if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {
                return false;				//比较
            }
            str2ch.put(tmp, ch);
            ch2str.put(ch, tmp);
            i = j + 1;
        }
        return i >= m;
    }
}