【leetcode】招商银行学习计划经典笔试题（java版本含注释）

前言

将近两年前的学习笔记，由于一直放在草稿箱中，今天将他释放了~~

该学习计划链接如下：
招商银行信用卡的学习计划

以下为我的学习笔记以及汇总，也为了方便其他人更加快速的浏览

这里大部分的题目都是刷过的，本着尽职的态度再次模拟，多刷多刷(#^.#)

个别题目太常见或者顺手就来，博主就不放详细题目，只放链接了

第一天

21. 合并两个有序链表（简单）

题目：leetcode：21. 合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prehead=new ListNode(0);

        ListNode pre=prehead;
        while(list1!=null&&list2!=null){
            if(list1.val>=list2.val){
                pre.next=list2;
                list2=list2.next;
            }else {
                pre.next=list1;
                list1=list1.next;
            }
            pre=pre.next;    
        }

        pre.next=list1==null?list2:list1;
        return prehead.next;//可以直接用这个节点的next返回，不用再创建多一个节点保存了

    }
}

3. 无重复字符的最长子串（中等）

题目：leetcode：3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set=new HashSet<>();
        int rk=-1,sum=0;
        for(int i=0;i<s.length();i++){
            if(i!=0){
                set.remove(s.charAt(i-1));
            }
            while(rk+1<s.length() && !set.contains(s.charAt(rk+1))){
                set.add(s.charAt(rk+1));
                rk++;
            }
            sum=Math.max(sum,rk-i+1);
        }
        return sum;

    }
}

第二天

1. 两数之和（简单）

题目：leetcode：1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
     
    }
}

199. 二叉树的右视图（中等）

题目：leetcode：199. 二叉树的右视图

class Solution {
    
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer>list=new ArrayList<>();
        if(root==null) return list;

        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int n=que.size();
            for(int i=0;i<n;i++){
                TreeNode node=que.poll();
                if(i==n-1)list.add(node.val);
                if(node.left!=null)que.offer(node.left);
                if(node.right!=null)que.offer(node.right);
            }
        }
        return list;
    }
}

124. 二叉树中的最大路径和（困难）

题目：leetcode：124. 二叉树中的最大路径和

要记住返回的值，所以使用后序递归是最合适的了

class Solution {
    int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }   

    public int dfs(TreeNode root){
        if(root ==null)return 0;

        /*  
        int left=dfs(root.left);
        int right=dfs(root.right);
        */


        /* 
          之所以不用上面那个操作主要是，为了保证每一步都是大于0，如果小于0，直接返回0即可  
        */ 
        int left=Math.max(dfs(root.left),0);
        int right=Math.max(dfs(root.right),0);

        //计算左右边界的值，本身已经默认大于0了，所以max比较最大值，在主函数中，返回max比较即可。
        //这和递归的条件不影响，递归只是返回单边最大的值而已，条件不能弄混
        int sum=left+right+root.val;

        max=Math.max(max,sum);

        //确定递归回去的条件，只能返回单边值
        return root.val+Math.max(left,right);


    }
}

第三天

198. 打家劫舍（中等）

题目：leetcode：198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        //因为创建了dp数组，前面两个数组的个数要做一个判断比较
        
        //为空或者长度为0，都返回为0
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n=nums.length;
        //如果数组长为1，则返回第一个
        if (n == 1) {
            return nums[0];
        }
        
        int []dp=new int [n];
        dp[0]=nums[0];
        //返回最大的那个，初始条件如果只有两个房屋，返回最大的那个
        dp[1]=Math.max(nums[0],nums[1]);

        //通过动态规划的公式，相邻两间屋的最大值
        for(int i=2;i<n;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }

        //输出动态规划数组的最后一个值，即可为最大
        return dp[n-1];


    }
}

15. 三数之和（中等）

