05、10-II、17、39、42、55、57、57-II、64

保護眼睛 2021-08-15 04:44:41 阅读数:402

本文一共[544]字,预计阅读时长:1分钟~
10-ii ii 57-ii ii

劍指 Offer 42. 連續子數組的最大和


class Solution42 {

public int maxSubArray(int[] nums) {

int len = nums.length;
int tmpRes = 0;
int res = nums[0];
for (int i = 0; i < len; i++) {

tmpRes = Math.max(nums[i], tmpRes + nums[i]);
res = Math.max(tmpRes, res);
}
return res;
}
}

劍指 Offer 10- II. 青蛙跳臺階問題

class Solution10 {

public static int numWays(int n) {

if (n <= 2)
return n;
int f1 = 1;
int f2 = 2;
int res = 0;
for (int i = 3; i <= n; i++) {

res = (f1 + f2) % 1000000007;
f1 = f2;
f2 = res;
}
return res;
}
}

劍指 Offer 05. 替換空格


class Solution05 {

public static String replaceSpace(String s) {

return s.replace(" ", "%20");
}
}

劍指 Offer 55 - I. 二叉樹的深度

class Solution55 {

public int maxDepth(TreeNode root) {

if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
public int maxDepthDfs(TreeNode root) {

if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int res = 0;
while (!queue.isEmpty()) {

res++;
int size = queue.size();
while (size-- > 0) {

TreeNode cur = queue.poll();
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return res;
}
}

劍指 Offer 17. 打印從1到最大的n比特數

class Solution17 {

public static int[] printNumbers(int n) {

StringBuilder len = new StringBuilder("1");
for (int i = 0; i < n; i++) {

len.append(0);
}
int[] res = new int[Integer.parseInt(len.toString()) - 1];
for (int i = 1; i <= Integer.parseInt(len.toString()) - 1; i++) {

res[i - 1] = i;
}
return res;
}
}

劍指 Offer 57 - II. 和為s的連續正數序列

class Solution57_II {

public int[][] findContinuousSequence(int target) {

List<int[]> res = new ArrayList<>();
int left = 1;
int right = 1;
int sum = 0;
while (left <= target / 2) {

if (sum < target) {

sum += right;
right++;
} else if (sum > target) {

sum -= left;
left++;
} else {

int[] tmp = new int[right - left];
for (int i = left; i < right; i++) {

tmp[i - left] = i;
}
res.add(tmp);
sum -= left;
left++;
}
}
return res.toArray(new int[res.size()][]);
}
}

劍指 Offer 57. 和為s的兩個數字

class Solution57 {

public int[] twoSum(int[] nums, int target) {

int i = 0, j = nums.length - 1;
while (i < j) {

int sum = nums[i] + nums[j];
if (sum == target) {

return new int[]{
nums[i], nums[j]};
} else if (sum > target) {

j--;
} else {

i++;
}
}
return new int[0];
}
}

劍指 Offer 64. 求1+2+…+n

class Solution64 {

public static int sumNums(int n) {

boolean flag = n > 0 && (n += sumNums(n - 1)) == 0;
return n;
}
public static int sumNums2(int n) {

boolean flag = n <= 0 || (n += sumNums2(n - 1)) > 0;
return n;
}
public static void main(String[] args) {

System.out.println(sumNums2(5));
}
}

劍指 Offer 39. 數組中出現次數超過一半的數字

class Solution39 {

public int majorityElement(int[] nums) {

Arrays.sort(nums);
return nums[nums.length / 2];
}
}
class Solution39_2 {

private Map<Integer, Integer> countNums(int[] nums) {

Map<Integer, Integer> counts = new HashMap<>();
for (int num : nums) {

if (!counts.containsKey(num)) {

counts.put(num, 1);
} else {

counts.put(num, counts.get(num) + 1);
}
}
return counts;
}
public int majorityElement(int[] nums) {

Map<Integer, Integer> counts = countNums(nums);
int len = nums.length;
for (Map.Entry<Integer,Integer> entry : counts.entrySet()) {

if (entry.getValue() > len / 2){

return entry.getKey();
}
}
return -1;
}
}
版权声明:本文为[保護眼睛]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815044426375f.html