Lcof-II

56 - I.数组中数字出现的次数

class Solution {
    public int[] singleNumbers(int[] nums) {
        int n = 0, m = 1, x = 0, y = 0;
        for (int num : nums) {
            n ^= num;
        }
        while ((n & m) == 0) {
            m <<= 1;
        }
        for (int num : nums) {
            if ((num & m) != 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}

57.和为s的两个数字

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

57 - II.和为s的连续正数序列

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while (i < j) {
            if (s == target) {
                int[] temp = new int[j - i + 1];
                for (int k = 0; k < temp.length; k++) {
                    temp[k] = i + k;
                }
                res.add(temp);
            }
            if (s > target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

58 - I.翻转单词顺序

class Solution {
    public String reverseWords(String s) {
        String[] temp = s.trim().split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = temp.length - 1; i >= 0; i--) {
            if (temp[i].equals("")) continue;
            stringBuilder.append(temp[i]).append(" ");
        }
        return stringBuilder.toString().trim();
    }
}

58 - II.左旋转字符串

class Solution {
    public String reverseLeftWords(String s, int n) {
        String end = s.substring(0, n);
        String begin = s.substring(n);
        return begin + end;
    }
}

61.扑克牌中的顺子

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int min = 14, max = 0;
        for (int num : nums) {
            if (num == 0) continue;
            max = Math.max(max, num);
            min = Math.min(min, num);
            if (set.contains(num)) return false;
            set.add(num);
        }
        return (max - min)<5;
    }
}

63.股票的最大利润

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for (int price : prices) {
            cost = Math.min(price, cost);
            profit = Math.max(price - cost, profit);
        }
        return profit;
    }
}

64.求1+2+…+n

class Solution {
    public int sumNums(int n) {
        boolean x = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

65.不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int c = (a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
}

66.构建乘积数组

class Solution {
    public int[] constructArr(int[] a) {
        if (a.length == 0) return new int[0];
        int[] b = new int[a.length];
        b[0] = 1;
        int temp = 1;
        for (int i = 1; i < b.length; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }
        for (int i = b.length - 2; i >= 0; i--) {
            temp *= a[i + 1];
            b[i] *= temp;
        }
        return b;
    }
}

92.反转链表 II

class Solution {
    ListNode successor = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left-1, right-1);
        return head;

    }

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode newHead = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return newHead;
    }
}

200.岛屿数量

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

206.反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}