二分查找：
public int search(int[] nums, int target) {
int left=0;
int right=nums.length;
while(left<right){
int mid=(left+right)>>>1;
if(nums[mid]==target){
return mid;
}else if(target<nums[mid]){
right=mid;
}else{
left=mid+1;
}
}
return -1;
}public int search(int[] nums, int target) {
int left=0,right=nums.length-1;
while(left<=right){
int mid=(left+right)>>>1;
if(target<nums[mid]){
right=mid-1;
}else if(nums[mid]<target){
left=mid+1;
}else{
return mid;
}
}
return -1;
}搜索插入位置：
方法一：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。就是查找>=target的元素，对于查找存在重复元素，返回最左边的元素。
public int searchInsert(int[] nums, int target) {
int left=0,right=nums.length-1;
while (left<=right){
int mid=(left+right)>>>1;
if (target<=nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
}
return left;
}方法二：
public int searchInsert(int[] nums, int target) {
int left=0,right=nums.length;
while (left<right){
int mid=(left+right)>>>1;
if (target<=nums[mid]){
right=mid;
}else{
left=mid+1;
}
}
return left;
}按奇偶排序数组II
方法一：先将数组遍历，分别将奇数和偶数放入两个数组中
public int[] sortArrayByParityII(int[] nums) {
int[] ou=new int[nums.length/2];
int[] ji=new int[nums.length/2];
int o=0,j=0;
for (int i = 0; i < nums.length; i++) {
if (nums[i]%2==0) ou[o++]=nums[i];
else ji[j++]=nums[i];
}
o=0;j=0;
for (int i = 0; i < nums.length; i++) {
if (i%2==0){
nums[i]=ou[o++];
}else{
nums[i]=ji[j++];
}
}
return nums;
}方法二：维护两个索引代表偶数和奇数的索引
public int[] sortArrayByParityII(int[] nums) {
int ou=0,ji=1;
int[] res=new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (nums[i]%2==0){
res[ou]=nums[i];
ou+=2;
}else{
res[ji]=nums[i];
ji+=2;
}
}
return res;
}方法三：在原数组中进行修改
public int[] sortArrayByParityII3(int[] nums) {
int ji=1;
for (int i = 0; i < nums.length; i+=2) {
if (nums[i]%2!=0){
//偶数位遇到奇数
while (nums[ji]%2!=0){
ji+=2;
}
swap(nums,i,ji);
}
}
return nums;
}在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
思路：就是查找目标元素最左边的元素和最右边的元素。查找最左边元素就是找到目标值后继续向左找，查找最右边元素同理。
public int[] searchRange(int[] nums, int target) {
int leftMost = getLeftMost(nums, target);
if (leftMost==-1){
return new int[]{-1,-1};
}
return new int[]{leftMost,getRightMost(nums,target)};
}
private int getLeftMost(int[] nums,int target){
int left=0,right=nums.length-1;
int candiate=-1;
while (left<=right){
int mid=(left+right)>>>1;
if (nums[mid]<target){
left=mid+1;
}else if (target<nums[mid]){
right=mid-1;
}else{
candiate=mid;
right=mid-1;
}
}
return candiate;
}
private int getRightMost(int[] nums,int target){
int left=0,right=nums.length-1;
int candiate=-1;
while (left<=right){
int mid=(left+right)>>>1;
if (nums[mid]<target){
left=mid+1;
}else if (target<nums[mid]){
right=mid-1;
}else{
candiate=mid;
left=mid+1;
}
}
return candiate;
}寻找数组的中心下标：
示例：
- 输入：nums = [1, 7, 3, 6, 5, 6]
- 输出：3
- 解释：中心下标是 3。左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
public int pivotIndex(int[] nums) {
for (int i = 1; i < nums.length; i++) {
nums[i]=nums[i-1]+nums[i];
}
if (nums[nums.length-1]-nums[0]==0){
return 0;
}
for (int i = 1; i < nums.length; i++) {
if (nums[i-1]==nums[nums.length-1]-nums[i]){
return i;
}
}
return -1;
}
使用前缀和。
轮转数组：
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
public void rotate(int[] nums, int k) {
k=k%nums.length;
reverse(nums,0,nums.length-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.length-1);
}
private void reverse(int[] nums,int start,int end){
while (start<end){
int temp=nums[start];
nums[start]=nums[end];
nums[end]=temp;
start++;
end--;
}
}反转字符串II
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
for (int i = 0; i < s.length(); i+=(2*k)) {
if (i+k<s.length()){
reverse(chars,i,i+k-1);
}else{
reverse(chars,i,s.length()-1);
}
}
return new String(chars);
}
private void reverse(char[] nums,int start,int end){
while (start<end){
char temp=nums[start];
nums[start]=nums[end];
nums[end]=temp;
start++;
end--;
}
}移动零：
public void moveZeroes(int[] nums) {
int j=0;
for (int i = 0; i < nums.length; i++) {
if (nums[i]!=0){
nums[j++]=nums[i];
}
}
for (int i = j; i <nums.length ; i++) {
nums[i]=0;
}
}有多少个小于当前数字的数字：
示例：
输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3]
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] temp=new int[nums.length];
System.arraycopy(nums,0,temp,0,nums.length);
Arrays.sort(temp);
Map<Integer,Integer> map=new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(temp[i])){
map.put(temp[i],i);
}
}
for (int i = 0; i < nums.length; i++) {
nums[i]=map.get(nums[i]);
}
return nums;
}计数排序：
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] cnt=new int[101];
for (int i = 0; i < nums.length; i++) {
cnt[nums[i]]++;
}
for (int i = 1; i <=100; i++) {
cnt[i]=cnt[i-1]+cnt[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i]=nums[i]==0?0:cnt[nums[i]-1];
}
return nums;
}有效的山脉数组
public boolean validMountainArray(int[] arr) {
if (arr.length<3){
return false;
}
if (arr[0]>arr[1]){
return false;
}
if (arr[arr.length-1]>arr[arr.length-2]){
return false;
}
int i=1;
while (i<arr.length){
while (arr[i-1]<arr[i]){
i++;
}
if (arr[i-1]==arr[i]){
return false;
}
while (i<arr.length&&arr[i-1]>arr[i]){
i++;
}
if (i<arr.length-1){
return false;
}
}
return true;
}x的平方根：
方法一：√x==e^(1/2lnx);
public int mySqrt(int x) {
if (x==0){
return 0;
}
int ans= (int) Math.exp(0.5*Math.log(x));
return (long)(ans+1)*(ans+1)<=x?ans+1:ans;
}方法二：二分查找（long）mid*mid
public int mySqrt2(int x) {
int i=0,j=x;
int ans=-1;
while (i<=j){
int mid=(i+j)>>>1;
if ((long)mid*mid<=x){
i=mid+1;
ans=mid;
}else{
j=mid-1;
}
}
return ans;
}有效的完全平方数：
public boolean isPerfectSquare(int num) {
if (num==0||num==1){
return true;
}
int left=2,right=num;
while (left<=right){
int mid=(left+right)>>>1;
if ((long)mid*mid==num){
return true;
}else if ((long)mid*mid<num){
left=mid+1;
}else{
right=mid-1;
}
}
return false;
}知道代码随想录太迟了，这么好的网站现在才知道，相见恨晚，大三下了，希望来的及。