[数据结构与算法]剑指offer 2021/7/25

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

算法思想

leetcode题解

法一

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1;
        double j = 2.0;
        ArrayList<int[]> list  = new ArrayList<>();
        while(i < j){
            j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
            if(j > i && (int)j == j){
                int[] ans = new int[(int)j - i  + 1];
                for(int k = i; k <= (int)j; ++k){
                    ans[k - i] = k;
                }
                list.add(ans);
            }
            i++;
        }
        return list.toArray(new int[0][0]);
    }
}

法二

滑动窗口。

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j =2, sum = 3;
        ArrayList<int []> list = new ArrayList<>();
        while(i < j){
            if(sum == target){
                int[] ans = new int[j - i + 1];
                for(int k = i; k <= j; ++k){
                    ans[k-i] = k;
                }
                list.add(ans);
                i++;
            }else if(sum > target){
                i++;
            }else{
                j++;
            }
            sum = (i + j) * (j - i + 1) / 2;
        }
        return list.toArray(new int[0][]);
    }
}

36. 二叉搜索树与双向链表

算法思想

中序遍历二叉搜索树中各个节点，设置两个节点cur和pre来辅助构建双向链表。最后将头尾节点连接。

代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if(root == null)    return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    public void dfs(Node curr){
        if(curr == null) return;
        dfs(curr.left);
        if(pre != null){
            pre.right = curr;
        }else{
            head = curr;
        }
        curr.left = pre;
        pre = curr;
        dfs(curr.right);
    }
}

61. 扑克牌中的顺子

法一

数组中无重复数字且最大最小值之差小于5即满足要求。用哈希表存储数组中元素以判断是否有元素重复。

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

法二

先排序，通过比较nums[i+1]与nums[i]是否相等判断数组中是否有重复元素。再用joker记录数组中大小王的个数，可得到最大最小值之差为nums[nums.length-1] - nums[joker]，若差值小于5，则返回true，否则返回false。

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-1; ++i){
            if(nums[i] == 0){
                joker++;
                continue;
            }
            if(nums[i+1] == nums[i]){
                return false;
            }
        }
        return nums[nums.length - 1] - nums[joker] < 5;
    }
}