LeetCode_easy_中文解析50题_day02

20、Valid Parentheses

六、题目：

给定一个只包含字符 '(' ， ')' ， '{' ， '}' ，'['  和  ']'  的字符串，确定这个字符串左括号和右括号是否匹配

如果输入字符串有效：

• 必须使用相同类型的括号关闭左括号。
• 必须以正确的顺序关闭打开括号。

思想：

先用一个map以键值对的形式存储左括号和右括号，遍历每一次取到的括号，如果是左括号放进栈中，如果是右括号，那就匹配栈顶的左括号，如果匹配上，就弹出栈顶的左括号，否则那就是不匹配，就不是有效的括号开闭。注意，栈中只放左括号，右括号只是为了匹配左括号，然后选择是否弹出左括号。

Example 1:

Input: "()"
Output: true
           

Example 2:

Input: "()[]{}"
Output: true
           

Example 3:

Input: "(]"
Output: false
           

Example 4:

Input: "([)]"
Output: false
           

Example 5:

Input: "{[]}"
Output: true
           

package cn.hnu.leetcode.easy;

import java.util.HashMap;
import java.util.Stack;

public class _020_IsValid {
	public boolean isValid(String s) {
		
                //以键值对的形式存储左右括号
		HashMap<Character,Character> map = new HashMap<Character,Character>();
		
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');
		
		Stack<Character> stack = new Stack<Character>();
		
		for(int i = 0;i<s.length();i++){
			
			//获取当前遍历的括号
			char element = s.charAt(i);
			
			//如果是左括号放进栈中
			if(map.keySet().contains(element)){
				stack.push(element);
			
			//如果是右括号，那就跟栈里的左括号匹配，如果匹配就弹出左括号
			}else if(map.values().contains(element)){
				
				//栈不为空才能peek；
				if(!stack.isEmpty()&&map.get(stack.peek())==element){
					stack.pop();
				//当前栈为空，没有左括号与相应的右括号匹配，就直接返回false
				}else{
					return false;
				}
			}
			
		}
		
		return stack.isEmpty();
	}
}
           

21、Merge Two Sorted Lists

七、题目：

合并两个已排序的链表并将其作为新链表返回，新链表也是有序的。

思想：

首先看链表是否为空，如果两个链表都为空，就直接返回null；如果两个之一为空，返回不空的链表；如果两个链表都不为空，那么就依次比较两个链表对应位置的，详细见代码，注意移位的操作。

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
           

package cn.hnu.leetcode.easy;

class ListNode{
	int val;
	ListNode next;
	
	ListNode(int x){ 
		val = x;
	}
}

public class _021_MergeTwoLists {

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		
		//如果两个链表都为空
		if(l1==null&&l2==null){
			return null;
		}
		
		//如果两个链表有一个为空
		if(l1==null||l2==null){
			return l1==null? l2:l1;
		}
		
		//设置一个链表头,第一个元素就是0
		ListNode head = new ListNode(0);
		
		//相当于用一个指针指向链表头,那么在对head操作的时候,cur始终指向head链表头部
		ListNode cur = head;
		
		//如果两个链表都不为空
		while(l1!=null&&l2!=null){
			
			if(l1.val<l2.val){
                                //head的下一个节点就是L1当前节点位置的值
				head.next = new ListNode(l1.val);
				//l1链表向后移一位
				l1 = l1.next;
				
			}else{
				//head的下一个节点就是L2当前节点位置的值
				head.next = new ListNode(l2.val);
                                //l2链表向后移一位
				l2 = l2.next;
				
			}
			
			//head链表向后移一位
			head = head.next;
		}// end while
		
		//可能两个链表一长一短,就把最后哪个剩下的一段放在head链表后面
		if(l1!=null){
			head.next = l1;
		}
		
		if(l2!=null){
			head.next = l2;
		}
		
		//返回结果,head链表的第1节点我们不要,从它的第2节点开始
		return cur.next;
		
    }
}
           

26、Remove Duplicates from Sorted Array

八、题目：

给定一个排好序的整数数组，不允许使用另一个数组存储变量，直接在原数组上修改，问这个数组中不重复的元素有多少个。

思想：

