16. 知识迁移能力（8）

时间：2019-12-21 14:13:29 阅读：57 评论：0 收藏：0 [点我收藏+]

题一：【数字在排序数组中出现的次数】

统计一个数字在排序数组中出现的次数。

法一：暴力解决O(N)

 1 public class Solution {
 2     public int GetNumberOfK(int [] array , int k) {
 3        int count = 0;
 4         for(int i=0;i<array.length;i++){
 5             if(array[i]==k){
 6                 count++;
 7             }
 8             if(i<array.length-1&&array[i]==k&&array[i+1]!=k){
 9                 return count;
10             }
11         }
12         return count;
13     }
14 }

法二：我们只用查询第一个k和最后一个k的位置，便可以求出k的次数（lastIndex-firstIndex+1）。使用二分查找O(logN)：

　　A.找第一个k

　　①如果中间值大于k，那么k在前半段；

　　②如果中间值小于k，那么k在后半段。

　　③如果中间值等于k，先判断是否是第一个k（前一个值不等于k或者不存在），如果是则返回，如果不是下一次循环接着往前找。

　　B.找最后一个k

　　①如果中间值大于k，那么k在前半段；

　　②如果中间值小于k，那么k在后半段。

　　③如果中间值等于k，先判断是否是最后一个k（后一个值不等于k或者不存在），如果是则返回，如果不是下一次循环接着往后找。

 1 public class Solution {
 2     public int GetNumberOfK(int [] array , int k) {
 3         if(array.length==0) return 0;
 4         int firstIndex = GetFirst(array, 0, array.length-1, k);
 5         int lastIndex = GetLast(array, 0, array.length-1, k);
 6         if(firstIndex!=-1&&lastIndex!=-1){
 7             return lastIndex-firstIndex+1;
 8         }
 9         return 0;
10     }
11     public int GetFirst(int[] array, int left, int right, int k){
12         if(left>right) return -1;
13         int mid = (left+right)/2;
14         if(array[mid]>k){
15             return GetFirst(array,0,mid-1,k);
16         }else if(array[mid]<k){
17             return GetFirst(array,mid+1,right,k);
18         }else{
19             if(mid==left||array[mid-1]!=k){
20                 return mid;
21             }else{
22                 return GetFirst(array,0,mid-1,k);
23             }
24         }
25     }
26     public int GetLast(int[] array, int left, int right, int k){
27         if(left>right) return -1;
28         int mid = (left+right)/2;
29         if(array[mid]>k){
30             return GetLast(array,0,mid-1,k);
31         }else if(array[mid]<k){
32             return GetLast(array,mid+1,right,k);
33         }else{
34             if(mid==right||array[mid+1]!=k){
35                 return mid;
36             }else{
37                 return GetLast(array,mid+1,right,k);
38             }
39         }
40     }
41 }

题二：【二叉树的深度】

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

分析：递归，遍历左右节点，比较左右节点深度。如果一棵树只有一个节点，那么他的深度加1。如果根节点只有左子树，那么树的深度应是其左子树深度加1。如果左子树右子树都存在，那么树的深度就是左右子树较大深度加1。

 1 /**
 2 public class TreeNode {
 3     int val = 0;
 4     TreeNode left = null;
 5     TreeNode right = null;
 6     public TreeNode(int val) {
 7         this.val = val;
 8     }
 9 }
10 */
11 public class Solution {
12     public int TreeDepth(TreeNode root) {
13         if(root==null) return 0;
14         int leftHeight = TreeDepth(root.left);
15         int rightHeight = TreeDepth(root.right);
16         return (leftHeight>rightHeight)?(leftHeight+1):(rightHeight+1);
17     }
18 }

题三：【平衡二叉树】

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

法一：利用题二中计算二叉树深度的方法，在遍历二叉树途中进行比较。

 1 public class Solution {
 2     public boolean IsBalanced_Solution(TreeNode root) {
 3         if(root==null) return true;
 4         int leftDepth = TreeDepth(root.left);
 5         int rightDepth = TreeDepth(root.right);
 6         int diff = leftDepth-rightDepth;
 7         if(diff>1||diff<-1){
 8             return false;
 9         }
10         return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
11     }
12     public int TreeDepth(TreeNode root) {
13         if(root==null) return 0;
14         int leftHeight = TreeDepth(root.left);
15         int rightHeight = TreeDepth(root.right);
16         return (leftHeight>rightHeight)?(leftHeight+1):(rightHeight+1);
17     }
18 }

法二：法一中在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销，节点越往下被遍历次数越多。因此可以使用后序遍历，在遍历到一个节点时就已经遍历了他的左右子树。只要在遍历每个节点是记录他的深度，我们就可以一边遍历一遍判断每个节点是不是平衡的。

 1 public class Solution {
 2     public boolean IsBalanced_Solution(TreeNode root) {
 3         return getDepth(root)!=-1;
 4     }
 5     public int getDepth(TreeNode root){
 6         if(root==null) return 0;
 7         int left = getDepth(root.left);
 8         //当前节点左子树不平衡的，则整个也不是平衡的
 9         if(left==-1) return -1;
10         int right = getDepth(root.right);
11         if(right==-1) return -1;
12         int diff = left-right;
13         if(diff>1||diff<-1){
14             return -1;
15         }else{//如果当前节点时平衡的，则深度为较深的子树深度加上1
16             return diff>0?left+1:right+1;
17         }
18     }
19 }

题四：【数组中只出现一次的数】

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

