JZ66 构建乘积数组
/* 暴力 */
public class JZ66_1
{
public static int[] multiply(int[] A)
{
int[] res = new int[A.length];
Arrays.fill(res, 1);
for (int i = 0; i < A.length; i++)
{
for (int j = 0; j < A.length; j++)
{
if (j == i) continue;
res[i] *= A[j];
}
}
return res;
}
}
/* 根据 i 分成两部分 */
public class JZ66_2
{
public static int[] multiply(int[] A)
{
int[] res = new int[A.length];
int temp = 1;
res[0] = 1;
for (int i = 1; i < A.length; i++)
res[i] = res[i - 1] * A[i - 1];
for (int i = A.length - 1; i >= 0; i--)
{
res[i] *= temp;
temp *= A[i];
}
return res;
}
}
JZ50 第一个只出现一次的字符
/* hashmap */
public class JZ50_1
{
public static int FirstNotRepeatingChar(String str)
{
HashMap<Character, Integer> map = new HashMap<>();
int res = Integer.MAX_VALUE;
for (int i = 0; i < str.length(); i++)
{
if (!map.containsKey(str.charAt(i)))
map.put(str.charAt(i), i);
else
map.remove(str.charAt(i));
}
Set<Character> characters = map.keySet();
for (char ch : characters)
{
int idx = map.get(ch);
if (idx < res)
res = idx;
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
JZ5 替换空格
public class JZ5_1
{
public static String replaceSpace(String s)
{
return s.replace(" ", "%20");
}
}
/* 双指针 */
public class JZ5_2
{
public static String replaceSpace(String s)
{
int spaceNum = 0, newLen, oldLen = s.length();
for (int i = 0; i < oldLen; i++)
if (s.charAt(i) == ' ') spaceNum++;
newLen = s.length() + spaceNum * 2;
StringBuilder str = new StringBuilder(s);
str.setLength(newLen);
newLen--;
for (oldLen--; oldLen >= 0; oldLen--)
{
if (s.charAt(oldLen) == ' ')
{
str.setCharAt(newLen--, '0');
str.setCharAt(newLen--, '2');
str.setCharAt(newLen--, '%');
}
else
str.setCharAt(newLen--, s.charAt(oldLen));
}
return str.toString();
}
}
JZ21 调整数组顺序使奇数位于偶数前面(一)
/* 双指针 */
public class JZ21_1
{
public static int[] reOrderArray(int[] array)
{
int[] res = new int[array.length];
int left = 0, right = array.length - 1, l = left, r = right;
while (left < array.length && right >= 0)
{
if (array[left] % 2 != 0)
res[l++] = array[left];
left++;
if (array[right] % 2 == 0)
res[r--] = array[right];
right--;
}
return res;
}
}
/* 遇到奇数,就把他按顺序放到前面 */
public class JZ21_2
{
public static int[] reOrderArray(int[] array)
{
int left = 0;
for (int i = 0; i < array.length; i++)
{
if (array[i] % 2 == 0) continue;
int temp = array[i];
for (int j = i; j > left; j--)
array[j] = array[j - 1];
array[left] = temp;
left++;
}
return array;
}
}
JZ39 数组中出现次数超过一半的数字
/* ⭐摩尔投票算法⭐ */
public class JZ39_1
{
public static int MoreThanHalfNum_Solution(int[] numbers)
{
int count = 0, res = -1;
for (int num : numbers)
{
if (count == 0)
{
res = num;
count++;
}
else
{
if (res == num) count++;
else
count--;
}
}
return res;
}
}
/* 快排 */
public class JZ39_2
{
public static int MoreThanHalfNum_Solution(int[] numbers)
{
int mid = numbers.length / 2, s = 0, e = numbers.length - 1;
int index = partition(numbers, s, e);
while (index != mid)
{
if (index > mid)
e = index - 1;
else
s = index + 1;
index = partition(numbers, s, e);
}
return numbers[mid];
}
public static int partition(int[] numbers, int left, int right)
{
int pivot = numbers[right];
while (left < right)
{
while (left < right && numbers[left] <= pivot) left++;
numbers[right] = numbers[left];
while (right > left && numbers[right] >= pivot) right--;
numbers[left] = numbers[right];
}
numbers[left] = pivot;
return left;
}
}
JZ43 整数中1出现的次数(从1到n整数中1出现的次数)⭐
/* 个位 + 十位 + 百位 + ... */
public class JZ43_1
{
public static int NumberOf1Between1AndN_Solution(int n)
{
int round = n, weight, extra, base = 1, res = 0;
while (round != 0)
{
weight = round % 10;
round /= 10;
extra = n % base;
res += round * base;
if (weight == 1) res += 1 + extra;
if (weight > 1) res += base;
base *= 10;
}
return res;
}
}
/* 最高位1的个数 + 其他位1的个数(左神) */
public class JZ43_2
{
public static int NumberOf1Between1AndN_Solution(int n)
{
if (n < 1)
return 0;
int len = getLenOfNum(n);
if (len == 1)
return 1;
int tmp = (int) Math.pow(10, len - 1);
int first = n / tmp;
int firstOneNum = first == 1 ? n % tmp + 1 : tmp;
int otherOneNUm = first * (len - 1) * (tmp / 10);
System.out.println(firstOneNum);
System.out.println(otherOneNUm);
return firstOneNum + otherOneNUm + NumberOf1Between1AndN_Solution(n % tmp);
}
public static int getLenOfNum(int n)
{
int len = 0;
while (n != 0)
{
len++;
n /= 10;
}
return len;
}
}
/* 数位DP */
public class JZ43_3
{
public static int[] num = new int[20];
public static int[][] dp = new int[25][20];
public static int NumberOf1Between1AndN_Solution(int n)
{
for (int[] dps : dp) Arrays.fill(dps, -1);
int k = 0;
while (n != 0)
{
num[++k] = n % 10;
n /= 10;
}
return dfs(k, 0, true);
}
public static int dfs(int pos, int cnt, boolean limit)
{
if (pos == 0) return cnt;
if (!limit && dp[pos][cnt] != -1) return dp[pos][cnt];
int top = limit ? num[pos] : 9, res = 0;
for (int i = 0; i <= top; i++)
res += dfs(pos - 1, cnt + (i == 1 ? 1 : 0), limit && (i == top));
if (!limit) dp[pos][cnt] = res;
return limit ? res : dp[pos][cnt];
}
}
JZ45 把数组排成最小的数⭐
/* (o1 + o2).compareTo(o2 + o1); */
public class JZ45_1
{
public static String PrintMinNumber(int[] numbers)
{
String[] temp = new String[numbers.length];
for (int i = 0; i < numbers.length; i++)
temp[i] = Integer.toString(numbers[i]);
Arrays.sort(temp, new Comparator<String>()
{
@Override
public int compare(String o1, String o2)
{
return (o1 + o2).compareTo(o2 + o1);
}
});
StringBuilder res = new StringBuilder();
for (String str : temp)
res.append(str);
return res.toString();
}
}
JZ49 丑数⭐
/* 模拟 */
public class JZ49_1
{
public static int GetUglyNumber_Solution(int index)
{
if (index == 0) return 0;
int[] res = new int[index];
int idx = 1, twoIdx = 0, threeIdx = 0, fiveIdx = 0;
res[0] = 1;
while (idx < index)
{
int val = Math.min(res[twoIdx] * 2, Math.min(res[threeIdx] * 3, res[fiveIdx] * 5));
res[idx++] = val;
while (2 * res[twoIdx] <= res[idx - 1])
twoIdx++;
while (3 * res[threeIdx] <= res[idx - 1])
threeIdx++;
while (5 * res[fiveIdx] <= res[idx - 1])
fiveIdx++;
}
return res[index - 1];
}
}
JZ74 和为S的连续正数序列
/* 滑动窗口 */
public class JZ74_1
{
public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum)
{
int left = 0, right = 0, s = 0;
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
while (right < sum)
{
if (s == sum)
{
ArrayList<Integer> temp = new ArrayList<>();
for (int i = left + 1; i <= right; i++)
temp.add(i);
res.add(temp);
}
if (s < sum)
{
right++;
s += right;
}
else
{
left++;
s -= left;
}
}
return res;
}
}
JZ57 和为S的两个数字
/* 双指针 */
public class JZ57_1
{
public static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum)
{
int left = 0, right = array.length - 1;
ArrayList<Integer> res = new ArrayList<>();
while (left < right)
{
if (array[left] + array[right] < sum)
left++;
else if (array[left] + array[right] > sum)
right--;
else
{
res.add(array[left]);
res.add(array[right]);
break;
}
}
return res;
}
}
/* hashmap */
public class JZ57_2
{
public static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum)
{
HashMap<Integer, Integer> map = new HashMap<>();
ArrayList<Integer> res = new ArrayList<>();
for (int num : array)
{
if (map.containsKey(num))
{
res.add(num);
res.add(map.get(num));
break;
}
map.put(sum - num, num);
}
return res;
}
}
标签:return,offer,int,res,算法,其他,array,public,left
From: https://www.cnblogs.com/VividBinGo/p/17727906.html