题目：leetcode：15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list =new ArrayList<List<Integer>>();
        

        int n=nums.length;
        Arrays.sort(nums);
        for(int i=0;i<n-2;i++){//    < nums.length - 2是为了保证后面还能存在两个数字
            
            if(nums[i]>0)break;//大于0，则后面的数字也是大于零（排序后是递增的）
            if(i!=0 && nums[i] == nums[i-1])continue;// 代表第一个值重复了，去重

            int left=i+1;
            int right=n-1;
            while(left<right){
                int sum=nums[left]+nums[right]+nums[i];

                if(sum==0){
                    //创建一个空的列表

                    /*
                    List<Integer>sonlist=new ArrayList<>();
                    sonlist.add(nums[i]);
                    sonlist.add(nums[left]);
                    sonlist.add(nums[right]);
                    
                    list.add(sonlist);
                    */

                    // 将其数组转换为列表，二者选择其一，跟上面的代码
                    list.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    
                    while(left<right && nums[left]==nums[++left]);//左指针前进并去重
                    while(left<right && nums[right] == nums[--right]);//右指针前进并去重

                }else if(sum<0){
                    while(left<right && nums[left]==nums[++left]);//左指针前进并去重
                }else if(sum>0){
                    while(left<right && nums[right] == nums[--right]);//右指针前进并去重
                }
            }
            
        }

        return list;

    }
}

第四天

53. 最大子数组和（简单）

题目：leetcode：53. 最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        
        int n=nums.length;
        int pre=0;
        int max=Integer.MIN_VALUE;
        // 或者使用 int max=nums[0];
        for(int i=0;i<n;i++){
            pre=Math.max(pre+nums[i],nums[i]);
            max=Math.max(pre,max);
        }
        return max;

    }
}

7. 整数反转（中等）*

题目：leetcode：7. 整数反转

大致题目意思是：
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [?231, 231 ? 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

核心代码主要是这一块：

// 弹出 x 的末尾数字 rev
rev = x % 10;
x /= 10;

// 将数字 rev 推入 res 末尾
res = res * 10 + rev;

最主要是数字会溢出，所以数字的判断条件比较关键：

class Solution {
    public int reverse(int x) {

        //返回最后的总数
        int res=0;
        
        while(x!=0){
            
            //因为反转的时候res会慢慢开始越界，所以在此处进行判断 倒数第二个数
            if(res>Integer.MAX_VALUE/10 || res<Integer.MIN_VALUE/10)return 0;

            //求余判断条件
            int rev=x%10;
            //除数判断的条件
            x=x/10;

            res=res*10+rev;
        
        }
        return res;

    }
}

33. 搜索旋转排序数组（中等）*

题目：leetcode：33. 搜索旋转排序数组

class Solution {
    public int search(int[] nums, int target) {

        int n=nums.length;
        int left=0,right=nums.length-1;
        //等于号不要漏掉
        while(left<=right){
            int mid=left+(right-left)/2;
            //不要少掉这个条件
            if(nums[mid]==target)return mid;
            //注意初值条件，左边界此处都是等于号，而且和nums【mid】作比较，target嵌入其中
            if(nums[0]<=nums[mid]){

                if(nums[0]<=target && target<nums[mid]){
                    right=mid-1;
                }else {
                    left=mid+1;
                }

            }else {
                //此处的等于号是在nums【n-1】作比较，
                if(nums[mid]<target && target<=nums[n-1]){
                    left=mid+1;
                }else {
                    right=mid-1;
                }

            }
        }
        //如果循环结束后条件不满足 则返回-1
        return -1;

    }
}

第五天

41. 缺失的第一个正数

题目：leetcode：41. 缺失的第一个正数

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n=nums.length;

        //将其小于等于0的数都变为n+1，因为之后用不到
        for(int i=0;i<n;i++){
            if(nums[i]<=0)nums[i]=n+1;
        }

        // 再一次遍历，类似哈希，将其元素标记在数组下标中
        // 置为负值，为了不让负变正，每次都是取绝对值，在变负，解决上面的疑惑
        for(int i=0;i<n;i++){
            int num=Math.abs(nums[i]);
            //此处判断的数字都是小于等于n的，也就是【1，n】
            if(num<=n)nums[num-1]=-Math.abs(nums[num-1]);
        }

        //如果遇到正数，说明其下标还未被标记，所以是i+1
        for(int i=0;i<n;i++){
            if(nums[i]>0)return i+1;
        }

        //如果没有被标记到，则将其n+1

        return n+1;
    }
}

