一些当时的bug和注意点大多在注解中标注

1.数组中的重复数字(Easy)

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

利用Set的性质

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set=new HashSet<Integer>();
        int repeat=-1;
        for (int num : nums){
            if(!set.add(num)){
                repeat=num;
                break;
            }

        }
        return repeat;
    }
}

2.和为s的连续正整数序列(Easy)

借用滑动窗口思想
输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<int[]>();
        for(int l=1, r=2;l<r;){
            int sum=(l+r)*(r-l+1)/2;//漏写乘号
            if(sum == target){
                int[] res = new int[r-l+1];
                for(int i=l;i<=r;++i){
                    res[i-l]=i;//i-l写成i-1
                }
                list.add(res);
                l++;//这里一刻开始漏了
            }else if(sum<target){
                r++;
            }else{
                l++;
            }
        }
        return list.toArray(new int[list.size()][]);//形参应该为new int[][]
    }
}

3.求链表倒数第k个节点

双指针同步移动

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
       ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;

    }
}

4.两数相加

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
image.png

该题所需注意的点都通过注释写于代码内

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode tail = null;
        int carry = 0;
        while(l1 != null || l2 != null){
            int i = l1 == null ? 0 :l1.val;
            int j = l2 == null ? 0 :l2.val; 
            if(l1!=null){
               l1=l1.next; 
            }
            if(l2!=null){
              l2=l2.next;  
            }
            int sum = i+j+carry;
            // if(i+j>10){         
            //      newNum = (i+j+carry)%10; 
            // }else{   
            //      newNum = i+j+carry;
            // }
            //这一段代码也不需要,统一对10取余

           
            //以下这两段链表的操作要熟悉
             if(head==null){
                head = tail = new ListNode(sum%10);    
            }else{
                tail.next = new ListNode(sum%10);
                tail = tail.next;
            }
            // if(i+j>10){
            //      carry = 1;
            
            // }else{
            //      carry = 0;  
            // }
            //上面这一步可以简化为下面这行代码
            carry = sum/10;  
        } 
        //循环完后还要记得加一步判断是否还要进位
        if(carry>0){
        //tail不需要移动了	
            tail.next= new ListNode(carry);
        }
        return head;          
           
    }
}

力扣剑指11题

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。
本题考虑三种情况

class Solution {
    public int minArray(int[] numbers) {
        if(numbers==null)return 0;
        int right = numbers.length-1;
        int left = 0;
        int mid = (left + right)/2;
        if(numbers[left]<numbers[right])return numbers[left];
        while(true){
            // if(mid==left)break;不能这样写,要考虑中、左右一样的情况
            if(right-left==1)break;
            if(numbers[mid]==numbers[left]&&numbers[mid]==numbers[right]){
                int res=numbers[0];
                for(int i=0;i<numbers.length-1;i++){
                    if(numbers[i]<res)res=numbers[i];
                }
                return res;
            }
            if(numbers[mid]>=numbers[left]) left=mid;
            else if(numbers[mid]<=numbers[right])right=mid;
            mid = (left + right)/2;
        }
        return numbers[right];
    }
}


反转链表(Medium)

npc算法
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
分别运用递归和迭代的方法来做

package leecode;


public class ReverseLink {


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.add(2);
        head.add(3);
        head.add(4);
        head.add(5);
        head.print();
        System.out.println();

        ListNode newHead = ReverseLink2(head);
        newHead.print();
    }

    //递归实现
    public static ListNode ReverseLink1(ListNode head) {
        if (head.next == null) return head;
        ListNode last = ReverseLink1(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    //迭代实现
    public static ListNode ReverseLink2(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

注释掉的代码为递归反转整个链表

K个一组反转链表(Hard)

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

/**
 * Definition for singly-linked list.
 * 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 Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null)return null;
        ListNode a = head,b=head;
        for(int i=0;i<k;i++){
            if(b==null) return head;

             b=b.next;
        }
        ListNode newHead = reverse(a,b);
        a.next =reverseKGroup(b,k);
        return newHead;
    }
    //这里用迭代实现
    static ListNode reverse(ListNode a,ListNode b){
        ListNode pre=null,cur = a,suc=a;
        while(cur!=b){
            suc = cur.next;//给第四步用
            cur.next = pre;
            pre = cur;
            cur = suc;
        }
        return pre;
    }
}

二进制中一的个数

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n!=0){
            res += n&1;
            n = n>>>1;
        }
        return res;
    }
    
}

这里采用无符号右移,对于负数>>>高位均补0,而负数>>高位补1

数值的整数次方

这里需要把n转换为long,防止越界。
一开始先自己写了个包含各种情况的解法

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        long nn = n;
        if(x==1)return 1;
        if(x==0)return 0;
        if(nn<0){
            if(x<0)return 0;
            for(long i=0;i<-nn;i++){
                res *=x; 
            }
            return 1.0/res;
        }else{
            if(nn==0)return 1.0;
            else{
                for(long i=0;i<nn;i++){
                res *=x; 
                }
                return res;
            }
        }
    }
    
}

报错超时
image.png
改为快速幂法
image.png
解法如下:

class Solution {
    public double myPow(double x, int n) {
            long b = n;
            double res = 1;
            if(x==0)return 0;
            if(b<0){
                b=-b;
                x=1/x;
            }
            while(b>0){
                if((b&1)==1)res *=x;
                x *=x;
                b >>=1;
            }
            return res;
        }
    }

时间复杂度变为log2N。

打印1到最大的n位数

考虑大整数的情况

package leecode;

public class MaxFrom1ToN {
    int n;
    char res[],loop[]={'0','1','2','3','4','5','6','7','8','9'};
    StringBuilder s = new StringBuilder();

    public static void main(String[] args) {
        MaxFrom1ToN maxFrom1ToN = new MaxFrom1ToN();
        System.out.println(maxFrom1ToN.printNumbers(6));
    }
    public String printNumbers(int n) {
        this.n = n;
        res =new char[n];
        dfs(0);
        s.deleteCharAt(s.length()-1);
        return s.toString();
    }
    void dfs(int x){
        if(x==n){
            s.append(String.valueOf(res)+',');
            return;
        }
        for(char i:loop){
            res[x] = i;
            dfs(x+1);
        }

    }


}

image.png

二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
image.png
用递归求

class Solution {
   public void flatten(TreeNode root) {
           if(root==null)return;
           flatten(root.left);
           flatten(root.right);
           TreeNode left = root.left;
           TreeNode right = root.right;
           root.left=null;
           root.right=left;
           TreeNode p =root;
           while(p.right!=null){
               p = p.right;
           }
           p.right=right;
   }
}

最大二叉树

image.png

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums,0,nums.length-1);
    }
    TreeNode build(int[] nums,int s,int e){
        if(s>e)return null;
        int max = Integer.MIN_VALUE;
        int index=s;
        for(int i=s;i<=e;i++){
            if(nums[i]>max) {
                max=nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left=build(nums,s,index-1);
        root.right=build(nums,index+1,e);
        return root;
    }
}

双栈实现队列

class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2; 
    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(stack2.size()==0&&stack1.size()==0)return -1;
        else if(stack2.size()==0){
        //for(int i=0;i<stack1.size();i++) 这一句不能用的原因 size是会变化的
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

Q.E.D.