《剑指Offer》打卡活动 Week 6《剑指Offer》第56-66题

68. 0到n-1中缺失的数字

思路1 二分法

因为是已经排序后的数组，所以可以使用下标和数值是否对应的规则划分

Java代码

class Solution {
    public int getMissingNumber(int[] nums) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] != mid) r  = mid;
            else l = mid + 1; 
        }
        return l;
    }
}

思路2 等差公式求和

适用于乱序的数列
等差数列求和公式；sn = a1 + (n - 1)n/2

Java代码

class Solution {
    public int getMissingNumber(int[] nums) {
        int n = nums.length + 1;
        int res = 0 + (n - 1) * n / 2;
        for (int x : nums) res -= x;
        return res;
    }
}

69. 数组中数值和下标相等的元素

思路1 遍历O(N)

Java代码

class Solution {
    public int getNumberSameAsIndex(int[] nums) {
        for (int i =  0; i < nums.length; i ++ ) {
            if (nums[i] == i) return i;
        }
        return -1;
    }
}

思路2 二分

检查单调性
因为nums中是严格单调上升的，所以有nums[i] - nums[i - 1] >= 1 两边同时减去i
得到nums[i] - i >= nums[i - 1] - i + 1 得到 nums[i] - i >= nums[i - 1] - (i - 1)
故可知nums[i] - i是单调上升的，所以具备单调性

Java代码

class Solution {
    public int getNumberSameAsIndex(int[] nums) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] - mid >= 0) r = mid;
            else l = mid + 1;
        }
        if (nums[l] == l) return l;
        else return -1;
    }
}

70. 二叉搜索树的第k个结点

思路1 中序遍历的序列保存，求第k个

思路2 中序遍历过程中的第k个
将k这个参数传入，每遍历一个节点就k--，当k = 0时，就是该节点 +剪枝

Java代码递归

class Solution {
    TreeNode ans = null;
    int cnt = 0;
    public TreeNode kthNode(TreeNode root, int k) {
        cnt = k;
        dfs(root);
        return ans;
    }
    public void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        cnt -- ;
        if (cnt == 0) ans = root;
        else dfs(root.right); // 剪枝

    }
}

Java代码非递归

class Solution {
    public TreeNode kthNode(TreeNode root, int k) {
        Stack<TreeNode> stk = new Stack<>();
        while (root != null || !stk.isEmpty()) {
            while(root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            k -- ;
            if (k == 0) return root;
            root = root.right;
        }
        return  null;
    }
}

复习非递归中序遍历代码

一种非递归实现二叉树的中序遍历的方法

def inorder_traverse(root):
    stack = []; node = root
    while len(stack) > 0 or node is not None:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        visit(node) # 访问node节点，如输出node的value
        node = node.right

作者：cornerCao
链接：https://www.acwing.com/blog/content/1685/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

71. 二叉树的深度

思路

二叉树的深度：从根节点到叶子节点最长的路径

Java代码后序遍历

class Solution {
    public int treeDepth(TreeNode root) {
        if (root == null) return 0;
        int l = treeDepth(root.left);
        int r = treeDepth(root.right);
        return Math.max(l, r) + 1;
    }
}

Java代码层序遍历

class Solution {
    public int treeDepth(TreeNode root) {
        int res = 0;
        if (root == null) return res;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i ++ ) {
                TreeNode cur = q.poll();
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
            res ++ ;
        }
        return res;
    }
}

72. 平衡二叉树

思路 和二叉树深度类似

使用全局变量，在求二叉树深度的过程中判断

java代码

class Solution {
    boolean res = true;
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return res;
    }

    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (Math.abs(left - right) > 1) res = false;
        return Math.max(left, right) + 1;
    }
}

73. 数组中只出现一次的两个数字

思路 考察异或

注意：>> 的优先级高于&

Java代码

class Solution {
    public int[] findNumsAppearOnce(int[] nums) {
        int sum = 0;
        for (int x : nums) sum ^= x;
        int k = 0;
        while ((sum >> k & 1) == 0) k ++ ;
        int X = 0;
        for (int x : nums) {
            if ((x >> k & 1 ) == 1) X ^= x;
        }
        return new int[]{X, sum ^ X};
    }
}

74. 数组中唯一只出现一次的数字

思路1 按二进制位一位位查看

int型按照32位来看
第一层循环枚举位数i
第二层循环枚举nums中的每个数x，并统计该位上是1的次数cnt，若cnt % 3 = 0那么res在这位上是0 若cnt % 3 = 1那么res在这位上是1
每一位相加res += 1 << i

复杂度分析

O(32n) 因为n的范围是1500，所以logN是小于32的，所以32n > nlogn 因此此种方法的复杂度是O(nlogn)

