蓝桥杯刷题JAVA（2）

1. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0)
        return "";
        int index = 0;
        String result = "";
        int sc = 0;
        for(int p = 1; p < strs.length; p++)
            if(strs[p].length() < strs[index].length())
                index = p;

        for(int j = 0; j < strs[index].length(); j++){
            int flag = 1;
            for(int i = 0; i < strs.length; i++)
                if(strs[i].charAt(j) != strs[index].charAt(j)){
                    flag = 0;
                    break;
                }

            if(flag == 0)
                return result;
            else{
                result = result.concat(strs[index].substring(sc, sc+1));
                sc++;
            }
                
        }
        return result;
    }
}

经验：
String的substring是前闭后开的。String的大部分方法需要熟悉，对象方法大小写有些玄学，没有api的时候容易出错。

2. 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        hashMap.put('(', 1);
        hashMap.put('[', 2);
        hashMap.put('{', 3);
        hashMap.put(')', 4);
        hashMap.put(']', 5);
        hashMap.put('}', 6);
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < s.length(); i++) {
        	if(stack.empty())
        		stack.push(hashMap.get(s.charAt(i)));
        	else {
        		int peek = stack.peek();
            	if(hashMap.get(s.charAt(i)) <= 3)
            		stack.push(hashMap.get(s.charAt(i)));
            	else if(hashMap.get(s.charAt(i)) - 3 == peek)
            		stack.pop();
            	else
            		return false;
			}
        }
        if(stack.empty())
        	return true;
        else
        	return false;
    }
}

经验：
快乐堆栈，快乐哈希，一遍AC。

3. 合并有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 1. Definition for singly-linked list.
 2. public class ListNode {
 3.     int val;
 4.     ListNode next;
 5.     ListNode() {}
 6.     ListNode(int val) { this.val = val; }
 7.     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 8. }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode temp = result;
        while(l1 != null && l2 != null){
        	if(l1.val > l2.val){
        		result.next = l2;
        		result = result.next;
                l2 = l2.next;
            }else{
            	result.next = l1;
                result = result.next;
                l1 = l1.next;
            }
        }
        if(l1 == null)
            result.next = l2;
        else
            result.next = l1;
        return temp.next;
    }
}

经验：
憨憨地弄错了好多回，链表链接的逻辑弄混淆了，可以用一个临时头把他们串联起来，最后返回的时候把头去掉直接取next即可。
4. 删除有序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0)
            return 0;
        int flag = -1111;
        int length = 0;
        int numlength = nums.length;
        int tag = 1;
        for(int i = 0; i < numlength;i++){
            while(nums[i] == flag && i < numlength){
            	tag = 0;
                for(int j = i; j < numlength - 1; j++) {
                	nums[j] = nums[j + 1];
                	tag = 1;
                } 
                numlength--;
            }
            if(tag == 1) {
            	flag = nums[i];
                length++;
            }
        }
        return length;
    }
}

//双指针解法
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0)
            return 0;
        if(nums.length == 1)
            return 1;

        int length = 0;
        int index = 1;
        while(index < nums.length)
            if(nums[length] == nums[index])
                index++;
            else
                nums[++length] = nums[index++];
        return length + 1;
    }
}

经验：java的长度不可变数组在这种题目里灰常难受。。双指针思想会方便很多。