分析：一个数异或它本身等于0。从头到尾依次异或数组中的每个数字，最后的结果是两个只出现一次数字的异或结果。两个数字不一样，因此最终的结果不为0，至少有一位是1。根据第一个1出现的位置将数组分为两组，一组是该位置是0，一组是该位置为1。两个不一样的数分别在这两个小数组里。将两个小数组分别异或就可以分别求出两个数（小数组除了这两个数，其他都是成对出现，如果异或，成对数异或之后为0，两个数组内就分别剩下这两个不一样的输了）。

 1 //num1,num2分别为长度为1的数组。传出参数
 2 //将num1[0],num2[0]设置为返回结果
 3 public class Solution {
 4     public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
 5         int xor = 0;
 6         //大数组的异或 
 7         for(int i=0;i<array.length;i++){
 8             xor = xor^array[i];
 9         }
10         //从左往右找出xor第一个1的位置
11         int index = 1;
12         while((xor&index)==0){//1&1=1，1&0=0，0&0=0
13             index = index<<1;//如果xor该位不为1，则index左移一位仅需判断
14         }
15         int res1=0;
16         int res2=0;
17         for(int i=0;i<array.length;i++){
18             if((array[i]&index)!=0){//分组，将该位是1的分为一组，该位是0的分为一组
19                 res1 = res1^array[i];
20             }else{
21                 res2 = res2^array[i];
22             }
23         }
24         num1[0] = res1;
25         num2[0] = res2;
26     }
27 }

题五：【和为S的连续正数序列】

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

【输出描述】输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

分析：连续正数序列，那就不止一个，遍历范围变成1~（S/2+1），例如S=89，则遍历范围是1~45. O(N^2)

 1 import java.util.ArrayList;
 2 public class Solution {
 3     public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
 4         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
 5        ArrayList<Integer> list;
 6        for(int i=1;i<=sum/2+1;i++){
 7            list = new ArrayList<Integer>();
 8            int sumary = 0;
 9            int j = i;
10            while(sumary<=sum){
11                if(sumary==sum&&j!=(i+1))
12                {
13                    res.add(list);
14                    break;
15                }
16                list.add(j);
17                sumary = sumary+j;
18                j=j+1;
19            }
20        }
21        return res;
22     }
23 }

分析：使用两个指针start、end分别对应序列的开始和结束，初始时将start=1，end=2.。将start到end之间求和(连续正数可使用求和公式)并与S进行比较：如果和小于S，则增加end；如果和大于S，则增加start。如果和等于S，则将start到end的数字添加到list中，并增加small，进行下一次循环。

 1 import java.util.ArrayList;
 2 public class Solution {
 3     public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
 4         ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
 5         if(sum<2) return res;
 6         int start = 1, end = 2;
 7         while(start<end&&end<=(sum/2+1)){
 8             int sumary = (start+end)*(end-start+1)/2;//求和公式
 9             if(sumary<sum){
10                 end++;
11             }else if(sumary>sum){
12                 start++;
13             }else{
14                 ArrayList<Integer> list = new ArrayList<Integer>();
15                 for(int i=start;i<=end;i++){
16                     list.add(i);
17                 }
18                 res.add(list);
19                 start++;
20             }
21         }
22         return res;
23     }
24 }

题六：【和为S的两个数字】

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

【输出描述】对应每个测试案例，输出两个数，小的先输出。

分析：根据题五思路，设置两个指针start、end分别指向第一个数和最后一个数的索引，初始化start=0,end=array.length-1；如果两个数字的和小于S，则start往后移动一位；如果两个数字的和大于S，则end往前移动一位；如果两个数字的和等于S，则直接输出。

【注意】：如果有多对数字的和等于S，输出两个数的乘积最小的。按照本解法，遍历到的第一个满足条件的两个数就是乘积最小的。

　　　　　a<b, a*b<(a+1)*(b-1)。

 1 import java.util.ArrayList;
 2 public class Solution {
 3     public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
 4         ArrayList<Integer> res = new ArrayList<Integer>();
 5         int start = 0;
 6         int end = array.length-1;
 7         while(start<end){
 8             int sumary = array[start]+array[end];
 9             if(sumary<sum){
10                 start++;
11             }else if(sumary>sum){
12                 end--;
13             }else{
14                     res.add(array[start]);
15                     res.add(array[end]);
16                     return res;
17                 }
18             }
19         return res;
20     }
21 }

题七：【翻译单词顺序列】

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

分析：翻转单词，但是单词内字符顺序不变且标点符号和字符一样处理。

 1 public class Solution {
 2     public String ReverseSentence(String str) {
 3         if(str.trim().equals("")) return str;
 4         String[] stringArr = str.split(" ");
 5         String res = "";
 6         for(int i=stringArr.length-1;i>=0;i--){
 7             if(i==stringArr.length-1){
 8                 res=res+stringArr[i];
 9             }else{
10                 res=res+" "+stringArr[i];
11             }
12         }
13         return res;
14     }
15 }

题八：【左旋转字符串】

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

 1 public class Solution {
 2     public String LeftRotateString(String str,int n) {
 3         if(n>str.length()) return "";
 4         char[] chArr = str.toCharArray();
 5         char[] res = new char[chArr.length];
 6         int index=0;
 7         for(int i=n;i<chArr.length;i++){
 8             res[index++] = chArr[i];
 9         }
10         for(int i=0;i<n;i++){
11             res[index++] = chArr[i];
12         }
13         return String.valueOf(res);
14     }
15 }

16. 知识迁移能力（8）

原文：https://www.cnblogs.com/qmillet/p/12066826.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)