11.22

384. 打乱数组

图片.png

  1. 对于reset操作，用一个数组保存nums原始的值，需要时返回即可
  2. 对于shuffle操作，采用洗牌算法：即对nums[i],将其和nums[i]-nums[n-1-i]中的的元素随机交换

下标为i的元素，和区间[i,n-1-i]内的元素随机交换 图片.png

  1. class Solution {
  2.     int initArr[];
  3.     int nums[];
  4.     public Solution(int[] nums) {
  5.         initArr=new int[nums.length];
  6.         for(int i=0;i<nums.length;i++)
  7.             initArr[i]=nums[i];
  8.         this.nums=nums;
  10.     }
  12.     public int[] reset() {
  13.         return initArr;
  15.     }
  17.     public int[] shuffle() {
  18.        Random random=new Random();
  19.        for(int i=0;i<nums.length;i++)
  20.        {
  21.            //random.nextInt(n-i)--->[0,n-i) 即[0,n-i-1]  
  22.            //[0,n-i-1]+i=[i,n-1]  
  23.            swap(i,i+random.nextInt(nums.length-i));
  24.        }
  25.        return nums;
  26.     }
  27.     public void swap(int i,int j)
  28.     {
  29.         int t=nums[i];
  30.         nums[i]=nums[j];
  31.         nums[j]=t;
  32.     }
  33. }
  34. //O(n)
  35. //O(n)

11.23

859. 亲密字符串

图片.png

  1. 当两个字符串长度不同时，返回false
  2. 记录两个字符串中各个字符出现的次数，某种字符出现的次数如果不同，返回false
  3. 记录s核goal中同一个位置上字符不同的个数为diff, 如果diff==2，返回false; 如果diff=0但是如果某类字符出现了两次及以上，这种情况也返回true, 比如aa aa | abab abab | aba aba| 
  1. class Solution {
  2. public:
  3.     bool buddyStrings(string s, string goal) {
  4.         if(s.size()!=goal.size())
  5.             return false;
  7.         unordered_map<char,int> map1,map2;
  8.         for(char c:s)
  9.             map1[c]++;
  10.         for(char c:goal)
  11.             map2[c]++;
  12.         int diff=0;
  13.         bool flag=false;
  14.         for(int i=0;i<s.size();i++)
  15.         {
  17.             if(map1[s[i]]!=map2[s[i]])
  18.                 return false;
  19.             if(s[i]!=goal[i])
  20.                 diff++;
  21.             if(map1[s[i]]>1)
  22.                 flag=true;
  23.         }
  24.         return diff==2||(diff==0&&flag);
  26.     }
  27. };
  28. //O(m+n) m n分别为s和goal的长度
  29. //O(c) c是s中出现的字符的种类数

11.24

700. 二叉搜索树中的搜索

图片.png

根据二叉搜索树的性质，如果当前key比当前节点大，就到当前节点的右子树中寻找；如果当前key比当前节点小，就到当前节点的左子树中寻找 实现方法有递归和迭代两种

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
         if(root==null)
            return null;
        if(val<root.val)
            return searchBST(root.left,val); 
        else if(val>root.val)
            return searchBST(root.right,val); 
          return root;
    }
}
//O(n) 最坏情况下BST退化为链表
//O(n)

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {

          while(root!=null)
          {
              if(root.val==val)
                 break;
              else if(root.val>val)
                root=root.left;
              else if(root.val<val)
                root=root.right;
          }
          return root;
    }
}
//O(n) 最坏情况下BST退化为链表
//O(1)