image.png
public String replaceSpaces(String S, int length) {
/*String res="";*/
StringBuilder builder = new StringBuilder("");
char[] arr=S.toCharArray();
for(int i=0;i<S.length();i++)
{
if(arr[i] ==' ')
{
builder.append("%20");
}
else {
builder.append(arr[i]);
}
}
return builder.toString();
}
public String replaceSpaces(String S, int length) {
char[] chs = S.toCharArray();
int i = length-1, j = S.length()-1;
while(i>=0){
if(chs[i]==' '){
chs[j--] = '0';
chs[j--] = '2';
chs[j--] = '%';
}else{
chs[j--] = chs[i];
}
i--;
}
return String.valueOf(chs,j+1, S.length()-j-1);
}
image.png
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i=0;i<nums.length;i++) {
if (!map.containsKey(target - nums[i]))
map.put(nums[i],i);
else
return new int[]{i, map.get(target - nums[i])};
}
return new int[]{};
}
image.png
image.png
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while(row < m && col >= 0) {
if(matrix[row][col] > target) {
col--;
}else if(matrix[row][col] < target) {
row++;
}else {
return true;
}
}
return false;
}
卡牌分组
public boolean hasGroupsSizeX(int[] deck) {
int[] count = new int[10000];
for (int c: deck)
count[c]++;
int g = -1;
for (int i = 0; i < 10000; ++i)
if (count[i] > 0) {
if (g == -1)
g = count[i];
else
g = gcd(g, count[i]);
}
return g >= 2;
}
public int gcd(int x, int y) {
return x == 0 ? y : gcd(y%x, x);
}
image.png
public void merge(int[] A, int m, int[] B, int n) {
int all=m+n-1;
int i=m-1;
int j=n-1;
while(i>=0&&j>=0)
{
if(A[i]<B[j])
{
A[all--]=B[j--];
}
else{
A[all--]=A[i--];
}
}
while(j>=0)
{
A[all--]=B[j--];
}
image.png
public int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int cur = nums[left] + nums[right];
if (cur == target)
return new int[]{nums[left], nums[right]};
else if (cur > target)
right--;
else
left++;
}
return new int[]{};
}
public int[] twoSum(int[] nums, int target) {
int[] res = {0,0};
int i=0, j=nums.length-1;
while(i<=j){
if(nums[i]+nums[j]<target) i++;
else if(nums[i]+nums[j]>target) j--;
else break;
}
res[0] = nums[i];
res[1] = nums[j];
return res;
}
image.png
public int search(int[] nums, int target) {
int res=0;
for(int num:nums)
{
if(num>target)
{
break;
}
if(num==target)
{
res++;
}
}
return res;
}
public int search(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int num:nums)
{
if(map.containsKey(num)){
map.put(num,map.get(num)+1);
}
else {
map.put(num, 1);
}
}
int res=0;
if(map.containsKey(target))
{
res=map.get(target);
}
return res;
}
public int search(int[] nums, int target) {
int len=nums.length-1;
int res=0;
res=binarySearch(nums,0,len,target);
return res;
}
public int binarySearch(int[] nums,int sta,int end,int target) {
int res = 0;
int temp = (sta+end) / 2;
if(sta==end){
if(target==nums[temp])
{
res++;
}
}
while (sta < end) {
if (target == nums[temp]) {
res++;
for (int i = temp + 1; i <= end; i++) {
if (nums[i] == target) {
res++;
} else {
break;
}
}
for (int i = temp - 1; i >= sta; i--) {
if (nums[i] == target) {
res++;
} else {
break;
}
}
return res;
} else if (target > nums[temp]) {
return binarySearch(nums, temp + 1, end, target);
} else {
return binarySearch(nums, 0, temp - 1, target);
}
}
return res;
}
image.png
既然数组中有出现次数> ⌊ n/2 ⌋的元素，那排好序之后的数组中，相同元素总是相邻的。
即存在长度> ⌊ n/2 ⌋的一长串 由相同元素构成的连续子数组。
举个例子：
无论是1 1 1 2 3，0 1 1 1 2还是-1 0 1 1 1，数组中间的元素总是“多数元素”，
毕竟它长度> ⌊ n/2 ⌋
public class one {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length >> 1];
}
}
public int majorityElement(int[] nums) {
int count = 0, last = 0;
for (int num: nums) {
if (count == 0) {
last = num;
}
count = count + (last == num? 1: -1);
}
return last;
}
image.png
public void moveZeroes(int[] nums) {
int j=0;
for(int i=0;i<nums.length;i++)
{
if(nums[i]!=0)
{
nums[j++]=nums[i];
}
}
while (j<nums.length)
{
nums[j++]=0;
}
}
image.png
public int findUnsortedSubarray(int[] nums) {
int[] copy=nums.clone();
Arrays.sort(copy);
int left=0,right=0;
for(int i=0;i<copy.length;i++)
{
if(copy[i]!=nums[i])
{
right=i;
break;
}
}
for(int i=copy.length-1;i>=left;i--)
{
if(copy[i]!=nums[i])
{
right=i;
break;
}
}
if(right==left)
{
return 0;
}
return right-left+1;
}
public int findUnsortedSubarray(int[] nums) {
int len = nums.length;
if(len <= 1) {
return 0;
}
int high = 0,low = len-1,curMax = Integer.MIN_VALUE,curMin=Integer.MAX_VALUE;
for(int i = 0;i<len;i++){
if(nums[i] >= curMax){
curMax = nums[i];
} else {
high = i;
}
if(nums[len-i-1] <= curMin){
curMin = nums[len-i-1];
} else {
low = len - i - 1;
}
}
return high > low ? high -low + 1 : 0;
}
image.png
public int missingNumber(int[] nums) {
for(int i=0;i<nums.length;i++){
if(nums[i]!=i){
return i;
}
}
return nums.length;
}
image.png
public int[] exchange(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
while (left < right && nums[left] % 2 != 0) {
left++;
}
while (left < right && nums[right] % 2 == 0) {
right--;
}
if (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
image.png
- 可看评论区
public int[] getLeastNumbers(int[] arr, int k) {
List<Integer> al=new ArrayList<>();
for(Integer a:arr)
{
al.add(a);
}
al.sort(null);
Integer[] array=al.toArray(new Integer[al.size()]);
int[] res=new int[k];
for(int i=0;i<k;i++){
res[i]=array[i];
}
return res;
}
public int[] getLeastNumbers(int[] arr, int k) {
//return solA(arr, k);
quickSort(arr, 0, arr.length - 1, k);
return Arrays.copyOf(arr, k);
}
//单边快排（快速选择算法）
//每次剪枝一半的区间，即piviot在k左侧，则左侧不用管了（必然已经是前k个数的一部分）。
//在右则，右侧不用管了（必然不在前k数区间）
private void quickSort(int[]arr, int l, int r, int k){
if(l >= r) return;
int i = l - 1, j = r + 1, x = arr[l];
while(i < j){
while(arr[++i] < x);
while(arr[--j] > x);
if(i < j){
int t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
if(k <= j) quickSort(arr, l, j, k);
else quickSort(arr, j + 1, r, k);
}
//维护大小k的堆 nlogk
private int[] solA(int[]arr, int k){
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2)->{
return o2 - o1;
});
for(int i = 0; i < arr.length; i++){
if(pq.size() < k) pq.add(arr[i]);
else if(pq.size() == k && arr[i] < pq.peek()){
pq.poll();
pq.add(arr[i]);
}
}
Integer[] res = new Integer[k];
/*Java中 的java.util.PriorityQueue.toArray（arr []）
方法用于形成与Priority Queue相同元素的数组。
基本上，它将所有元素从优先级队列复制到新数组。
它创建了多个数组，与之前没有参数的方法不同。此方法将所有元素复制到arr []中。*/
pq.toArray(res);
int[] ans = new int[k];
for(int i = 0; i < k; i++) ans[i] = res[i];
return ans;
}
