作者：Opera2502898747 | 来源：互联网 | 2023-10-11 11:14
用O(1)时间检测整数n是否是2的幂次。样例n4，返回true;n5，返回false.注意O(1)时间复杂度1classSolution{2*3*@paramn:Aninteger
用 O(1) 时间检测整数 n 是否是 2 的幂次。
样例n=4，返回 true;
n=5，返回 false.
注意O(1) 时间复杂度
1 class Solution {
2 /*
3 * @param n: An integer
4 * @return: True or false
5 */
6 public boolean checkPowerOf2(int n) {
7 // write your code here
8 if(n==1){
9 return true;
10 }else if(n<=0||n%2==1){
11 return false;
12 }else{
13 while(n>1){
14 n=n/2;
15 if(n==1) return true;
16 if(n%2==1) return false;
17 }
18 }
19 return true;
20 }
21 };
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
- 每行中的整数从左到右是排序的。
- 每行的第一个数大于上一行的最后一个整数
考虑下列矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
给出 target = 3，返回 true
我使用的是二分法，最传统的查找，当然也过了，不过在学习过程中发现了别人更好的代码
1 public class Solution {
2 /**
3 * @param matrix, a list of lists of integers
4 * @param target, an integer
5 * @return a boolean, indicate whether matrix contains target
6 */
7 public boolean searchMatrix(int[][] matrix, int target) {
8 // write your code here
9 int left = 0;
10 int right = matrix.length-1;
11 if(left!=right){
12 while(left<=right){
13 int middle=(right+left)/2;
14 if(matrix[middle][0]<target){
15 left = middle +1;
16 }else if(matrix[middle][0]>target){
17 right = middle -1;
18 }else {
19 return true;
20 }
21 }
22
23 }
24 if(right <0 ){
25 return false;
26 }
27 else{
28 int row = right;
29 left = 0;
30 right = matrix[row].length -1;
31 if(left!=right){
32 while(left<=right){
33 int middle=(right+left)/2;
34 if(matrix[row][middle]<target){
35 left = middle +1;
36 }else if(matrix[row] [middle]>target){
37 right = middle -1;
38 }else {
39 return true;
40 }
41 }
42 }
43
44 }
45 return false;
46 }
47 }
1 public class Solution {
2 /**
3 * @param matrix, a list of lists of integers
4 * @param target, an integer
5 * @return a boolean, indicate whether matrix contains target
6 */
7 public boolean searchMatrix(int[][] matrix, int target) {
8 // write your code here
9 int i=0;
10 int j=matrix[0].length -1;
11 while (i =0）{
12 if(matrix[i][j]==target){
13 return true;
14 }else if (target < matrix[i][j]){
15 j--;
16 }else {
17 i++;
18 }
19 return false；
20 }
21 }
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix.html 附上这个分析思路很不错的帖子。题目虽然不难，但也是有陷阱的
京公网安备 11010802041100号