LeetCode算法集

贴的题是不难的算法题，但是感觉易错易考。

1、统计所有小于非负整数 n 的质数的数量。
思路：用一个数组来存储boolean，判断是否是质数

class Solution {
    public int countPrimes(int n) {
        boolean notPrime[] = new boolean[n + 2];
        notPrime[0] = notPrime[1] = true;  //0，1为非质数
        /**
        不断地求质数*n,使其位置为非质数
        2*2=4 2*3 2*4 2*5...
        3*3=9 3*4 3*5...
        ...
        false为质数
        */
       for(int i=2;i*i<n;i++){
          if(!notPrime[i]){//如果这个数为质数
              int c=i*i;
              while(c<n){
                  notPrime[c]=true;  //该位置为非质数
                  c+=i;
              }
          }
       }
        int count=0;
        for(int i=2;i<n;i++){
            //输出质数
            if(!notPrime[i]){
                count++;
            }
        }
        return count;
    }
}

2、反转链表：做了很多次还总是做错
先判断链表是否为空
递归链表反转，再构造2个链表节点next和pre，
递归时围绕next、head.next、pre和head=？来写
最后输出的pre节点（指向最后的当前节点）。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
       ListNode pre=null;
        ListNode next=null;
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
    
}

3。判断hashmap是否包含这个key：map.containsKey(key)

4、移动零
题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
思路：j=0，直接遍历，找数组中非0的，然后都移到前面（利用数组中j的位置），则遍历完成j之后的到数组长度的 就都是0

class Solution {
    public void moveZeroes(int[] nums) {
       int j=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[j++]=nums[i];
            }
        }
        while(j<nums.length){
            nums[j++]=0;
        }
    
    }
}