Leecode编程题，刷题，笔试题_编程刷题 code

Lee.第1题：

方法一：暴力破解法：在原数组上进行操作。

class Solution {
    public int[] twoSum(int[] nums, int target) {
		for(int i = 0; i < nums.length - 1; i++) {
			for(int j = i + 1; j < nums.length; j++) {
				if(nums[i] + nums[j] == target) {
					return new int[] {i,j};
				}
			}
		}
		return null;
    }
}

解析：定义一个 i 从数组的下标0开始遍历，定义一个 j 从 i + 1开始遍历，先遍历j ，判断 i 对应的值加 j 对应的值是否等于 target的值，若等于，则返回下标，不等于让 i ++，i 遍历完之后，若没找到，则返回null，代表没有符合要求的数字。

方法二：哈希表法：

解析：用到HashMap，给定target的值，用target - i 对应的值，i 从数组下标0处开始，i 对应的值一开始为11，做差后在HashMap中找不到，就把i对应的值和角标存到HashMap中，一次遍历做差，直到角标3处，9 - 7 = 2，可以在HashMap中找到2，所以返回7和2对应的角标即可。代码如下：

Lee.第二题：三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

方法一：双指针法

public class threeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> list1 = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            if (nums[i] > 0){
                return list1;
            }
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int cur = nums[i];
            int L = i + 1;
            int R = nums.length - 1;
            while (L < R){
                int temp = cur + nums[L] + nums[R];
                if (temp == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(cur);
                    list.add(nums[L]);
                    list.add(nums[R]);
                    list1.add(list);
                    L++;
                    R--;
                    while (L < R && nums[L] == nums[L - 1]){
                        L++;
                    }
                    while (L < R && nums[R] == nums[R + 1])
                        R--;
                }else if (temp > 0){
                    R--;
                }else {
                    L++;
                }
            }
        }
        return list1;
    }
}

（3）：统计n以内的素数，素数是只能被1和自身整除的数，0,1除外；

方法一：暴力破解法

public class lianxi {
    public static void main(String[] args) {
        System.out.println(countSuNum(100));
    }
    public static int countSuNum(int n){
        int count = 0;
        for (int i = 2; i < n; i++){
            count += isPrima(i) ? 1 : 0;
        }
        return count;
    }
 
    private static boolean isPrima(int x) {
        for (int i = 2; i < x; i++){
            if (x % i == 0){
                return false;
            }
        }
        return true;
    }
}

方法二：埃筛法，是bf的一种优化；（eratosthenes）

public class lianxi {
    public static void main(String[] args) {
        System.out.println(eratasthenes(100));
    }
    public static int eratasthenes(int n){
        boolean[] isPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++){
            if (!isPrime[i]){
                count++;
                for (int j = 2 * i; j < n; j += i){
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }
}

需要注意的是内层for循环，i是外层的变量，后面用j+=i让j自加；

（4）：链表反转，将链表的顺序反转过来

方法一：递归

        递归最关键的就是把大的问题华为小的问题解决，最后把这个方法用到整个问题当中；

遇到问题不要慌，先分析问题：

配图一：结点反转的思路；

配图2：从后向前反转，头结点的确定；

 （2）:迭代法：

从前向后，先创建一个next保存下一个节点的值，即head.next，将head.next置空，再保存head的值再prev中，用于第二个结点指向第一个结点，再把next的值赋给head，让head走到第二个结点

全部代码如下：

public class lianxi {
    static class ListNode{
        int val;
        ListNode next;
 
        public ListNode(int val,ListNode next){
            this.val = val;
            this.next = next;
        }
    }
    //迭代
    public static ListNode iterate(ListNode head){
        ListNode prev = null,next;
        ListNode curr = head;
        while (head != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    //递归
    public static ListNode recursion(ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode new_node = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return new_node;
    }
    
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);
//      ListNode prev = iterate(node1);
//      System.out.println(prev);
        ListNode prev = iterate(node1);
        System.out.println(prev);
    }
}