使用一个index指向数组的第一个元素，从数组的第二个元素开始遍历，如果遍历到的元素不等于index指向的元素，那么就将index+1，指向下一个元素，并将遍历到的元素的值直接赋值给index指向的元素。详见代码

Example 1:

Given nums = [1,1,2],
Your function should return length = 2
           

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5；
           

package cn.hnu.leetcode.easy;

public class _26_RemoveDuplicates {
	public int removeDuplicates(int[] nums) {
		//index开始指向数组的第0个元素
		int index = 0;
		
		//从数组的第2个元素开始遍历
		for(int i = 1;i<nums.length;i++){
			
			//如果当前遍历的元素和index指向的元素不同
			if(nums[i]!=nums[index]){
				//index向后移一位
				index++;
				
				//将遍历到的元素直接赋值给index指向的元素
				nums[index] = nums[i];
			}
		}
		
		//index是从0开始,那么想知道不重复的元素有多少个,还需要+1
		/**
		 * [0,0,1,1,1,2,2,3,3,4],
		 * 最终数组变成
		 * [0,1,2,3,4,2,2,3,3,4]
		 *          |
		 *        index
		 */
		return index+1;
	}
}
           

27、Remove Element

九、题目：

给定数组nums和值val，在适当位置删除val值的所有实例并返回新数组的长度。不要为另一个数组分配额外的空间，必须通过使用O（1）额外内存修改输入数组来实现此目的。元素的顺序可以改变。 最终留下的新长度并不重要。

思想：

同上一题，使用一个index指向数组的第一个位置，从数组的开始遍历，遇到要删除的val不管，遇到跟val不相同的元素，直接覆盖index指向的位置，然后index向后移一位，最终的index的值就是不重复数组的长度。

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2
           

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5
           

package cn.hnu.leetcode.easy;

public class _027_RemoveElement {
	public int removeElement(int[] nums, int val) {
		
		//同26、Remove Duplicates from Sorted Array
		
		//定义一个指针指向数组的第一个元素
		int index = 0;
		
		//不断用不删除的元素进行一个一个覆盖，最终看index在哪里
		//从数组的开始元素遍历
		for(int i = 0;i<nums.length;i++){
			
			//遍历到的元素 不等于 目标删除元素val
			if(nums[i]!=val){
				//直接把遍历到的元素赋值给index指向的位置
				//然后index向后移一位
				nums[index++] = nums[i];
			}
		}
		
	/**
	 * [3,2,2,3] 3
	 * [2,2,2,3]
	 *      |
	 *    index (它有一个后移的操作，出if循环的时候有个+1的操作)
     */
		return index;
	        
	}
}
           

28、Implement strStr()

十、题目：

给定一个字符串haystack和目标字符串needle，返回needle字符串出现在haystack字符串的位置，如果haystack中不包含needle子串则返回-1；当needle为空字符串时，也返回0。

思想：

从haystack字符串的首位置开始以needle字符串长度截取子串target，然后用equals方法比较target和needle是否相同，如果相同返回遍历的位置；详见代码

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
           

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
           

package cn.hnu.leetcode.easy;

public class _028_StrStr {
	
	public int strStr(String haystack, String needle) {
		
		//如果needle的长度为0或者needle为空,就直接返回0
		if(needle.length()==0||needle==null){
			return 0;
		}
		
		//如果haystack的长度小于needle,那也就不用找了,直接返回-1
		if(haystack.length()<needle.length()){
			return -1;
		}
		
		//needle的长度
		int len = needle.length();
		/**
		 * 从haystack的首位置开始,以len长度截取字符串haystack的子串
		 * 为什么是haystack.length()-needle.length()+1？
		 * 把needle的尾部和haystack的尾部对齐就知道,如果错位了,没必要比较吧！
		 * hello   ---  haystack
		 *    ll   ---  needle
		 * 
		 */
		for(int i = 0;i<haystack.length()-needle.length()+1;i++){
			
			String target = haystack.substring(i, i+len);
			
			//如果子串和needle相同,就返回i
			if(target.equals(needle)){
				return i;
			}
		}
		
		//循环结束没有找到,就返回-1
		return -1;
	}
}