置换的做法：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n=nums.length;

        //将其数组值对应放到数组下标中
        for(int i=0;i<n;i++){
            //无限在这里置换 只有不等的时候才需要操作置换
            while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){
                int temp=nums[nums[i]-1];
                nums[nums[i]-1]=nums[i];
                nums[i]=temp;
            }
        }

        //类似哈希的存储，如果不等于i+1的时候 就返回第一个正数
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1)return i+1;
        }

        return n+1;
    }
}

20. 有效的括号（简单）*

题目：leetcode：20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        //临界条件 奇数个数排除
        if(s.length()%2!=0)return false;
        
        int n=s.length();
        Map<Character,Character>map=new HashMap<>(){
            {
                //注意此处为put而不是map.put函数
                put(')','(');
                put(']','[');
                put('}','{');
            }
        };
        
        Stack<Character>stack=new Stack<>();

        for(int i=0;i<n;i++){
            //此处的条件是如果包含了这个key，也就是可能栈中有左括号
            if(map.containsKey(s.charAt(i))){
                //判断栈如果为空或者是获取这个节点对应的value中不是等于peek值，说明为false
                //之所以判断false条件是 因为如果不是可以直接返回结果
                if(stack.isEmpty() || map.get(s.charAt(i))!=stack.peek()){
                    return false;
                }
                stack.pop();
            }else{
                //如果没有包含则进栈
                stack.push(s.charAt(i));
            }
        }

        //最后的返回条件是栈是否为空
        return stack.isEmpty();



    }
}

103. 二叉树的锯齿形层序遍历（中等）

题目：leetcode：103. 二叉树的锯齿形层序遍历

class Solution {
    
    
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        List<List<Integer>> list=new ArrayList<List<Integer>>();
        if(root==null) return list;


        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root);
        int ans=0;
        while(!que.isEmpty()){
            int n=que.size();
            List<Integer>sonlist=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode node=que.poll();
                sonlist.add(node.val);
                if(node.left!=null)que.offer(node.left);
                if(node.right!=null)que.offer(node.right);
            }
            ans++;
            if(ans%2==0)Collections.reverse(sonlist);
            list.add(sonlist);
        }
        return list;
        

    }
}

第六天

415. 字符串相加（简单）

题目：leetcode：415. 字符串相加

class Solution {
    public String addStrings(String num1, String num2) {
        int l1=num1.length()-1;
        int l2=num2.length()-1;

        int add=0;
        StringBuilder sb=new StringBuilder();
        while(l1>=0||l2>=0|add!=0){
            //判断格式是这样的
            int x=l1>=0?num1.charAt(l1)-'0':0;
            int y=l2>=0?num2.charAt(l2)-'0':0;
            int sum=x+y+add;

            sb.append(sum%10);
            add=sum/10;
            l1--;
            l2--;
        }

        sb.reverse();
        return sb.toString();
    }
}

64. 最小路径和

题目：leetcode：64. 最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        //初始值判断
        if (grid == null || grid.length == 0||grid[0].length==0) {
            return 0;
        }
        
        int m=grid.length;
        int n=grid[0].length;

        int [][]dp=new int [m][n];
        //赋值一个值，主要用来求边界想加点
        dp[0][0]=grid[0][0];
        
        //边界处理
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //需求最小的边界，而且是邻接边
                dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }

        return dp[m-1][n-1];

    }
}

第六天

88. 合并两个有序数组（简单）

题目：leetcode：88. 合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        //逆序存放主要是不会被覆盖
        //a b都是有效数组下标开始
        int a = m - 1, b = n - 1;
        int tail = m + n - 1;

        //有效数组的个数大于等于0开始
        while(a>=0 ||b>=0) {
            //如果数组下标等于-1，既越界，直接tail--存放b数组或者对应的a数组
            if (a == -1) {
               nums1[tail--] = nums2[b--];
            } else if (b == -1) {
                nums1[tail--] = nums1[a--];
            } else if (nums1[a] > nums2[b]) {
                nums1[tail--] = nums1[a--];
            } else {
                nums1[tail--] = nums2[b--];
            }
        }
    }
}