Likou second week wrong questions collection

Force in the second week of some wrong topic and personal understanding

• LeetCode232：用栈实现队列
• LeetCode278：第一个错误的版本
• LeetCode383：赎金信
• LeetCode70：爬楼梯
• LeetCode409：最长回文串
• LeetCode206：反转链表
• LeetCode169：多数元素
• LeetCode67：二进制求和
• LeetCode543：二叉树的直径
• LeetCode876：链表的中间结点
• LeetCode104：二叉树的最大深度
• LeetCode217：存在重复元素

LeetCode232：用栈实现队列
解法一：The operation of the stack is used to implement a queue,需要用到两个栈,一个是输出栈,一个是输入栈,再进行相应的操作

class MyQueue {
    
    private Stack<Integer> a;//输入栈
    private Stack<Integer> b;//输出栈
    public MyQueue() {
    
        a = new Stack<>();
        b = new Stack<>();     
    }
    
    public void push(int x) {
    
        a.push(x);
    }
    
    public int pop() {
    
        //如果b栈为空,则将a栈全部弹出并压入b栈中,然后b.pop()
        if(b.isEmpty()){
    
            while(!a.isEmpty()){
    
                b.push(a.pop());
            }
        }
        return b.pop();
    }
    
    public int peek() {
    
        if(b.isEmpty()){
    
            while(!a.isEmpty()){
    
                b.push(a.pop());
            }
        }
        return b.peek();
    }
    
    public boolean empty() {
    
        return a.isEmpty() && b.isEmpty();
    }
}

LeetCode278：第一个错误的版本
解法一：Through the dichotomy found the wrong version of corresponding,Direct violence find version will be very slow when too much

public class Solution extends VersionControl {
    
    public int firstBadVersion(int n) {
    
        if (n < 1) {
    
            return -1;
        }
        int left = 1;
        int right = n;
        int res = -1;
        while(left <= right){
    
            int mid =left + ((right - left) >> 1);
            if(isBadVersion(mid)){
    
                right = mid - 1;
                res = mid;
            }else {
    
                left = mid + 1;
            }
        }
        return res;
    }
}

LeetCode383：赎金信
解法一：Record the occurrence of each letters in a string number,Then take another string traversal compare them one by one

class Solution {
    
    public boolean canConstruct(String ransomNote, String magazine) {
    
        //记录杂志字符串出现的次数
        int[] arr=new int[26];
        int temp;
        for(int i=0;i<magazine.length();i++){
    
            temp = magazine.charAt(i) - 'a';
            arr[temp]++;
        }
        for(int i=0;i<ransomNote.length();i++){
    
            temp = ransomNote.charAt(i) - 'a';
            //对于金信中的每一个字符都在数组中查找
            //找到相应位减一,否则找不到返回false
            if(arr[temp]>0){
    
                arr[temp]--;
            }else{
    
                return false;
            }
        }
        return true;
    }
}

• temp = magazine.charAt(i) - ‘a’;The letter minus’a’Can get the letter subscript serial number（The corresponding index of letters）
• arr[temp]++;To record the letters(个)数

LeetCode70：爬楼梯
解法一：
1.确定dp数组以及下标的含义;
dp[i]：爬到第i层楼梯,有dp[i]种方法
2.确定递推公式
从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来.
首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么.
还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么.
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] .
在推导dp[i]的时候,一定要时刻想着dp[i]的定义,否则容易跑偏.
这体现出确定dp数组以及下标的含义的重要性！
3.dp[]数组的初始化
4.Determine traversal recursive
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的
5.举例推导dp[]数组

class Solution {
    
