數據結構與演算法系列一之整數、數組及字元串
前言：由於本人不是科班出身，電腦基礎相對薄弱一些，最近在工作之餘想系統的學習一下數據結構與演算法，主要是通過學習專項突破版的劍指Offer每一部分的典型題目，將每一部分相關的基礎內容盡量掌握一下。由於沒有太多時間將看過的基礎內容都總結整理起來，因此先將題目根據書中的講解和自己的理解整理一下，後續有時間再系統整理一下每一部分的基礎知識。
第一章 整數
1、整數除法
題目：輸入 2 個 int 型整數，他們進行除法計算並返回商，要求不得使用乘號’*’、除號’/’及求余符號’%’。當發生溢出時，返回最大的整數值。假設除數不為0。例如，輸入 15 和 2 ，輸出 15/2 的結果，即 7 。
import java.util.Scanner;
public class test0101 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = Integer.parseInt(sc.next());
int b = Integer.parseInt(sc.next());
if (a==0x80000000 && b==-1){
System.out.println(Integer.MAX_VALUE);
}else {
//由於正數int最大為2^31-1，負數int最小為2^31，所以將除數與被除數都轉換成負數來進行計算，防止越界
//0x80000000是-2^31,0xc0000000是-2^30
int flag = 2; //使用flag來控制結果的正負符號
if (a>0){
flag--;
a=-a;
}
if (b>0){
flag--;
b=-b;
}
int result = divide(a, b);
result = flag == 1 ? -result : result; //當除數與被除數符號不同時結果為負
System.out.println(result);
}
}
//設置初始值 res=0,countNum=1,value=b,
private static int divide(int a,int b){
int res = 0; //結果初始值為0
while (a>=b){ //當被除數>除數時進入循環
int countNum = 1; //設置倍數初始值為1
int value = b; //將除數的值賦給value，用於後續處理
while (value>=0xc0000000 && a <= value+value){ //當被除數<除數的兩倍時進入循環(負數)，防止2倍value越界，需要保證value>=0xc0000000
countNum+=countNum; //倍數通過相加翻倍
value+=value; //value也通過相加翻倍
}
a-=value; //當被除數>value的兩倍時，被除數a-value，再進行循環
res+=countNum; //結果加上被除數減去的value的倍數countNum
}
return res;
}
}
2、二進位加法
題目：輸入兩個表示二進位的字元串，請計算它們的和，並以二進位字元串的形式輸出。例如，輸入的二進位字元串分別是”11″和”10″，則輸出”101″。
import java.util.Scanner;
public class test0201 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
String s = add(str1, str2);
System.out.println(s);
}
private static String add(String str1,String str2){
StringBuilder res = new StringBuilder(); //實例化一個StringBuilder()類
int l1 = str1.length()-1; //獲取輸入的字元串長度，用於後續獲取字元，由於字元序號是0~length-1，因此獲取值為字元串長度length-1
int l2 = str2.length()-1;
int num01 = 0;
int num02 = 0;
int sum = 0;
int forward = 0;
while (l1>=0 || l2>=0){ //當兩個字元串中有一個還有剩餘未計算的數字時，進入循環
num01 = l1>=0?str1.charAt(l1--)-'0':0; //當字元串長度大於0時，獲取當前進行計算的數值，然後將字元串長度-1；字元串長度等於0時，數值設為0
num02 = l2>=0?str2.charAt(l2--)-'0':0;
sum = num01 + num02 +forward; //計算當前位的數值及進位的數值之和
forward = sum>=2 ? 1:0; //當和大於等於2時，進位為1，否則進位為0
sum = sum>=2?sum-2:sum; //當和大於等於2時，由於已經進位，因此和-2作為當前位的數值
res.append(sum); //結果添加當前位的數值
}
if (forward==1){ //如果兩個字元串所有位的數值都計算完了，那麼判斷進位是否還有數值1，有則在結果中添加1
res.append(1);
}
return res.reverse().toString(); //由於append是在字元串最後添加當前位數值，因此結果要進行反轉才是最終結果字元串
}
}
3、前 n 個數字二進位形式中 1 的個數
題目：輸入一個非負數 n ，請計算 0 到 n 之間每個數字的二進位形式中 1 的個數，並輸出一個數組。例如，輸入的 n 為 4，由於0、1、2、3、4 的二進位形式中 1 的個數分別為 0、1、1、2、1，因此輸出數組[0,1,1,2,1]。
解法一：
import java.util.Scanner;
public class test0301 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //獲取輸入的數值
int in = sc.nextInt();
int[] result = count(in);
sc.close(); //輸入完後不要忘了關閉Scanner降低系統資源佔用
for (int i : result) { //遍歷結果輸出，以空格為間隔
System.out.print(i+" ");
}
}
private static int[] count(int in){
int[] res = new int[in + 1];
for (int i = 0; i <= in; i++) { //遍歷0到該數值，將每次遍歷到的數值轉換為二進位字元串
String s = Integer.toBinaryString(i);
int contain = 0;
for (int j = 0; j < s.length(); j++) { //遍歷字元串每個字元，有1則結果數組中該位置結果+1
if (s.charAt(j)=='1'){
contain++;
}
}
res[i] = contain;
}
return res;
}
}
解法二：
import java.util.Scanner;
public class test0302 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int in = sc.nextInt();
int[] result = add(in);
sc.close();
for (int i : result) {
System.out.print(i+" ");
}
}
private static int[] add(int in){
int[] res = new int[in + 1]; //初始化一個結果數組
for (int i = 0; i <= in; i++) { //遍歷需要計算1個數的每一個數值
int j = i;
while (j != 0){ //當前數值不為0，則一定存在1，當前數值的結果+1
res[i]++;
j=j&(j-1); //將當前數值的最後一個1去掉，通過j&(j-1)
}
}
return res;
}
}
解法三：
import java.util.Scanner;
public class test0303 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int in = sc.nextInt();
int[] result = add(in);
sc.close();
for (int i : result) {
System.out.print(i+" ");
}
}
private static int[] add(int in){
int[] res = new int[in + 1];
for (int i = 1; i < in; i++) {
res[i] = res[i&(i-1)]+1;
}
return res;
}
}
解法四：
import java.util.Scanner;
public class test0304 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //獲取輸入的數值，輸入完畢不要忘了關閉Scanner
int in = sc.nextInt();
int[] result = add(in);
sc.close();
for (int i : result) {
System.out.print(i+" ");
}
}
private static int[] add(int in){
int[] res = new int[in + 1]; //新建一個結果數組
for (int i = 0; i <= in; i++) { //從小到大遍歷0到目標數值
//當前數值為偶數時，最後一位為0，數值中1的個數與當前數值右移一位中1的個數相等；
//當前數值為奇數時，最後一位為1，數值中1的個數=當前數值右移一位中1的個數+1；
//可以通過按位與運算 i&1 來實現奇數+1，偶數+0
res[i] = res[i>>1] + (i&1); //當前數值中1的個數，是當前數值右移1位的數值的1的個數+當前數值&1
}
return res;
}
}
4、只出現一次的數字
題目：輸入一個整數數組，數組中只有一個數字出現了一次，而其他數字都出現了 3 次。請找出那個只出現一次的數字。例如，如果輸入的數組為[0,1,0,1,0,1,100]，則只出現一次的數字是 100。
解法一：
import java.util.ArrayList;
import java.util.Scanner;
public class test0401 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //獲取用戶輸入的數組
ArrayList<String> in = new ArrayList<>(); //新建數組，保存用戶的輸入數值
int i;
int max = 0;
String str;
while (sc.hasNextInt()){ //循環接收輸入的數值
i = sc.nextInt();
str = Integer.toBinaryString(i); //把輸入的整數轉換為二進位字元串進行後續處理
if (str.length()>max){ //獲取字元串最大長度，以便後續初始化中間數組
max=str.length();
}
in.add(str); //向數組中添加字元串
}
sc.close();
int result = query(in, max);
System.out.println(result);
}
private static int query(ArrayList<String> list,int max){
int res = 0;
StringBuilder stringBuilder = new StringBuilder(); //初始化一個可變長字元串用於後續獲取結果
int[] contains = new int[max]; //新建一個數組用來保存所有輸入數值每一位相加的結果
for (String s : list) { //循環遍歷所有二進位字元串的每一位，並將所有字元串相同位的數值相加
for (int i = 0; i < s.length(); i++) {
contains[i] = contains[i] + (s.charAt(i)-'0');
}
}
//由於只有一個數值出現一次，其他數值都出現三次，因此所有位數值之和與3求余，為1時只出現一次的數值該位為1，為0時只出現一次的數值該位為0
for (int i = 0; i < contains.length; i++) { //遍歷保存所有位數值之和的數組，每位的和%3，將所有結果進行拼接
stringBuilder.append(contains[i] % 3);
}
res = Integer.parseInt(stringBuilder.toString(),2); //將所有位與3求余拼接後的結果轉換為整數
return res;
}
}
解法二：
import java.util.ArrayList;
import java.util.Scanner;
public class test0402 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //接收輸入的數組
ArrayList<Integer> list = new ArrayList<>();
int i;
while (sc.hasNextInt()){ //循環接收輸入的數字
i = sc.nextInt();
list.add(i);
}
System.out.println(query(list));
sc.close();
}
private static int query(ArrayList<Integer> list){
int[] contains = new int[32]; //因為整數就是32位的，所以新建一個容量32的數組，保存輸入數字每一位和的結果
int res = 0;
for (Integer integer : list) { //遍歷輸入數組的每一個數值
for (int i = 0; i < 32; i++) { //遍歷每一個數值的每一個二進位位
//通過 (integer>>(31-i))&1 來獲取第i位的數值0或1，注意i為0-31，數值位數為1-32，是從左往右的順序
contains[i] += (integer>>(31-i))&1; //i=0時，就是第一位，一定要保證運算的順序
}
}
for (int i = 0; i < 32; i++) { //遍歷保存每一位和的數組
//當前結果左移一位，使當前位數字為0，再通過 contains[i]%3 來獲得當前位的數值，通過相加，把該數值放到結果res的當前位
res = (res << 1) + (contains[i] % 3);
}
return res;
}
}
5、單詞長度的最大乘積
題目：輸入一個字元串數組 words，請計算不包含相同字元的兩個字元串 words[i] 和 words[j] 的長度乘積的最大值。如果所有字元串都包含至少一個相同字元，那麼返回 0。假設字元串中只包含英文小寫字母。例如，輸入的字元串數組 words 為[“abcw”,”foo”,”bar”,”fxyz”,”abcdef”]，數組中的字元串”bar”與”foo”沒有相同的字元，它們長度的乘積為 9。”abcw”與”fxyz”也沒有相同的字元，它們長度的乘積為 16，這是該數組不包含相同字元的一對字元串的長度乘積的最大值。
解法一：
import java.util.ArrayList;
import java.util.Scanner;
public class test0501 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<String> list = new ArrayList<>();
while (sc.hasNextLine()){ //逐行循環輸入字元串，連續回車兩次結束輸入
String s = sc.nextLine();
if (s.equals(""))break; //控制輸入結束
list.add(s);
}
list.forEach(System.out::println);
// ArrayList<String> strings = new ArrayList<>();
// strings.add("abcw");
// strings.add("foo");
// strings.add("bar");
// strings.add("fxyz");
// strings.add("abcdef");
//
// int res = multiply(strings);
// System.out.println(res);
}
private static int multiply(ArrayList<String> list){
int max = 0;
//由於字元中只會出現26個小寫字母，因此新建字元串個數個26空間大小的數組
Boolean[][] booleans = new Boolean[list.size()][26];
//位運算包括：與& 或| 異或^(相當於兩個字元串或運算減去與運算) 取反~
for (int i = 0; i < booleans.length; i++) { //一定要給Boolean數組進行賦值，否則會報空指針異常
for (int j = 0; j < 26; j++) {
booleans[i][j] = false;
}
}
for (int i = 0; i < list.size(); i++) { //遍歷每個字元串中的每個字元，按字元位於字母表中的位置，將Boolean數組中對應位置設為true
for (char c : list.get(i).toCharArray()) {
int num = c-'a'; //通過字元c-'a'來獲取當前字元在字母表中的位置
booleans[i][num] = true;
}
}
for (int i = 0; i < list.size()-1; i++) { //遍歷保存每個字元串中字母的數組
for (int j = i+1; j < list.size(); j++) {
int k = 0;
for (; k < 26; k++) {
if (booleans[i][k] && booleans[j][k]){ //如果兩個字元串字母數組中有同為true的字母，則中止此次循環
break;
}
}
if (k==26){ //如果遍歷兩個字元串字母數組都沒有同為true的字母，則計算字元串長度乘積，保存乘積的最大值
max = Math.max(max,list.get(i).length()*list.get(j).length());
}
}
}
return max;
}
}
解法二：
public class test0502 {
public static void main(String[] args) {
String[] str = {"abcw","foo","bar","fxyz","abcdef"};
int result = multiply(str);
System.out.println(result);
}
private static int multiply(String[] str){
int res = 0;
//由於int類型數字有32位，字母只有26個，所以可以用int類型的二進位數字來保存字元串中包含的字母資訊
//後續通過按位與運算&，比較不同字元串是否有重複字元，如果有則結果不為0，沒有則結果為0
int[] ints = new int[str.length]; //新建一個字元串數組長度的int數組，其中每個元素初始值都為0
for (int i = 0; i < str.length; i++) { //遍歷每個字元串的每個字元
for (char c : str[i].toCharArray()) {
//通過1左移c-'a'位來使字元c對應位置的數值變為1，通過與該字元串對應的二進位數字 取或|，來使該字元串對應二進位數字中的所有字元對應的位置為1
ints[i] |= 1<<(c-'a');
}
}
for (int i = 0; i < ints.length; i++) { //遍歷比較不同字元串對應的數值
for (int j = i+1; j < ints.length; j++) {
if ((ints[i] & ints[j])==0){ //如果兩個字元串對應的數值按位與運算結果為0，則這兩個字元串不包含相同字元
res = Math.max(res,str[i].length()*str[j].length()); //計算這兩個字元串長度的乘積，保存乘積的最大值
}
}
}
return res;
}
}
第二章 數組
6、排序數組中的兩個數字之和
題目：輸入一個遞增排序的數組和一個值 k，請問如何在數組中找出兩個和為 k 的數字並返回他們的下標？假設數組中存在且只存在一對符合條件的數字，同時一個數字不能使用兩次。例如，輸入數組[1,2,4,6,10]，k的值為 8，數組中的數字 2 與 6 的和為 8，它們的下標分別為 1 與 3。
解法一：
public class test0101 {
public static void main(String[] args) {
int[] in = {1,2,4,6,10};
int k = 8;
int[] result = binarySearch(in, k);
for (int i : result) {
System.out.println(i);
}
}
private static int[] binarySearch(int[] in,int k){
int[] res = new int[2];
int target = 0;
for (int i : in) {
target = k-i;
//int j = select01(in, 0, in.length - 1, target);
int j = select02(in, target);
if (j != 0 ){
res[0] = i;
res[1] = j;
break;
}
}
return res;
}
private static int select01(int[] input, int start, int end, int target){ //遞歸方式二分查找
int mid = (start + end)/2;
if (start<=end){
if (target == input[mid]){
return target;
}else if (target>input[mid]){
return select01(input, mid+1, end, target); //下一層函數的輸入值起始點，一定要為mid加1或減1，否則棧溢出
}else if (target<input[mid]){
return select01(input, start, mid-1, target);
}
}
return 0;
}
private static int select02(int[] input,int target){
int n = input.length;
int low = 0;
int high = n-1;
while (low<=high){
int mid = low + ((high-low)>>1);
if (input[mid] == target){
return input[mid];
}else if (input[mid] > target){
high = mid-1;
}else {
low = mid+1;
}
}
return 0;
}
}
解法二：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class test0102 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
HashMap<Integer, String> map = new HashMap<>();
while (sc.hasNextLine()){
String s = sc.nextLine();
if (s.equals(""))break;
int i = Integer.parseInt(s);
list.add(i);
}
Integer k = list.get(list.size()-1);
list.remove(list.size()-1);
for (Integer i : list) {
map.put(i,"");
}
int[] result = hashQuery(map, k);
for (int i : result) {
System.out.println(i);
}
}
private static int[] hashQuery(HashMap<Integer,String> map,int k){
int[] res = new int[2];
String s = map.get(map.size() - 1);
for (Integer i : map.keySet()) {
if (map.containsKey(k-i)){
res[0] = i;
res[1] = k-i;
break;
}
}
return res;
}
}
解法三：
import java.util.ArrayList;
import java.util.Scanner;
public class test0103 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
while (sc.hasNextLine()){
String s = sc.nextLine();
if (s.equals(""))break;
int i = Integer.parseInt(s);
list.add(i);
}
Integer k = list.get(list.size()-1);
list.remove(list.size()-1);
int[] result = pointerQuery(list, k);
for (int i : result) {
System.out.println(i);
}
}
private static int[] pointerQuery(ArrayList<Integer> list, int k){
int[] res = new int[2];
int p1 = 0;
int p2 = list.size()-1;
while (p1<p2){
if (list.get(p1)+list.get(p2) == k){
res[0] = list.get(p1);
res[1] = list.get(p2);
break;
}else if (list.get(p1)+list.get(p2) > k){
p2--;
}else if (list.get(p1)+list.get(p2) < k){
p1++;
}
}
return res;
}
}
7、數組中和為 0 的 3 個數字
題目：輸入一個數組，如何找出數組中所有和為 0 的 3 個數字的三元組？需要注意的是，返回值中不得包含重複的三元組。例如，在數組[-1,0,1,2,-1,-4]中有兩個三元組的和為 0，它們分別是[-1,0,1]和[-1,-1,2]。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class test0201 {
public static void main(String[] args) {
int[] input = {-1,0,1,2,-1,-4};
int target = 0;
List<List<Integer>> lists = threeSum(input, target);
lists.forEach(System.out::println);
}
private static List<List<Integer>> threeSum(int[] list,int target){
List<List<Integer>> result = new LinkedList<>();
Arrays.sort(list); //先對數組進行排序，方便後續查找
//先遍曆數組，指定當前的值為第一個值，再查找另外兩個值，使三個數之和為目標值
for (int i = 0; i < list.length-2; ) {
int goal = target - list[i]; //計算需要查找的其他兩個值的和
List<List<Integer>> res = twoSum(list, goal, i+1); //傳入twoSum函數，數組、目標值、查找的起始下標
res.forEach(System.out::println);
if (!res.isEmpty()){ //當其他兩個值查找的結果集不為空時，遍歷結果集，每一個結果都與當前遍歷的第一個數字組成一個最終結果數組
for (int j = 0; j < res.size(); j++) {
result.add(res.get(j));
}
}
int temp = list[i];
while (list[i]==temp && i<list.length-2){ //保證下一個便遍歷的值一定跟當前的值不同，並且一定至少會執行一次
i++;
}
}
return result;
}
//可以將最終結果數組傳入twoSum函數中，每次查找到符合要求的三個值直接放入最終的結果數組，這樣twoSum就不需要返回值
private static List<List<Integer>> twoSum(int[] list,int goal,int i){ //一個數字確定後，查找另外兩個數字
List<List<Integer>> res = new LinkedList<>();
int m = i-1;
int j = list.length-1;
while (i<j){ //從確定的那一個數字後面的子數組中查找，從子數組的第一位和最後一位開始查找
if (list[i] + list[j] == goal){ //當兩個數字之和是目標值時，將這兩個數字構建成數組，放到結果集中
res.add(Arrays.asList(list[m],list[i],list[j]));
int temp = list[i]; //為了去重，跳過與當前下標小的數字相同的數字，需保證小的下標小於大的坐標
while (list[i]==temp && i<j){
i++;
}
}else if (list[i] + list[j] > goal) { //當兩個數值大於目標值，大的下標減1
j--;
}else if (list[i] + list[j] < goal){ //當兩個數值小於目標值，小的下標加1
i++;
}
}
return res;
}
}
8、和大於或等於 k的最短子數組
題目：輸入一個正整數組成的數組和一個正整數 k，請問數組中和大於或等於 k 的連續子數組的最短長度是多少？如果不存在所有數字之和大於或等於 k 的子數組，則返回 0。例如，輸入數組[5,1,4,3]，k 的值為 7，和大於或等於 7 的最短連續子數組是[4,3]，因此輸出它的長度 2。
public class test0301 {
public static void main(String[] args) {
int[] in = {5,1,4,3};
int k = 7;
int res = queryCount(in, k);
System.out.println(res);
}
private static int queryCount(int[] in,int k){
int minCount = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
for (int right = 0; right < in.length; right++) {
sum += in[right];
while (sum>=k && left<=right){ //當sum>=k時，滿足要求，計算當前子字元串長度並取最小值，同時需要滿足左指針小於等於右指針
minCount=Math.min(minCount,right-left+1); //判斷時只考慮當前左右指針中間的子數組，不要考慮左指針右移一位後的結果
//當左指針超過右指針一位時，不會再進入循環計運算元數組最小長度
sum -= in[left++]; //每次先將sum和減去當前左指針指向的值，再將左指針右移一位
}
}
return minCount==Integer.MAX_VALUE ? 0:minCount;
}
}
9、乘積小於 k的子數組
題目：輸入一個由正整數組成的數組和一個正整數 k，請問數組中有多少個數字乘積小於 k 的連續子數組？例如，輸入數組[10,5,2,6]，k 的值為100，有 8 個子數組的所有數字的乘積小於 100，它們分別是[10]、[][][][][][][5]、[2]、[6]、[10,5]、[5,2]、[2,6]和[5,2,6]。
public class test0401 {
public static void main(String[] args) {
int[] in = {10,5,2,6};
int k = 100;
int res = queryMultiply(in, k);
System.out.println(res);
}
private static int queryMultiply(int[] in,int k){
int product = 1; //保存當前子數組乘積結果
int left = 0; //左指針
int count = 0; //記錄目前有多少子數組符合要求
for (int right = 0; right < in.length; right++) { //循環遍歷輸入的數組，當前下標為右指針
product *= in[right]; //計算到當前右指針的子數組的乘積
while (product>=k && left<=right){ //當子數組乘積大於等於k值同時左指針小於等於右指針時，當前子數組乘積除以左指針指向的數值，左指針右移一位
product /= in[left++]; //當前右指針指向的數值大於k時，左右指針都指向該數值，之後product=1，左指針會比右指針+1，跳出循環
}
//計算符合條件連續子數組數量時，只有以當前右指針指向數值為起始值的子數組是不重複的子數組，其餘包含的子數組都在之前計算中包含
//因此，計算當前子數組中滿足條件的所有與之前不重複數組，只需計算右指針-左指針+1
count += left<=right ? right-left+1:0; //當左指針大於右指針，說明當前右指針指向的數值大於k，此時count數值不變
}
return count;
}
}
10、和為 k的子數組
題目：輸入一個整數數組和一個整數 k，請問數組中有多少個數字之和等於 k 的連續子數組？例如，輸入數組[1,1,1]，k 的值為 2，有 2 個連續子數組之和等於 2。
import java.util.HashMap;
public class test0501 {
public static void main(String[] args) {
int[] in = {1,1,1};
int k = 2;
int res = queryMultiply(in, k);
System.out.println(res);
}
//計算從第一個數到當前下標位置累加和，從當前下標位置開始累加和為k，那麼從數組第一個數到找到的目標位置累加和為sum-k
//計算從第一個數開始到當前下標位置的累加和，key為累加和結果，value為+1，放到哈希表中
//要特殊考慮以下k=sum和k=0的情況
private static int queryMultiply(int[] in,int k){
int sum = 0;
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
//先給哈希表放入一個初始值(0,1)，因為當前下標sum=k時，則有一個滿足條件的數組，而前面保存的數組累加和中沒有這個結果（即使有sum=0，也會少計數一次）
map.put(0,1);
for (int i = 0; i < in.length; i++) { //遍曆數組
sum += in[i]; //計算當前下標的累加和
count += map.getOrDefault(sum-k,0); //獲取哈希表中有沒有記錄sum-k的值，有的話則有對應value數量個滿足條件的數組
//要查找完sum-k的值後，再把當前sum值放入哈希表中，因為如果先放入sum的值時，當k=0時，sum-k=sum，此時count+1，而數組中沒有k=0的子數組
map.put(sum,map.getOrDefault(sum,0)+1); //把到當前下標累加和放入哈希表中
}
return count;
}
}
11、0 和 1 個數相同的子數組
題目：輸入一個只包含 0 和 1 的數組，請問如何求 0 和 1 的個數相同的最長連續子數組的長度？例如，在數組[0,1,0]中有兩個子數組包含相同個數的 0 和 1，分別是[0,1]和[1,0]，它們的長度都是 2，因此輸出 2。
import java.util.HashMap;
public class test0601 {
public static void main(String[] args) {
int[] in = {0,1,0};
int res = queryMaxlength(in);
System.out.println(res);
}
private static int queryMaxlength(int[] in){
int max = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
in[i] = in[i]==0 ? -1:1; //簡單的判斷使用三元運算符使程式碼更易讀
//當數組中0和1數量相等時，子數組為從0下標到當前下標的所有數組，當哈希表中沒有key為0時，則不能計算這個子數組的長度，因此要先放入(0,1)
map.put(0,-1);
sum+=in[i]; //計算到當前下標的數組數字累加和
if (map.containsKey(sum)){ //如果哈希表中已經包含該累加和sum，那麼從上一次放入累加和的位置後一位到現在的下標位置累加和為0
max=Math.max(max,i-map.get(sum));
}else {
//哈希表中只放入某個sum值第一次出現的位置，以計算0與1相同的最長子數組
map.put(sum,i);
}
}
return max;
}
}
12、左右兩邊子數組的和相等
題目：輸入一個整數數組，如果一個數字左邊的子數組的數字之和等於右邊的子數組的數字之和，那麼返回該數字的下標。如果存在多個這樣的數字，則返回最左邊一個數字的下標。如果不存在這樣的數字，則返回 -1。例如，在數組[1,7,3,6,2,9]中，下標為 3 的數字（值為6）的左邊 3 個數字 1、7、3 的和與右邊兩個數字 2 和 9 的和相等，都是 11，因此正確的輸出值是 3。
public class test0701 {
public static void main(String[] args) {
int[] in = {1,7,3,6,2,9};
int res = queryEqual(in);
System.out.println(res);
}
private static int queryEqual(int[] in){
int total = 0;
int sum = 0;
int target = -1;
for (int i : in) { //計算數組綜合，方便後續遍歷計算右側數組之和
total += i;
}
for (int i = 0; i < in.length; i++) { //遍曆數組，計算數組中每個數值左側數組之和及右側數組之和
//先把in[i]放進sum也可以
//sum += in[i];
//if (i>=1 && sum-in[i] == total-sum){
// target = i;
//}
//空數組不是子數組，子數組是從一個數組中取出一些元素所構成的新的數組，而空數組沒有元素，因此要保證下標i>=1才能保證in[i]左右兩側都有子數組
if (i>=1 && sum == total-in[i]-sum){ //右側數組之和為數組綜合-當前下標數值-到當前下標之前數字之和，判斷右側數組之和與左側數組之和是否相等
target = i;
}
sum += in[i];
}
return target;
}
}
13、二維子矩陣的數字之和
題目：輸入一個二維矩陣，如何計算給定左上角坐標和右下角坐標的子矩陣的數字之和？對於同一個二維矩陣，計運算元矩陣的數字之和的函數可能由於輸入不同的坐標而被反覆調用多次。例如，輸入下圖中的二維矩陣，以及左上角坐標為(2,1)和右下角坐標為(4,3)的子矩陣，該函數輸出 8。
說明：左上角坐標為(2,1)，右下角坐標為(4,3)的子矩陣（有灰色背景部分）的數字之和等於 8
import java.util.HashMap;
public class test0801 {
public static void main(String[] args) {
}
private static int matrixSum(int[][] in, HashMap<Integer,Integer> scale){
int[][] sums = new int[in.length+1][in[0].length+1]; //新建一個比輸入數組長寬都大1的二維數組，保存從0點到輸入矩陣每個點的子矩陣中所有數字之和
int addSum = 0;
int res = 0;
int left_x = -1,left_y = -1,right_x = -1,right_y = -1;
for (Integer x : scale.keySet()) { //遍歷輸入的兩個點坐標哈希表，通過設置初始值-1來判斷當前遍歷的使左上角坐標還是右下角坐標
left_x = left_x == -1 ? x : left_x;
right_x = left_x == -1 ? right_x : x;
left_y = left_y == -1 ? scale.get(x) : left_y;
right_y = left_y == -1 ? right_y : scale.get(x);
}
for (int i = 0; i < in.length; i++) { //構建工具矩陣，保存0點到數組每個點的子矩陣的所有數字之和
addSum = 0;
for (int j = 0; j < in[0].length; j++) { //每個點矩陣之和可以看作橫坐標-1的子矩陣+當前行起始點到該點的一維子數組之和
addSum += in[i][j];
sums[i+1][j+1] = sums[i][j+1] + addSum;
}
}
//目標子矩陣數字之和 = 0點到目標矩陣右下角的子矩陣 - 0點到目標矩陣左側的子矩陣 - 0點到目標矩陣上側的子矩陣 + 0點到目標矩陣左上方的子矩陣
res = sums[right_x][right_y] - sums[right_x][left_y-1] - sums[left_x-1][right_y] + sums[left_x-1][left_y-1];
return res;
}
}
第三章 字元串
14、字元串中的變位詞
題目：輸入字元串 s1 和 s2，如何判斷字元串 s2 中是否包含字元串的某個變位詞？如果字元串 s2 中包含字元串 s1 的某個變位詞，則字元串 s1 至少有一個變位詞是字元串 s2 的子字元串。假設兩個字元串中只包含英文小寫字母。例如，字元串 s1 為”ac”，字元串 s2 為”dgcaf”，由於字元串 s2 中包含字元串 s1 的變位詞 “ca”，因此輸出為 true。如果字元串 s1 為 “ab”，字元串 s2 為”dgcaf”，則輸出為 false。
public class test0101 {
public static void main(String[] args) {
String str1 = "ac";
String str2 = "dgcaf";
System.out.println(anagram(str1,str2));
}
//判讀字元串2是否包含字元串1的變位詞
private static boolean anagram(String str1, String str2){
if (str1.length() > str2.length()){
return false;
}
int[] charSum = new int[26]; //數組每個位置的初始值為0
//循環遍歷字元串str1，每出現一個字母就把數組中對應位置的值+1
//先把str1字元串的字母資訊添加到charSum數組中，再將str2字元串中第一個子數組的字母資訊減去，這裡將兩步合併到一起，簡化程式碼
//把str2中第一個子字元串的字母資訊減去後，後續只需要在str2字元串中循環移動第一個子字元串的最左側和最右側指針進行判斷即可
for (int i = 0; i < str1.length(); i++) { //從字元串str2的0點開始，遍歷與字元串相同長度的子字元串，每出現一個字母就把數組中對應位置的值-1
charSum[str1.charAt(i) - 'a']++;
charSum[str2.charAt(i) - 'a']--;
}
//判斷數組中每個位置的值是否都為0，如果都為0，則表示str2字元串當前位置對應的與str1字元串長度相同的子字元串是str1的變位詞
if (judgeZero(charSum)){
return true;
}
//當前放入數組的str2中的子字元串是從0到str1.length()-1，按位逐漸向字元串str2右移
//每右移一位則在數組中子字元串最左側對應字母位置+1，最右側+1對應字母位置-1
int left = 0; //初始化一個左指針left=0，右指針i初始值為str1.length()，右指針i的最大值為str2.length()-1，進行循環遍歷
//str2字元串中向右循環遍歷子字元串，只需在數組中將子字元串右移一位的右側指針指向的字母資訊減去，左側指針指向的字母資訊加上即可
for (int i = str1.length(); i < str2.length(); i++) {
charSum[str2.charAt(i) - 'a']--; //最右側指針右移一位後，數組減去當前指針指向的字母資訊
//也可以不初始化左指針left，直接用 i-str1.length() 代替，因為i是右側指針的下一位，而要減去的是當前的左側指針指向的字母
charSum[str2.charAt(left++) - 'a']++; //因為遍歷子字元串時將最左側字母資訊在數組中減去了，所以，向右移動指針時，要把最左側字母資訊再加上
//str2中遍歷的子字元串每右移一位，都要判斷一次當前子字元串對應的數組值是否全為0，全為0則表示當前子字元串為str1字元串的變位詞
if (judgeZero(charSum)){
return true;
}
}
return false;
}
//判斷保存26個小寫字母數組中有沒有不為0
private static boolean judgeZero(int[] in){
for (int i : in) {
if (i != 0){
return false;
}
}
return true;
}
}
15、字元串中的所有變位詞
題目：輸入字元串 s1 和 s2，如何找出字元串 s2 的所有變位詞在字元串 s1 中的起始下標？假設兩個字元串中只包含英文小寫字母。例如，字元串 s1 為”cbadabacg”，字元串 s2 為”abc”，字元串 s2 的兩個變位詞”cba”和”bac”是字元串 s1 中的子字元串，輸出它們在字元串 s1 中的起始下標 0 和 5。
import java.util.LinkedList;
public class test0201 {
public static void main(String[] args) {
String s1 = "cbadabacg";
String s2 = "abc";
LinkedList<Integer> result = queryAnagram(s1, s2);
result.forEach(System.out::println);
}
//查找str2在str1中的變位詞
private static LinkedList<Integer> queryAnagram(String str1,String str2){
LinkedList<Integer> res = new LinkedList<>();
if (str1.length() < str2.length()){
return res;
}
int[] charSum = new int[26];
for (int i = 0; i < str2.length(); i++) {
charSum[str2.charAt(i) - 'a']++; //str2中每出現一個字元就把charSum數組中對應位置+1
charSum[str1.charAt(i) - 'a']--; //str1中每出現一個字元就把charSum數組中對應位置-1
}
if (judgeZero(charSum)){
res.add(0);
}
for (int i = str2.length(); i < str1.length(); i++) {
charSum[str1.charAt(i) - 'a']--;
charSum[str1.charAt(i-str2.length()) - 'a']++;
if (judgeZero(charSum)){
res.add(i-str2.length()+1);
}
}
return res;
}
private static boolean judgeZero(int[] in){
for (int i : in) {
if (i != 0){
return false;
}
}
return true;
}
}
16、不含重複字元的最長子字元串
題目：輸入一個字元串，求該字元串中不含重複字元的最長子字元串的長度。例如，輸入字元串”babcca”，其最長的不含重複字元的子字元串是”abc”，長度為 3。
解法一：
public class test0301 {
public static void main(String[] args) {
String in = "babcca";
int res = queryLongest(in);
System.out.println(res);
}
private static int queryLongest(String in){
int[] countNum = new int[256]; //新建一個256大小的數組保存字元串中字元資訊，因為沒有說明字元全為小寫字母，所以假設輸入字元為ASCII碼範圍內
int max = 0;
//當前子字元串為左指針右一位到右指針指向的位置
int left = -1; //初始化左指針為-1，右指針為0
int right = 0;
for (;right<in.length();right++) { //右指針按位右移遍歷字元串
countNum[in.charAt(right)]++; //當前右指針字元所在數組位置+1，遍曆數組，如果有等於2的數值，則左指針右移一位，當前左指針指向的字元所在數組位置-1
while (queryZero(countNum)) {
left++;
countNum[in.charAt(left)]--;
}
max = Math.max(max, right - left); //獲取已保存子字元串長度的最大值與當前子字元串長度中較大的數值
}
return max;
}
private static boolean queryZero(int[] countNum){ //遍曆數組，判斷是否有等於2的數值，有則當前子字元串中有重複字元
for (int i : countNum) {
if (i == 2){
return true;
}
}
return false;
}
}
解法二：
public class test0302 {
public static void main(String[] args) {
String in = "babcca";
int res = queryLongest(in);
System.out.println(res);
}
private static int queryLongest(String in){
int[] countNum = new int[256];
int max = 0;
int left = -1;
int right = 0;
//由於每次右指針右移時都會保證當前子字元串中沒有重複字元，因此出現的重複字元只會是右指針右移一位後指向的字元
//只需要右移左指針保證當前右指針指向的字元在子字元串中無重複即可保證子字元串中無重複字元
for (;right<in.length();right++){
countNum[in.charAt(right)]++;
while (countNum[in.charAt(right)]==2){ //當前右指針指向的字元在數組中對應數值為2時，左指針按位右移使右指針指向的字元對應數組數值為1
left++;
countNum[in.charAt(left)]--;
}
max = Math.max(max,right-left);
}
return max;
}
}
17、包含所有字元的最短字元串
題目：輸入兩個字元串 s 和 t，請找出字元串 s 中包含字元串 t 的所有字元的最短子字元串。例如，輸入的字元串 s 為”ADDBANCAD”，字元串 t 為”ABC”，則字元串 s 中包含字元’A’、’B’和’C’的最短子字元串是”BANC”。如果不存在符合條件的子字元串，則返回空字元串””。如果存在多個符合條件的子字元串，則返回任意一個。
import java.util.HashMap;
public class test0401 {
public static void main(String[] args) {
String s = "ADDBANCAD";
String t = "ABC";
String res = containsAll(s, t);
System.out.println(res);
}
private static String containsAll(String s,String t){
HashMap<Character, Integer> map = new HashMap<>(); //初始化一個hashmap保存字元串t中的字元資訊
int count = 0; //初始化一個count記錄字元串t中出現多少種字元
for (char c : t.toCharArray()) {
map.put(c,map.getOrDefault(c,0)+1);
if (map.get(c)==1){
count++;
}
}
//使用兩個指針start和end控制字元串s中子字元串的起始終止位置，minStart和minEnd記錄滿足條件的最小長度子字元串的起始終止位置
int start = 0;
int end = 0;
int minStart = 0;
int minEnd = 0;
int minLength = Integer.MAX_VALUE;
//如果字元串s最後一個字元剛好是字元串t最後一個字元，那麼進入循環後count=0，end=s.length()，此時start到end的子字元串滿足要求
while (end < s.length() || (count==0 && end==s.length())){
//當count>0時，判斷當前end指針指向的字元是否包含在map中，如果包含則value-1，如果value=0則count-1，end指針+1
//因為子字元串是start到end前一位，因此先判斷當前end指針指向的字元，再將end指針+1
if (count>0){
char i = s.charAt(end);
if (map.containsKey(i)){
map.put(i,map.get(i)-1);
if (map.get(i)==0){
count--;
}
}
end++;
}else {
//當count=0時，當前子字元串滿足條件，判斷end-start長度是否為最小，保存最小長度子字元串的起始終止位置
minLength = Math.min(minLength,end-start);
minEnd = end;
minStart = start;
//判斷map中是否包含當前start指針指向的字元，如果包含則value+1，如果value=1則count+1，start指針+1
char j = s.charAt(start);
if (map.containsKey(j)){
map.put(j,map.get(j)+1);
if (map.get(j)==1){
count++;
}
}
start++;
}
}
//substring方法截取字元串為起始下標start到終止下標end前一位的子字元串
System.out.println(minStart+"and"+minEnd);
return minLength == Integer.MAX_VALUE ? null:s.substring(minStart,minEnd);
}
}
18、有效的迴文
題目：給定一個字元串，請判斷它是不是迴文。假設只需要考慮字母和數字字元，並忽略大小寫。例如，”Was it a cat I saw?”是一個迴文字元串，而”race a car”不是迴文字元串。
public class test0501 {
public static void main(String[] args) {
String s1 = "Was it a cat I saw?";
String s2 = "race a car";
System.out.println(judgePalindrome(s1));
System.out.println(judgePalindrome(s2));
}
private static boolean judgePalindrome(String s){
int left = 0;
int right = s.length()-1;
while (left<right){ //當左右指針指向的字元不是字母或數字時，則跳過該字元
if (!Character.isLetterOrDigit(s.charAt(left))){
left++;
}else if (!Character.isLetterOrDigit(s.charAt(right))){
right--;
}else { //當兩個指針指向的字元都是字母或數字時，將兩個指針指向的字元全部轉換為小寫字元再判斷是否相等，數字字元轉換小寫後還是本身
if (Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))){
return false;
}
left++;
right--;
}
}
return true;
}
}
19、最多刪除一個字元得到迴文
題目：給定一個字元串，請判斷如果最多從字元串中刪除一個字元能不能得到一個迴文字元串。例如，如果輸入字元串”abca”，由於刪除字元’b’或’c’就能得到一個迴文字元串，因此輸出為 true。
public class test0601 {
public static void main(String[] args) {
String s = "abca";
System.out.println(judgePalindrome(s));
}
//因為要滿足最多刪除一個字元，保證剩餘字元串是迴文字元串
//因此可以使左右指針從兩端逐漸向內移動，找到不同的字元後，分別刪除左右指針指向的字元來判斷剩餘字元串是否是迴文字元串
private static boolean judgePalindrome(String s){
int left = 0;
int right = s.length()-1;
//當s.length()為奇數時，s.length()/2為字元串s中間字元的下標；當s.length()為偶數時，s.length()/2為字元串s中間右一位字元下標
//字元串中字元下標是從0開始的
for (;left<s.length()/2;left++,right--){
//左指針按位右移，右指針按位左移，當左指針指向字元與右指針指向的字元不相等時，在當前位置中止循環
if (s.charAt(left)!=s.charAt(right)){
break;
}
}
//在中止循環的位置將左指針右移一位或將右指針左移一位繼續判斷剩下的子字元串是否為迴文字元串
//當循環完全執行沒有中止時，左指針最終的值為s.length()/2
return left==s.length()/2 || judgePartial(s,left,right-1) || judgePartial(s,left+1,right);
}
private static boolean judgePartial(String s,int start,int end){
for (;start<end;start++,end--){
if (s.charAt(start)!=s.charAt(end)){
return false;
}
}
return true;
}
}
20、迴文子字元串的個數
題目：給定一個字元串，請問該字元串中有多少個迴文連續子字元串？例如，字元串”abc”有 3 個迴文子字元串，分別為”a”、”b”和”c”；而字元串”aaa”有 6 個迴文子字元串，分別為”a”、”a”、”a”、”aa”、”aa”和”aaa”。
public class test0701 {
public static void main(String[] args) {
String s1 = "abc";
String s2 = "aaa";
System.out.println(totalPalindrome(s1));
System.out.println(totalPalindrome(s2));
}
private static int totalPalindrome(String s){
int count = 0;
//迴文字元串分為奇數個字元和偶數個字元兩種，判斷字元串是否是迴文字元串可以從字元串中間位置
//奇數個字元的字元串中間字元只有一個，偶數個字元的字元串中間字元有兩個
//將start指針和end指針逐漸同時向前一位和後一位遍歷，如果兩個指針指向的字元相同，那麼兩個指針中間部分為迴文字元串，此時迴文字元串個數count+1
//遍歷字元串s的每個字元，分別判斷以當前字元為中心字元的奇數個字元的字元串和偶數個字元的字元串中有多少個迴文字元串
for (int i = 0; i < s.length(); i++) {
count += countPalindrome(s,i,i);
count += countPalindrome(s,i,i+1);
}
return count;
}
private static int countPalindrome(String s,int start,int end){
int count = 0;
//可以將while循環修改為以下判斷方式，可以減少一條判斷語句及break的書寫
//while (start>=0 && end<s.length() && s.charAt(start)==s.charAt(end)){
// count++;
// start--;
// end++;
//}
while (start>=0 && end<s.length()){
if (s.charAt(start)==s.charAt(end)){
count++;
start--;
end++;
}else {
break;
}
}
return count;
}
}