Java代码

class Solution {
    public int findNumberAppearingOnce(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i ++ ) {
            int cnt = 0;
            for (int x : nums) {
                if ((x >> i & 1) == 1) cnt ++ ;
            }
            if (cnt % 3 == 1) res += 1 << i;
        }
        return res;
    }
}

思路2 状态机

数电的思路，从状态位表示真值表到转移方程推导
参考大佬的题解

本题是需要1出现三次时才会抵消，因此有三种状态，即1出现的次数为3k, 3k + 1, 3k + 2次

逐个位来看，要设计一个两位的状态转移，出现三个1时，循环抵消，出现0时不变，一个变量只能记录两种状态，因此要用两个变量来记录状态，用one和two两个变量来记录1出现次数
00表示1出现3k次，01表示1出现3k + 1次，10表示1出现3k + 2次

  真值表
  two     one     x       two     one
  0       0       1       0       1   
  0       1       1       1       0
  1       0       1       0       0
  0       0       0       0       0
  0       1       0       0       1
  1       0       0       1       0
先看one的状态转移方程

 one = (~one & ~two & x) | (one & ~two & ~x)
     = ~two & ((~one & x) | (one & ~x))
     = ~two & (one ^ x)
同理，再用转移后的one来求two的状态转移方程

这里，one为当且仅当1出现次数为3k + 1, tow为当且仅当1出现次数为3k + 2
因此如果题目改为，有一个数出现了两次，则返回two即可

作者：Rainbow_0
链接：https://www.acwing.com/solution/content/19076/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

利用特点: 位运算的过程中，每一位之间都是独立的

Java代码

class Solution {
    public int findNumberAppearingOnce(int[] nums) {
        int one = 0, two = 0;
        for (int x : nums) {
            one = (one ^ x)& ~two;
            two = (two ^ x) & ~one;
        }
        return one;
    }
}

75. 和为S的两个数字

暴力做法

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

优化方法

Java代码

class Solution {
    public int[] findNumbersWithSum(int[] nums, int target) {
        Set<Integer> map = new HashSet<>();
        for (int i = 0; i < nums.length; i ++ ) {
            if (map.contains(target - nums[i])) return new int[]{nums[i], target - nums[i]};
            else map.add(nums[i]);
        }
        return new int[]{0, 0};
    }
}

76. 和为S的连续正数序列

思路 暴力做法，枚举子序列的首尾

Java代码

class Solution {
    public List<List<Integer> > findContinuousSequence(int sum) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 1; i < sum; i ++ ) {
           for (int j = 1; j < i; j ++ ) {
               List<Integer> path = new LinkedList<>();
               int ans = 0;
               for (int k = j; k <= i; k ++ ) {
                  path.add(k);
                  ans += k; 
               }
               if (ans == sum) res.add(path);
           }

       }
       return res;
    }
}

思路2 双指针

i往后移的过程中j一定也往后移

类似做法参考
https://www.acwing.com/file_system/file/content/whole/index/content/7079120/
最长不重复子串 https://www.acwing.com/file_system/file/content/whole/index/content/6656307/
count and say https://www.acwing.com/file_system/file/content/whole/index/content/6645149/

Java代码

class Solution {
    public List<List<Integer> > findContinuousSequence(int sum) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        for (int i = 1, j = 1, s = 0; i < sum; i ++ ) {
            s += i;
            path.addLast(i);
            while (j < i && s > sum) {
                s -= j;
                j ++ ;
                path.removeFirst();
            }
            if (s == sum) res.add(new LinkedList<>(path));
        }
       return res;
    }
}

77. 翻转单词顺序

思路

先翻转整个句子，再逐个翻转每一个单词

Java代码

class Solution {
    public String reverseWords(String s) {
        char[] str = s.toCharArray();
        reverse(str, 0, s.length() - 1);

        int start = 0;
        for (int i = 0; i < s.length(); i ++ ) {
            if (str[i] == ' ') {
                reverse(str, start, i - 1);
                start = i + 1;
            }
            // 因为最后一个单词后面没有空格
            // 特殊处理
            if(i == s.length() - 1){
                reverse(str, start, i);
            }
        }
        return new String(str);

    }
    public void reverse(char[] str, int l, int r) {
        for (int i = l, j = r; i < j; i ++, j -- ) {
            char c = str[i];
            str[i] = str[j];
            str[j] = c;
        }
    }
}

78. 左旋转字符串

Java代码

class Solution {
    public String leftRotateString(String str,int n) {
        if (n == 0) return str;
        int len = str.length();
        str += str;
        return str.substring(n, n + len);
    }
}