    public int climbStairs(int n) {
    
        // if(n <= 2) return n;
        // int a=1,b=2 ,sum=0;

        // for(int i=3;i<=n;i++){
    
        // sum = a+b;
        // a = b;
        // b = sum;
        // }
        // return b;
        int[] dp=new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i<=n;i++){
    
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

LeetCode409：最长回文串
解法一：Put the number of characters appear in the character array to,And then the array of traverse a number,Create a new record in the length ofans,Traversed if is even added directly,为奇数时ans就+1,Finally returned to the generalans

class Solution {
    
    public int longestPalindrome(String s) {
    
        // StringBuffer sb = new StringBuffer();
         int count[] = new int[128];
        for (char c : s.toCharArray()) {
    
            count[c]++;
        }
        int ans = 0;
        for (int v : count) {
    
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
    
                ans++;
            }
        }
        return ans;
    }
}

LeetCode206：反转链表
解法一：Create a new pointer or a pointer to the current node before,然后每次循环,都将当前节点指向它前面的节点,然后当前节点和前节点后移

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode prev = null;//前指针结点
        ListNode curr = head;//The current cursor node
        //每次循环,都将当前节点指向它前面的节点,然后当前节点和前节点后移
        while(curr != null){
    
            ListNode nextTemp = curr.next; //临时节点,暂存当前节点的下一节点,用于后移
            curr.next = prev;//将当前节点指向它前面的节点
            prev = curr;//前指针后移
            curr = nextTemp;//当前指针后移
        }
        return prev;
    }
}

LeetCode169：多数元素
解法一：从第一个数开始count=1,遇到相同的就加1,遇到不同的就减1,减到0就重新换个数开始计数,总能找到最多的那个

class Solution {
    
    public int majorityElement(int[] nums) {
    
        int count = 1;
        int maj = nums[0];
        for(int i = 1;i < nums.length; i++){
    
            if(maj == nums[i]){
    
                count++;
            }else{
    
                count--;
                if(count == 0){
    
                    maj = nums[i+1];
                }
            }
        }
        return maj;
    }
}

LeetCode67：二进制求和

class Solution {
    
    public String addBinary(String a, String b) {
    
        if(a == null || a.length() == 0) return b;
        if(b == null || b.length() == 0) return a;

        StringBuffer stb=new StringBuffer();
        int i= a.length() - 1;
        int j= b.length() - 1;

        int c = 0; //进位
        while(i>=0 || j>=0){
    
            if(i >=0) c+=a.charAt(i --) - '0';
            if(j >=0) c+=b.charAt(j --) - '0';
            stb.append(c%2);
            c>>=1;
        }

        String res = stb.reverse().toString();
        return c > 0 ? '1' + res : res;
    }
}

LeetCode543：二叉树的直径

class Solution {
    
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
    
        if(root == null){
    
            return 0;
        }
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root){
    
        if(root.left == null && root.right == null){
    
            return 0;
        }
        int leftSize = root.left == null?0:dfs(root.left) + 1;
        int rightSize = root.right ==null?0:dfs(root.right) + 1;
        max = Math.max(max,leftSize+rightSize);
        return Math.max(leftSize,rightSize);
    }
}

LeetCode876：链表的中间结点
解法一：快慢指针,slow 一次走一步,fast 一次走两步.那么当 fast 到达链表的末尾时,slow 必然位于中间.

class Solution {
    
    public ListNode middleNode(ListNode head) {
    
        ListNode p = head;
        ListNode q = head;
        while(q!=null && q.next!=null){
    
            q=q.next.next;
            p=p.next;
        }
        return p;
    }
}

LeetCode104：二叉树的最大深度

class Solution {
    
    public int maxDepth(TreeNode root) {
    
        //深度优先
        if (root == null) {
    
            return 0;
        } else {
    
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }

        //广度优先
           if (root == null) {
    
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            while (size > 0) {
    
                TreeNode node = queue.poll();
                if (node.left != null) {
    
                    queue.offer(node.left);
                }
                if (node.right != null) {
    
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }
}

LeetCode217：存在重复元素
解法一：利用set的特性,不能存储重复的元素

class Solution {
    
    public boolean containsDuplicate(int[] nums) {
    
        Set<Integer> set=new HashSet<Integer>();
        for(int num : nums){
    

            if(set.add(num) == false){
    
                return true;
            }
        }
        return false;
    }
}