Sword finger Offer 53 - I. find the number I in the sorted array
Counts the number of times a number appears in the sorted array.
Problem solving idea: binary search
class Solution {
public int search(int[] nums, int target) {
if(nums==null||nums.length==0||target<nums[0]||target>nums[nums.length-1])return 0;
int left,right;
int i=0,j=nums.length-1;
while(i<=j){
int mid=(i+j)/2;
if(nums[mid]<=target)i=mid+1;
else j=mid-1;
}
right=i;
if(j >= 0 && nums[j] != target) return 0;
i=0;j=right-1;
while(i<=j){
int mid=(i+j)/2;
if(nums[mid]>=target)j=mid-1;
else i=mid+1;
}
left=i;
return right-left;
}
}
Missing numbers in sword finger Offer 53 - II. 0 ~ n-1
All numbers in an incremental sort array with length n-1 are unique, and each number is in the range of 0 ~ n-1. Among the N numbers in the range 0 ~ n-1, there is only one number that is not in the array. Please find this number.
Solution: dichotomy
class Solution {
public int missingNumber(int[] nums) {
if(nums.length==1)return nums[0]==0?1:0;
int i=0,j=nums.length-1;
while(i<=j){
int mid=(j+i)/2;
if(nums[mid]==mid)i=mid+1;
else j=mid-1;
}
return j+1;
}
}
Sword finger Offer 54. The k-th node of the binary search tree
Given a binary search tree, please find the k-largest node.
Problem solving idea: recursion
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int k,ans;
public int kthLargest(TreeNode root, int k) {
this.k=k;
visit(root);
return ans;
}
public void visit(TreeNode root){
if(root.right!=null)visit(root.right);
--k;
if(k==0){
ans=root.val;
return;
}
if(root.left!=null) visit(root.left);
}
}
Sword finger Offer 55 - I. depth of binary tree
Enter the root node of a binary tree to find the depth of the tree. The nodes (including root and leaf nodes) passing from root node to leaf node form a path of the tree, and the length of the longest path is the depth of the tree.
Problem solving idea: recursion
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)return 0;
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
Sword finger Offer 55 - II. Balanced binary tree
Enter the root node of a binary tree to judge whether the tree is a balanced binary tree. If the depth difference between the left and right subtrees of any node in a binary tree is no more than 1, it is a balanced binary tree.
Problem solving idea: recursion
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return visit(root)!=-1;
}
public int visit(TreeNode root){
if(root==null)return 0;
int left=visit(root.left);
if(left==-1)return -1;
int right=visit(root.right);
if(right==-1)return -1;
return (left-right)>=-1&&(left-right)<=1?Math.max(left,right)+1:-1;
}
}
Sword finger Offer 57. And are two numbers of s
Enter an incrementally sorted array and a number s, and find two numbers in the array so that their sum is exactly s. If the sum of multiple pairs of numbers is equal to s, any pair can be output.
Solution idea: double pointer
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums.length<=1||target<nums[0]||target>2*nums[nums.length-1])return new int[0];
int i=0,j=nums.length-1;
int[] ans=new int[2];
while(i<j){
if(nums[i]+nums[j]==target){
ans[0]=nums[i];
ans[1]=nums[j];
return ans;
}else if(nums[i]+nums[j]<target){
++i;
}else{
--j;
}
}
return ans;
}
}
Sword finger Offer 57 - II. Continuous positive sequence with sum of s
Enter a positive integer target and output a sequence of consecutive positive integers with a sum of target (at least two numbers). The numbers in the sequence are arranged from small to large, and different sequences are arranged from small to large according to the first number.
Solution idea: double pointer, sliding window
class Solution {
public int[][] findContinuousSequence(int target) {
if(target==1){
int[][] ans=new int[1][1];
ans[0][0]=1;
return ans;
}
ArrayList<int[]> ans=new ArrayList<int[]>();
int i=1,j=2,sum=1;
while(j<=target/2+1){
sum=(i+j)*(j-i+1)/2;
if(sum<target)++j;
else if(sum==target){
int[] item=new int[j-i+1];
for(int k=i;k<=j;++k){
item[k-i]=k;
}
ans.add(item);
++i;
}else{
++i;
}
}
return ans.toArray(new int[ans.size()][]);
}
}
Sword finger Offer 58 - I. flip word order
Input an English sentence and flip the order of words in the sentence, but the order of characters in the word remains the same. For simplicity, punctuation is treated like ordinary letters. For example, if you enter the string "I am a student.", you will output "student. a am I".
Problem solving idea: traverse from back to front
class Solution {
public String reverseWords(String s) {
char[] ch=s.trim().toCharArray();
if(ch.length==0)return "";
int index=ch.length-1;
StringBuilder ans=new StringBuilder();
for(int i=index;i>=0;){
// First space found
int j=i;
while(j>=0&&ch[j]!=' '){
--j;
}
ans.append(ch,j+1,i-j);
ans.append(" ");
// Skip multiple spaces
while(j>=0&&ch[j]==' '){
--j;
}
i=j;
}
return ans.toString().trim();
}
}
Sword finger Offer 58 - II. Left rotation string
The left rotation operation of a string is to transfer several characters in front of the string to the end of the string. Please define a function to realize the function of string left rotation operation. For example, if you enter the string "abcdefg" and the number 2, the function will return the result "cdefgab" obtained by rotating two bits left.
class Solution {
public String reverseLeftWords(String s, int n) {
if(s==null||s.length()==0)return s;
return s.substring(n,s.length())+s.substring(0,n);
}
}
Sword finger Offer 65. Add without addition, subtraction, multiplication and division
Write a function and find the sum of two integers. It is required that four operation symbols "+", "-", "*", "/" shall not be used in the function body.
Example:
Input: a = 1, b = 1
Output: 2